Language Shootout

[Tim Peters]

[Bengt Richter]
> ...
> I just did a python recursive fib(100000) in
> just over 15 seconds, including startup and
> printing to screen, by my watch. (Not a typo,
> that was 100k). Of course, it might not be the
> usual recursive solution (see below)  ;-)
> ...
> It's a close translation of a scheme version I came
> up with about five years ago.  Dave Ulrich may remember.
> He pointed out that the next to last version wasn't
> doing what I thought. So he helped nudge it into being.
> Never did establish what wheel I was reinventing, but
> apparently there is something related.

Cute!  For "something related", see Knuth section 4.6.3 exercise 26.

Apart from tricks specific to Fibonacci numbers, a general "good thing to
know" is that an order-N linear recurrence can be viewed as mapping
N-vectors to N-vectors via multiplication by a fixed NxN matrix M.  N==2 in
this case, and if a,b,c are consecutive Fibonacci numbers then

    [b c] = [a b] * M

where "*" is matmult and M is

    0 1
    1 1

That's why your program wound up with expressions that look a lot like
2-term dot products:  they are <wink>!  Moving ahead k steps is essentially
equivalent to computing M**k, and that can be done in "the usual" way via
O(log(k)) 2x2 matmults.  This has practical application in, e.g., many kinds
of recurrence-based random-number generators, for "skipping ahead" a huge
number of terms very quickly.