# Java Fibonacci serie - Knuth multiplication

Leonardo Fibonacci,the Italian mathematician (from Pisa, 1170, one of the most important mathematician of all time) invented the famous serie defined recursively as follows:




We all know that as programmers once in life (at least) we will write some piece of code to compute the  element of the serie. Recursive implementation is straightforward but inefficient, due to the exponential number of recursive calls, that make "hard" to compute numbers bigger that 40. It is very easy to come up with some iterative or memoised implementation, that lowers the complexity to  and allows to efficently compute "any" number of the serie.
In this post we will derive an implementation (JAVA) that have complexity 1)using results from Knuth, Fibonacci multiplication,1988.

Knuth observed that the following holds:
 = 

infact it easy to proof by induction:

Base case: N=1
 =  = 

Suppose it hold up to  and show that holds for 
 =   =   =

 = 

Another observation that we'll use to derive the algorithm is that if  is a matrix then , and in particular with  even 

Let's see the actual code.

The FibMatr class, simply is used to store the 4 integer field used during the Knuth multiplication. BigInteger are required here due to the large number that the serie produces very soon. multiply method performs the matrix multiplication and store the result in a new matrix leaving the operands unaffected by the operation.

class FibMatr{
BigInteger Q0,Q1,Q2,Q3;

public  FibMatr(BigInteger a,BigInteger b,BigInteger c,BigInteger d) {
Q0=a;
Q1=b;
Q2=c;
Q3=d;
}

public  FibMatr() {
Q0=BigInteger.ONE;
Q1=BigInteger.ONE;
Q2=BigInteger.ONE;
Q3=BigInteger.ZERO;
}

public FibMatr multiply(FibMatr p){
FibMatr f= new FibMatr();
return f;
}
};


This is the recursive function used to compute the  element of the serie. Base case return the Knuth matrix while if the current  is even we recursively find the matrix at  and the return it squared. If  is odd the Knuth matrix is multiplied with the th element. The overall complexity is obviously 

public static  FibMatr fibLog(int n){
if(n<=1)
return (new FibMatr());
else
if( (n & 0x1) ==0){
FibMatr m = fibLog( n/2);
return m.multiply(m);
}else{
FibMatr m = new FibMatr();
return m.multiply(fibLog( n-1 ) );
}

}


References   [ + ]

 1 ↑ using results from Knuth, Fibonacci multiplication,1988