Yet Another one on Fibonacci serie - Knuth multiplication

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();
		f.Q0=(Q0.multiply(p.Q0)).add(Q1.multiply(p.Q2));
		f.Q1=(Q0.multiply(p.Q1)).add(Q1.multiply(p.Q3));
		f.Q2=(Q2.multiply(p.Q0)).add(Q3.multiply(p.Q2));
		f.Q3=(Q2.multiply(p.Q1)).add(Q3.multiply(p.Q3));
		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

Be the first to leave a comment. Don’t be shy.

Join the Discussion

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>