# 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.