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

## No comments:

## Post a Comment

With great power comes great responsibility.

Da grandi poteri derivano grandi responsabilità.