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 + 5^{1/2}) / 2,

or approximately 1.618. We'll also use the conjugate of Φ, which we'll call Φ^:

Φ^ = (1 - 5^{1/2}) / 2,

or approximately -.618. The formula for the *n*th Fibonacci number, then, is simply:

**
F**_{n} = (Φ^^{n} - Φ^{n}) / 5^{1/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}| / 5^{1/2} < 1/5^{1/2} < 1/2, so the subtracted portion will always be less than a half. Therefore we can say **F**_{n} = Φ^{n} / 5^{1/2}, rounded to the nearest integer. In other words, to get the *n*th Fibonacci number, all you have to do is take the Golden Ratio to the *n*th 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 *n*th 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:

F_{0} = 0

F_{1} = 1

F_{n+2} = F_{n} + F_{n+1} (n >= 0)

Let P(n) be the proposition that F_{n} = (Φ^{n} - Φ^^{n}) / 5^{1/2}.

For n of 1 and 2: F_{1} is defined to be 1. (Φ^{1} - Φ^^{1}) / 5^{1/2} = 1, so P(1) is true. F_{2} is defined to be F_{0} + F_{1} = 0 + 1 = 1. (Φ^{2} - Φ^^{2}) / 5^{1/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, F_{k} = (Φ^{k} - Φ^^{k}) / 5^{1/2} and F_{k+1} = (Φ^{k+1} - Φ^^{k+1}) / 5^{1/2}. We will show that P(k+2) can be inferred from this. By definition, F_{k+2} = F_{k} + F_{k+1}. Based on the above assumption, we can substitute this for the right side of the equation:

F_{k+2} = (Φ^{k} - Φ^^{k}) / 5^{1/2} + (Φ^{k+1} - Φ^^{k+1}) / 5^{1/2}

With some algebraic manipulation,

F_{k+2} = ((Φ^{k} - Φ^^{k}) + (Φ^{k+1} - Φ^^{k+1})) / 5^{1/2}

F_{k+2} = (Φ^{k} + Φ^{k+1} - Φ^^{k} - Φ^^{k+1}) / 5^{1/2}

F_{k+2} = (Φ^{k}(1 + Φ) - Φ^^{k}(1 + Φ^) / 5^{1/2}

F_{k+2} = (Φ^{k}Φ^{2} - Φ^^{k}Φ^^{2} / 5^{1/2} ***

F_{k+2} = (Φ^{k+2} - Φ^^{k+2}) / 5^{1/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 + 5^{1/2})/2)^{2}

Φ^{2} = (1 + 2*5^{1/2} + 5) / 4

Φ^{2} = (6 + 2*5^{1/2}) / 4

Φ^{2} = (3 + 5^{1/2}) / 2

Φ^{2} = (2 + 1 + 5^{1/2}) / 2

Φ^{2} = 2/2 + (1 + 5^{1/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..."