Language Shootout

[David C. Ullrich]

On Tue, 10 Jul 2001 01:18:16 -0400, "Tim Peters" <tim.one at home.com>
wrote:

>[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.

Yup. Many years ago one of my favorite applications in linear algebra
was showing the kids how to compute M**k here by first diagonalizing
M. A smaller number of years ago I realized how wrong that was, from
a computational standpoint. Never got a chance to tell the kids
I'd lied - probably they're all lurking here so now it's ok.

(Took a minute to find fib.py just now, because it was filed 
under "MatrixTypes". I calculate fib(100000) in 1.7 
seconds this way; for comparison, str(fib(100000)) takes 
8.0 seconds.)



David C. Ullrich
**********************************
About this published paper that has to do with some agreements with some of the 
things that I say, I heard about it at least a couple months ago, although it might 
have been within the last two months. (Ross Finlayson, sci.math 7-6-01)