[Java] Better Fibonacci algorithms

The last time we saw a good Fibonacci algorithm, which is better than the textbook one, but still falls short of its duties for numbers around 100.

So here are a couple others algorithms which can efficiently compute big Fibonacci numbers correctly. I was able to test them up to around 10 millions, after which it took more than 30 seconds on my machine to produce a solution, which wasn't always correct.

The first one is based on this article from Daisuke Takahashi:

 public static BigInteger fib(int n){  
   
     BigInteger F = BigInteger.ONE;  
     BigInteger L = BigInteger.ONE;  
   
     int sign = -2;  
     int exp = (int)Math.floor((Math.log(n)/Math.log(2)));  
     int mask = (int)Math.pow(2, exp);  
     for(int i = 0; i < exp-1; i++){  
       mask = mask >> 1;  
       BigInteger F2  = F.pow(2);  
       BigInteger FL2 = F.add(L).pow(2);  
       F = FL2.subtract(F2.multiply(BigInteger.valueOf(6))).shiftRight(1).add(BigInteger.valueOf(-sign));  
   
       if ((n & mask) != 0){  
         BigInteger temp = FL2.shiftRight(2).add(F2);  
         L = temp.add(F.shiftLeft(1));  
         F   = temp;  
       }  
       else  
         L  = F2.multiply(BigInteger.valueOf(5)).add(BigInteger.valueOf(sign));  
   
       sign = (n & mask) != 0 ? -2: 2;  
     }  
     if ((n & (mask >> 1)) == 0)  
       return F.multiply(L);  
     else  
       return F.add(L).shiftRight(1).multiply(L).subtract(BigInteger.valueOf(sign >> 1));  
   }  

Then a couple others from Nayuki:

1) Using the matrix exponentiation method:

 private static BigInteger fastFibonacciMatrix(int n) {  
           BigInteger[] matrix = {BigInteger.ONE, BigInteger.ONE, BigInteger.ONE, BigInteger.ZERO};  
           return matrixPow(matrix, n)[1];  
      }  
        
      // Computes the power of a matrix. The matrix is packed in row-major order.  
      private static BigInteger[] matrixPow(BigInteger[] matrix, int n) {  
           if (n < 0)  
                throw new IllegalArgumentException();  
           BigInteger[] result = {BigInteger.ONE, BigInteger.ZERO, BigInteger.ZERO, BigInteger.ONE};  
           while (n != 0) { // Exponentiation by squaring  
                if (n % 2 != 0)  
                     result = matrixMultiply(result, matrix);  
                n /= 2;  
                matrix = matrixMultiply(matrix, matrix);  
           }  
           return result;  
      }  
        
      // Multiplies two matrices.  
      private static BigInteger[] matrixMultiply(BigInteger[] x, BigInteger[] y) {  
           return new BigInteger[] {  
                multiply(x[0], y[0]).add(multiply(x[1], y[2])),  
                multiply(x[0], y[1]).add(multiply(x[1], y[3])),  
                multiply(x[2], y[0]).add(multiply(x[3], y[2])),  
                multiply(x[2], y[1]).add(multiply(x[3], y[3]))  
           };  
      }  
   
 // Multiplies two BigIntegers. This function makes it easy to swap in a faster algorithm like Karatsuba multiplication.  
      private static BigInteger multiply(BigInteger x, BigInteger y) {  
           return x.multiply(y);  
      }  

2) Using the fast doubling method:

 private static BigInteger fastFibonacciDoubling(int n) {  
           BigInteger a = BigInteger.ZERO;  
           BigInteger b = BigInteger.ONE;  
           int m = 0;  
           for (int i = 31 - Integer.numberOfLeadingZeros(n); i >= 0; i--) {  
                  
                // Double it  
                BigInteger d = multiply(a, b.shiftLeft(1).subtract(a));  
                BigInteger e = multiply(a, a).add(multiply(b, b));  
                a = d;  
                b = e;  
                m *= 2;  
                  
                // Advance by one conditionally  
                if (((n >>> i) & 1) != 0) {  
                     BigInteger c = a.add(b);  
                     a = b;  
                     b = c;  
                     m++;  
                }  
           }  
           return a;  
      }  
   
 // Multiplies two BigIntegers. This function makes it easy to swap in a faster algorithm like Karatsuba multiplication.  
      private static BigInteger multiply(BigInteger x, BigInteger y) {  
           return x.multiply(y);  
      }  

Also, the suggestion to implement your own Karatsuba multiplication should be surpassed in Java 8 by the fact that Java 8 already uses it if necessary