document.write('
Data hosted with ♥ by Pastebin.com - Download Raw - See Original
  1. import java.math.BigInteger;
  2.  
  3. /*
  4.  ============================================================================
  5.  Author      : Catarina Moreira
  6.  Copyright   : Catarina Moreira all rights reserved
  7.  Description : Implementation of the matrix form Fibonacci algorithm
  8.               | 1 1 | ^ n = | F(n+1) F(n)   |
  9.               | 1 0 |   | F(n)   F(n-1) |
  10.  ============================================================================
  11.  */
  12.  
  13. public class MatrixForm
  14. {
  15.     public BigInteger runFibonacci(int n)
  16.     {
  17.         BigInteger[ ][ ] fib_matrix = { {BigInteger.ONE, BigInteger.ONE}, {BigInteger.ONE,  BigInteger.ZERO} };
  18.     BigInteger[ ][ ] result =     { {BigInteger.ONE, BigInteger.ZERO},{BigInteger.ZERO, BigInteger.ONE} };
  19.        
  20.     if( n == 0)
  21.        return BigInteger.ZERO;
  22.        
  23.     if( n == 1)
  24.            return BigInteger.ONE;
  25.        
  26.         BigInteger i;
  27.     for( i = new BigInteger(Integer.toString(n)); i.compareTo(BigInteger.ZERO) != 0; i = i.shiftRight(1))  
  28.     {
  29.         if (i.remainder(new BigInteger("2")).compareTo(BigInteger.ZERO) != 0)
  30.            result = karatsubaMultiplication(result, fib_matrix);
  31.              
  32.             fib_matrix = karatsubaMultiplication(fib_matrix, fib_matrix);  
  33.     }
  34.     return result[0][1];
  35.     }  
  36.  
  37.     public BigInteger[][] karatsubaMultiplication(BigInteger[][] matrix1, BigInteger[][] matrix2)
  38.     {
  39.         BigInteger[][] result = new BigInteger[2][2];
  40.    
  41.         for( int i = 0; i < 2; i++ )
  42.        for( int j = 0; j < 2; j++ )
  43.           result[i][j] = karatsuba(matrix1[i][0], matrix2[0][j]).add(
  44.                  karatsuba(matrix1[i][1], matrix2[1][j]));
  45.         return result;
  46.      }
  47.  
  48.      public BigInteger karatsuba(BigInteger x, BigInteger y)
  49.      {
  50.          int N = Math.max(x.bitLength(), y.bitLength());
  51.          if (N <= 2000) return x.multiply(y);  
  52.          
  53.      N = (N / 2) + (N % 2);
  54.          
  55.          BigInteger b = x.shiftRight(N);
  56.          BigInteger a = x.subtract(b.shiftLeft(N));
  57.          BigInteger d = y.shiftRight(N);
  58.          BigInteger c = y.subtract(d.shiftLeft(N));
  59.  
  60.          BigInteger ac    = karatsuba(a, c);
  61.          BigInteger bd    = karatsuba(b, d);
  62.          BigInteger abcd  = karatsuba(a.add(b), c.add(d));
  63.  
  64.          return ac.add(abcd.subtract(ac).subtract(bd).shiftLeft(N)).add(bd.shiftLeft(2*N));
  65.     }
  66. }
');