import java.math.BigInteger;
/*
============================================================================
Author : Catarina Moreira
Copyright : Catarina Moreira all rights reserved
Description : Implementation of the matrix form Fibonacci algorithm
| 1 1 | ^ n = | F(n+1) F(n) |
| 1 0 | | F(n) F(n-1) |
============================================================================
*/
public class MatrixForm
{
public BigInteger runFibonacci(int n)
{
BigInteger[ ][ ] fib_matrix = { {BigInteger.ONE, BigInteger.ONE}, {BigInteger.ONE, BigInteger.ZERO} };
BigInteger[ ][ ] result = { {BigInteger.ONE, BigInteger.ZERO},{BigInteger.ZERO, BigInteger.ONE} };
if( n == 0)
return BigInteger.ZERO;
if( n == 1)
return BigInteger.ONE;
BigInteger i;
for( i = new BigInteger(Integer.toString(n)); i.compareTo(BigInteger.ZERO) != 0; i = i.shiftRight(1))
{
if (i.remainder(new BigInteger("2")).compareTo(BigInteger.ZERO) != 0)
result = karatsubaMultiplication(result, fib_matrix);
fib_matrix = karatsubaMultiplication(fib_matrix, fib_matrix);
}
return result[0][1];
}
public BigInteger[][] karatsubaMultiplication(BigInteger[][] matrix1, BigInteger[][] matrix2)
{
BigInteger[][] result = new BigInteger[2][2];
for( int i = 0; i < 2; i++ )
for( int j = 0; j < 2; j++ )
result[i][j] = karatsuba(matrix1[i][0], matrix2[0][j]).add(
karatsuba(matrix1[i][1], matrix2[1][j]));
return result;
}
public BigInteger karatsuba(BigInteger x, BigInteger y)
{
int N = Math.max(x.bitLength(), y.bitLength());
if (N <= 2000) return x.multiply(y);
N = (N / 2) + (N % 2);
BigInteger b = x.shiftRight(N);
BigInteger a = x.subtract(b.shiftLeft(N));
BigInteger d = y.shiftRight(N);
BigInteger c = y.subtract(d.shiftLeft(N));
BigInteger ac = karatsuba(a, c);
BigInteger bd = karatsuba(b, d);
BigInteger abcd = karatsuba(a.add(b), c.add(d));
return ac.add(abcd.subtract(ac).subtract(bd).shiftLeft(N)).add(bd.shiftLeft(2*N));
}
}