19 October 2007

Fibonacci tattoo!

From Pink Haired Girl, who I apparently share several mutual friends with: a tattoo to generate the Fibonacci sequence, in Scheme.

There are faster algorithms to generated the Fibonacci sequence, but they obscure the recursive definition; her tattoo follows the simple recursive definition Fn = Fn-1 + Fn-2, which takes O(n) arithmetic operations to compute Fn. Wikipedia's article on Fibonacci numbers gives an identity
F2n+k = Fk Fn+12 + 2Fk-1Fn+1Fn + Fk-2Fn2

Now, note that we get F-2 = -1 , F-1 = 1 , F0 = 0 by running the recursion backwards. Letting k=1 gives

F2n+1 = (2Fn+1 - Fn) Fn

and letting k=2 gives
F2n+2 = Fn+12 + 2Fn+1Fn.
Letting m+1 = n, we get
F2m = Fm2 + 2FmFm-1
= Fm(Fm + 2Fm-1)
= Fm(Fm+1 + Fm-1).

Thus we can express Fn in terms of Fibonacci numbers of indices around n/2, and thus find Fibonacci numbers in logarithmic time... but that obscures the central fact about these numbers, which is the recursion that produces them. (There are probably other ways to arrange those identities that give more efficient algorithms than the one I'm alluding to, but I didn't try that hard.) There are also identities for Fn in terms of Fibonacci numbers of index around n/3, for example -- see Wikipedia -- which could be even faster.


Pseudonym said...

You can prove most of these identities by noting that the matrix:

[ 1 1 ]
[ 1 0 ]

raised to an integral power generates the Fibonacci numbers. You can then prove statements about F_2m by squaring matrices.

David Glasser said...

she totally hung out in our hammock tree