Fibonacci numbers, with an one-liner in Python 3?

I recently learned about using matrix multiplication to generate Fibonacci numbers, which was pretty cool. You take a base matrix:

[1, 1]
[1, 0]

and multiply it by itself N times to get:

[F(N+1), F(N)]
[F(N), F(N-1)]

This morning, doodling in the steam on the shower wall, I realized that you could cut the running time in half by starting with the second matrix, and multiplying it by itself N/2 times, then using N to pick an index from the first row/column.

With a little squeezing, I got it down to one line:

import numpy

def mm_fib(n):
    return (numpy.matrix([[2,1],[1,1]])**(n//2))[0,(n+1)%2]

>>> [mm_fib(i) for i in range(20)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]

fib = lambda n:reduce(lambda x,n:[x[1],x[0]+x[1]], range(n),[0,1])[0]

(this maintains a tuple mapped from [a,b] to [b,a+b], initialized to [0,1], iterated N times, then takes the first tuple element)

>>> fib(1000)
43466557686937456435688527675040625802564660517371780402481729089536555417949051
89040387984007925516929592259308032263477520968962323987332247116164299644090653
3187938298969649928516003704476137795166849228875L

(note that in this numbering, fib(0) = 0, fib(1) = 1, fib(2) = 1, fib(3) = 2, etc.)

(also note: reduce is a builtin in Python 2.7 but not in Python 3; you'd need to execute from functools import reduce in Python 3.)


A rarely seen trick is that a lambda function can refer to itself recursively:

fib = lambda n: n if n < 2 else fib(n-1) + fib(n-2)

By the way, it's rarely seen because it's confusing, and in this case it is also inefficient. It's much better to write it on multiple lines:

def fibs():
    a = 0
    b = 1
    while True:
        yield a
        a, b = b, a + b