On Fri, May 13, 2011 at 5:11 AM, rusi <rustompm...@gmail.com> wrote: > The tightest way I knew so far was this: > The 2x2 matrix > 0 1 > 1 1 > raised to the nth power gives the nth fibonacci number. [And then use > a logarithmic matrix mult] > Your version is probably tighter than this.
Oh, nice! I did it this way once: V = [0 1] M = [0 1] [1 1] fib(n) = (V * M ** n)[0] Since I viewed M as operating on V, it never occurred to me that multiplying by V is actually unnecessary, but it is obvious in retrospect. I think it's just a fortuitous coincidence that it works, since V sets up the base case and M describes the recursive case. For a FIbonacci sequence starting with any other pair of numbers, V would change, but M would not, and so V would no longer happen to be identical to the top row of M. Ian -- http://mail.python.org/mailman/listinfo/python-list
