The world of Java Enterprise development full of frameworks, configuration files, things like hibernate, maven, JPAs, EJBs and other three letter acronyms may make you forget how cool it was to dive deep into the most exciting areas of the CS.

Luckily there there are places on the web that help you remember the good old times (namely the classes on algorithms at your the university, I guess). Javalobby with their Thursday Code Puzzler is definitely one of them.

So today, they asked to find the n-th Fibonacci number. A naive solution is pretty straightforward. A good solution is not that obvious, though. You could probably easily code a solution that runs in O(n) time.

It turns out it can be computed in logarithmic time. There are a couple of tricky ways to do it, I like one of them the most. First, however you have to know how to raise a number to a power in logarithmic time.

In order to do that the Divide-and-Conquer paradigm may be used. To make a long story short, the idea is to use an algorithm that halves the exponent and then recursively computes the power. In the merge phase of the divide and conquer process, the result is multiplied by itself for even exponents (the odd exponents needs one step more, but that only affects the constant factor of algorithms running time). The merge step is based on a following property of exponentiation:

X

^{m}* X^{n}= X^{m+n}

In case of even exponent e:

X

^{e/2}* X^{e/2}= X^{e}

In case of odd numbers and extra step is needed

X

^{(e – 1)/2}* X^{(e – 1)/2}* X = X^{e}

Once you know how to implement exponentiation in logarithmic time (and I leave the proof that this runs in logarithmic time to the reader), you can move on to the tricky part. Let’s assume the following is true (that’s the tricky part and I will not prove it here either):

The only thing you have to do is to implement matrix exponentiation and you then can calculate the n-th Fibonacci number in logarithmic time by raising the matrix

See my example implementation of the recursive matrix exponentiation.

private TwoByTwoMatrix computePower(TwoByTwoMatrix matrix, long e) { if (e < 0) { throw new IllegalArgumentException("Exponent must be non-negative, [" + e + "] was given"); } else if (e == 0) { return TWO_BY_TWO_IDENTITY_MATRIX; } else { if (isEven(e)) { TwoByTwoMatrix raisedToHalvedPower = computePower(matrix, e / 2); return raisedToHalvedPower.multiplyBy(raisedToHalvedPower); } else { TwoByTwoMatrix raisedToHalvedPower = computePower(matrix, (e - 1) / 2); return raisedToHalvedPower.multiplyBy(raisedToHalvedPower) .multiplyBy(matrix); } } }

Your n-th Fibonacci number will be always in the top-right or bottom left corner of the result matrix.

You can browse the complete project on GitHub.

#1 by

Marco Gonzalezon December 20, 2012 - 11:39 pmHi, I enjoyed your post. I like math so much as programming. And with your post you have touched a very interesting point. Do you know that following a mathematical process, similar to yours, you can calculate Fibonacci numbers in O(1). I can give you the calculation process, but for the sake of this comment, I’ll omit that, and I will only give you the results for Fibonacci(n):

double sqrt5 = sqrt(5);

return round((pow((sqrt5+1)/2, n) – pow(-1, n)*pow((sqrt5-1)/2, n)) / sqrt5)

Let me add that I am not very good with java syntax.

This solution is O(1), but with this, we would skipped the “computePower” function.

The mathematical process is quite long, but very interesting. And the formula too, it doesn’t appear to give the result. Sadly, you have to put a “round” function, because of precision.

#2 by marekdec on December 21, 2012 - 11:25 am

Marco,

Thanks for bringing here this golden-ratio based trick.

Note, however, that your solution is quite similar to the one I described here. While it may seem it is O(1), you actually have to perform a power operation which at best can be computed in O(log(n)). Its main drawback additionally, is the fact that it involves multiplications of floating point numbers (which are supposed to approximate the irrational value of golden ratio), and this may provide incorrect results in a very bad case. And I guess also the constant factor hidden behind the O-notation will be greater when you use the method you describe.

Thank you again for your comment, it definitely deepens the problem and brings new light to it.