The Fibonacci sequence is one of the best-known number sequences:
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
Fn3 = Fn4 + Fn5 Fn = (3Fn4 + 3Fn5) + 2Fn4 Fn = 5Fn4 + 3Fn5, for n > 4
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.
- It's clearly much faster, and it's simple to do.
- 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).
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