A Faster, Cheaper Fibonacci Definition

The Fibonacci sequence is one of the best-known number sequences:

  1. 1
  2. 1
  3. 2
  4. 3
  5. 5
  6. 8
  7. 13
  8. 21…

Each Fibonacci number above 1 is defined as the sum of the previous two Fibonacci numbers:

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)

Just for fun, here’s another way to specify the Fibonacci sequence. It takes fewer calculations, especially for large numbers. The math is basic algebra substitutions. This could be old news — if you’ve seen this before, I’d love to hear from you.

Deriving the new Fibonacci definition

Before we begin, let’s notate F(n) as Fn, and F(n-1) as Fn1 — it’ll make everything tidier.

That Fn1 + Fn2 part, to me, always begged for substitution. Fn1 should equal Fn2 + Fn3, right? What if we re-write Fn in terms of Fn1‘s definition? What might that lead to?

Fn = Fn1 + Fn2
Fn1 = Fn2 + Fn3
Fn = Fn2 + Fn2 + Fn3
Fn = 2Fn2 + Fn3, as long as n > 2.

Pretty basic: substitute the definition for Fn1 back into the definition for Fn, and simplify. We can keep going:

Fn2 = Fn3 + Fn4
Fn = 2Fn2 + Fn3, from above
Fn = (2Fn3 + 2Fn4) + Fn3
Fn = 3Fn3 + 2Fn4, for n > 3

…and then:

Fn3 = Fn4 + Fn5
Fn = (3Fn4 + 3Fn5) + 2Fn4
Fn = 5Fn4 + 3Fn5, for n > 4

…and again:

Fn4 = Fn5 + Fn6
Fn = (5Fn5 + 5Fn6) + 3Fn5
Fn = 8Fn5 + 5Fn6, for n > 5

…just one more time:

Fn5 = Fn6 + Fn7
Fn = 8Fn6 + 8Fn7 + 5Fn6
Fn = 13Fn6 + 8Fn7, for n > 6

See the pattern? Look at the coefficients:

Fn = 2Fn2 + 1Fn3, for n > 2
Fn = 3Fn3 + 2Fn4, for n > 3
Fn = 5Fn4 + 3Fn5, for n > 4
Fn = 8Fn5 + 5Fn6, for n > 5
Fn = 13Fn6 + 8Fn7, for n > 6

They’re the Fibonacci sequence starting up. Do the math, and you’ll see that the next few steps follow along. What if we replace the coefficients with their Fibonacci indexes? If F(6) = 8 and F(7) = 13, we can rewrite 13Fn6 + 8Fn7 as F(7) Fn6 + F(6) Fn7. Let’s carry that out:

Fn = F(3) Fn2 + F(2) Fn3, for n > 2
Fn = F(4) Fn3 + F(3) Fn4, for n > 3
Fn = F(5) Fn4 + F(4) Fn5, for n > 4
Fn = F(6) Fn5 + F(5) Fn6, for n > 5
Fn = F(7) Fn6 + F(6) Fn7, for n > 6

Let’s quickly verify this. We know from the original definition that F(10) = 55, so let’s see whether these new versions agree. (I’ll only test the first and last versions, to save space, but you can verify as many as you like.)

F(10) = 55 = F(3) Fn2 + F(2) Fn3
F(10) = 55 = F(3) F(8) + F(2) F(7)
F(10) = 55 = 2 * 21 + 1 * 13

F(10) = 55 = F(7) Fn6 + F(6) Fn7
F(10) = 55 = F(7) F(4) + F(6) F(3)
F(10) = 55 = 13 * 3 + 8 * 2

They both pass. More generally:

Fn = F(x) Fny + F(y) Fnx, for n > x, and y = x – 1

It’s not terribly wordier than the original definition, Fn = Fn1 + Fn2, for n > 2.

Putting this to use

A nice property of this new version is that it lets us skip some steps. If we’re calculating F(1000) with the traditional definition, we have to calculate each Fibonacci along the way; but now, we can set x = 500, and skip down to the neighborhood of F(500):

F(1000) = F(500) * F(501) + F(499) * F(500)

We can continue to skip down to about n/2, decreasing the amount of calculations we need to do.

Just for fun, I implemented both fib_orig and fib_new in ruby: here’s the file. I memoized the methods, for two reasons:

  1. It’s clearly much faster, and it’s simple to do.
  2. It lets us see exactly which Fibonacci numbers were calculated.

I put the two methods in a test case, with four test methods.

The first test ensures that the new equation matches the old. Unfortunately, I could only reach 6000 with the fib_orig, before I ran out of stack space.

The second test benchmarks the two versions. It reports the memo array size (6000 for fib_orig, as expected, and 40 for fib_new — 99.3% fewer calculations).

When fib_orig ran out of stack space so quickly, I wondered how far I could take the new version (which should recurse many fewer times). So in the third test, I benchmarked it with progressively bigger numbers. It starts to slow down around the millionth Fibonacci number: it completes in about 12 seconds on my machine. I suspect it’s spending the extra time array-seeking at that point, since the array gets pretty sparse — the last few non-null array indexes are: 125001 249999 250000 250001 499999 500000 500001 1000000. Maybe I’ll try a hash…

The fourth test is a bit of extra-credit, and a sanity check. Fn / F(n+1) approaches the golden ratio, 1.61803398874…, as N approaches infinity. So I calculated F(1401) / F(1400) with fib_new, and it’s accurate to 15 decimal points, rounding the last one, which seems to be the limit of precision on my WinXP machine. I tried using higher Fibonacci numbers, but was warned that I was exceeding the range of ruby’s floating point numbers. Here’s the output of that test:

 actual golden ratio: 1.6180339887498948482
approx. golden ratio: 1.618033988749895
precision-level test: 0.333333333333333

So it seems the new approach is correct, faster, uses less space, and is still pretty elegant. Who knows whether this will ever come in handy, but at least it was fun to do.

F(n) = F(x) F(n-y) + F(y) F(n-x), for n > x, and y = x – 1

Advertisements