Fibonacci revisited

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:

Xm * Xn = Xm+n

In case of even exponent e:

Xe/2 * Xe/2 = Xe

In case of odd numbers and extra step is needed

X(e – 1)/2 * X(e – 1)/2 * X = Xe

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.

About these ads
  1. #1 by Marco Gonzalez on December 20, 2012 - 11:39 pm

    Hi, 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: