Check out the Pastebin Gadgets Shop. We have thousands of fun, geeky & affordable gadgets on sale :-)Want more features on Pastebin? Sign Up, it's FREE!
tweet

# Fast Fibonacci sequence based on Dijkstra's recurrence

By: cat_baxter on May 30th, 2012  |  syntax: Java 5  |  size: 2.41 KB  |  views: 300  |  expires: Never
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
1. /*
2.  *    Compute Fibonacci number using Dijkstra's recurrence:
3.  *
4.  *    F(2N-1)  = F(N-1)^2 + F(N)^2
5.  *    F(2N)    = (2 F(N-1) + F(N)) F(N)
6.  *
7.  *    Use the following BigInteger implementation for maximum performance:
8.  *    https://raw.github.com/tbuktu/bigint/master/src/main/java/java/math/BigInteger.java
9.  *
10.  */
11. import java.util.HashMap;
12. import java.util.Map;
13.
14. public class Fibonacci {
15.
16.     private static Map<BigInteger, BigInteger> cache = new HashMap<BigInteger, BigInteger>();
17.     static {
18.             cache.put(BigInteger.ONE,  BigInteger.ONE);
19.             cache.put(BigInteger.ZERO, BigInteger.ZERO);
20.     }
21.
22.     public static BigInteger fibonacci(BigInteger n) {
23.
24.         if (cache.containsKey(n)) return cache.get(n);
25.         // odd
26.         if (n.testBit(0)) {
27.             BigInteger n2 = n.shiftRight(1);
30.             cache.put(n, result);
31.             return result;
32.         }
33.         // even
34.         else {
35.             BigInteger n2 = n.shiftRight(1);
38.             cache.put(n, result);
39.             return result;
40.         }
41.     }
42.
43.     private static void printResult(BigInteger num){
44.         System.out.printf("  Number of bits:  %d%n", num.bitLength());
45.         byte[] numHex = num.toByteArray();
46.         System.out.print("  First 10 bytes: ");
47.         for (int i = 0; i < (numHex.length < 10 ? numHex.length : 10); i++) {
48.             System.out.printf(" %02x", numHex[i]);
49.         }
50.         System.out.println();
51.         if (numHex.length > 20){
52.             System.out.print("  Last 10 bytes : ");
53.             for (int i = numHex.length - 10; i < numHex.length; i++) {
54.                 System.out.printf(" %02x", numHex[i]);
55.             }
56.             System.out.println();
57.         }
58.     }
59.
60.     public static void main(String[] args) {
61.         long time = System.currentTimeMillis();
62.         BigInteger N = new BigInteger(args[0]);
63.         System.out.printf("Searching for Fibonacci(%,d)%n", Integer.parseInt(args[0]));
64.         BigInteger res = fibonacci(N);
65.         printResult(res);
66.         System.out.printf("  Time to calculate %d ms%n%n", System.currentTimeMillis() - time);
67.     }
68. }
clone this paste RAW Paste Data
Top