Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- * Compute Fibonacci number using Dijkstra's recurrence:
- *
- * F(2N-1) = F(N-1)^2 + F(N)^2
- * F(2N) = (2 F(N-1) + F(N)) F(N)
- *
- * Use the following BigInteger implementation for maximum performance:
- * https://raw.github.com/tbuktu/bigint/master/src/main/java/java/math/BigInteger.java
- *
- */
- import java.util.HashMap;
- import java.util.Map;
- public class Fibonacci {
- private static Map<BigInteger, BigInteger> cache = new HashMap<BigInteger, BigInteger>();
- static {
- cache.put(BigInteger.ONE, BigInteger.ONE);
- cache.put(BigInteger.ZERO, BigInteger.ZERO);
- }
- public static BigInteger fibonacci(BigInteger n) {
- if (cache.containsKey(n)) return cache.get(n);
- // odd
- if (n.testBit(0)) {
- BigInteger n2 = n.shiftRight(1);
- BigInteger n3 = n2.add(1);
- BigInteger result = fibonacci(n2).multiply(fibonacci(n2)).add(fibonacci(n3).multiply(fibonacci(n3)));
- cache.put(n, result);
- return result;
- }
- // even
- else {
- BigInteger n2 = n.shiftRight(1);
- BigInteger n3 = n2.add(-1);
- BigInteger result = fibonacci(n2).multiply(fibonacci(n2).add(fibonacci(n3).add(fibonacci(n3))));
- cache.put(n, result);
- return result;
- }
- }
- private static void printResult(BigInteger num){
- System.out.printf(" Number of bits: %d%n", num.bitLength());
- byte[] numHex = num.toByteArray();
- System.out.print(" First 10 bytes: ");
- for (int i = 0; i < (numHex.length < 10 ? numHex.length : 10); i++) {
- System.out.printf(" %02x", numHex[i]);
- }
- System.out.println();
- if (numHex.length > 20){
- System.out.print(" Last 10 bytes : ");
- for (int i = numHex.length - 10; i < numHex.length; i++) {
- System.out.printf(" %02x", numHex[i]);
- }
- System.out.println();
- }
- }
- public static void main(String[] args) {
- long time = System.currentTimeMillis();
- BigInteger N = new BigInteger(args[0]);
- System.out.printf("Searching for Fibonacci(%,d)%n", Integer.parseInt(args[0]));
- BigInteger res = fibonacci(N);
- printResult(res);
- System.out.printf(" Time to calculate %d ms%n%n", System.currentTimeMillis() - time);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement