## 13/09/2015

### [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.

`````` 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)));
for(int i = 0; i < exp-1; i++){
BigInteger F2  = F.pow(2);

if ((n & mask) != 0){
F   = temp;
}
else

sign = (n & mask) != 0 ? -2: 2;
}
if ((n & (mask >> 1)) == 0)
return F.multiply(L);
else
}
``````

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[] {
};
}

// 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;

if (((n >>> i) & 1) != 0) {
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