If you find the matrix implementation above intimidating, here's how to get the same
O(log n) behavior* using an amazing relationship between
Fibonacci numbers and the
Golden Ratio. The Golden Ratio, typically represented by the
Greek letter
phi (Φ), is defined as
Φ = (1 + 51/2) / 2,
or approximately 1.618. We'll also use the conjugate of Φ, which we'll call Φ^:
Φ^ = (1 - 51/2) / 2,
or approximately -.618. The formula for the nth Fibonacci number, then, is simply:
Fn = (Φ^n - Φn) / 51/2
We can further simplify the formula by getting rid of the conjugate, since its contribution is always pretty negligible. Because |Φ^| < 1, we know |Φ^n| / 51/2 < 1/51/2 < 1/2, so the subtracted portion will always be less than a half. Therefore we can say Fn = Φn / 51/2, rounded to the nearest integer. In other words, to get the nth Fibonacci number, all you have to do is take the Golden Ratio to the nth power, divide it by the square root of 5, and round it off. Amazing, right?
But why is any of this the case? Well, Fibonacci numbers and the Golden Ratio both occur with freakish regularity in nature, so it makes sense that they would be cosmically linked somehow. Ok, so the real answer is I have no freaking clue why**. But logic shows us things we can't necessarily grasp intuitively, and I can at least prove that it's true.
* The original version of this writeup made the somewhat smug assertion that we could get O(1) time from this "algorithm", but pfft set me straight: computing the nth power of phi still requires log n time. This is why I shouldn't do technical nodes.
** For a real explanation of the relationship between the Fibonacci numbers and the Golden Ratio, see mblase's definitive writeup under the latter.
Proof
The recursive definition of the Fibonacci sequence is:
F0 = 0
F1 = 1
Fn+2 = Fn + Fn+1 (n >= 0)
Let P(n) be the proposition that Fn = (Φn - Φ^n) / 51/2.
For n of 1 and 2: F1 is defined to be 1. (Φ1 - Φ^1) / 51/2 = 1, so P(1) is true. F2 is defined to be F0 + F1 = 0 + 1 = 1. (Φ2 - Φ^2) / 51/2 = 1, so P(2) is true as well.
Now for the inductive step. Assume P(k) and P(k+1) to be true; that is, Fk = (Φk - Φ^k) / 51/2 and Fk+1 = (Φk+1 - Φ^k+1) / 51/2. We will show that P(k+2) can be inferred from this. By definition, Fk+2 = Fk + Fk+1. Based on the above assumption, we can substitute this for the right side of the equation:
Fk+2 = (Φk - Φ^k) / 51/2 + (Φk+1 - Φ^k+1) / 51/2
With some algebraic manipulation,
Fk+2 = ((Φk - Φ^k) + (Φk+1 - Φ^k+1)) / 51/2
Fk+2 = (Φk + Φk+1 - Φ^k - Φ^k+1) / 51/2
Fk+2 = (Φk(1 + Φ) - Φ^k(1 + Φ^) / 51/2
Fk+2 = (ΦkΦ2 - Φ^kΦ^2 / 51/2 ***
Fk+2 = (Φk+2 - Φ^k+2) / 51/2
Which is exactly what we were proposing to show. Therefore (P(k) & P(k+1)) --> P(k+2) and the proof is complete.
*** Show that Φ2 = 1 + Φ:
Φ2 = ((1 + 51/2)/2)2
Φ2 = (1 + 2*51/2 + 5) / 4
Φ2 = (6 + 2*51/2) / 4
Φ2 = (3 + 51/2) / 2
Φ2 = (2 + 1 + 51/2) / 2
Φ2 = 2/2 + (1 + 51/2) / 2
Φ2 = 1 + Φ
(The same process can be used to show that Φ^2 = 1 + Φ^)
ariels says "One problem with using
Binet's formula (as you do) is that in order to perform
accurate calculations of φ^n/sqrt(5) you need to expand the two
quadratic surds (φ and sqrt(5)) to increasing precisions. I think you run out of precision quite quickly with
floats or even
doubles..."