Pastebin is 300% more awesome when you are logged in. Sign Up, it's FREE!
Guest

Fast Fibonacci sequence based on Dijkstra's recurrence

By: cat_baxter on May 30th, 2012  |  syntax: Java 5  |  size: 2.41 KB  |  hits: 175  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
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);
  28.             BigInteger n3 = n2.add(1);
  29.             BigInteger result = fibonacci(n2).multiply(fibonacci(n2)).add(fibonacci(n3).multiply(fibonacci(n3)));
  30.             cache.put(n, result);
  31.             return result;
  32.         }
  33.         // even
  34.         else {
  35.             BigInteger n2 = n.shiftRight(1);
  36.             BigInteger n3 = n2.add(-1);
  37.             BigInteger result = fibonacci(n2).multiply(fibonacci(n2).add(fibonacci(n3).add(fibonacci(n3))));
  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. }