Pure Python Fibonacci Numbers

A while back, I came across this post, in which the author implements a couple of different algorithms to generate Fibonacci numbers in Python. What he finally ends up with is an algorithm that essentially does matrix exponentiation by repeated squaring, and it runs fairly fast.

I thought it’d be fun to see if I could improve upon his work, so I did some searching on Google for algorithms to use. The fastest one I found was from this paper. (Warning: PDF format.) If the download doesn’t work, you can always dig up the print version. Here’s the full citation:

Takahashi, Daisuke. “A fast algorithm for computing large Fibonacci numbers.” Information Processing Letters 75.6 (2000): 243-246.

Though I haven’t constructed a proof yet, it seems that this algorithm is faster than the one in the original post by at least a factor of 5, and I suspect it is asymptotically faster.

Code

Without further ado, here is Takahashi’s algorithm rendered into Python code:

from math import log, floor

def fib (n):
    if n == 0: return 0
    elif n == 1: return 1
    elif n == 2: return 1
    else:
        F = 1
        L = 1
        sign = -1
        mask = 2 ** (int(floor (log (n,2)))-1)
        for i in xrange (1, int(floor (log(n,2)))):
            temp = F ** 2
            F = (F + L) / 2
            F = 2 * F ** 2 - 3 * temp - 2 * sign
            L = 5 * temp + 2 * sign
            sign = 1
            if n & mask:
                temp = F
                F = (F + L) / 2
                L = F + 2 * temp
                sign = -1
            mask = mask / 2
        if n & mask == 0:
            F = F * L
        else:
            F = (F + L) / 2
            F = F * L - sign
        return F

Timings

On my machine (an AMD Athlon 64 x2 @ 1.70 GHz, running Python 2.5 on Ubuntu Hardy), I get the following timing results:

Timing results in seconds for various n by algorithm

n	Takahashi’s algorithm	Matrix exponentiation
220	0.435	2.072
220-1	0.439	2.101
222	3.458	19.272
222-1	3.366	18.866
224	29.741	170.194
224-1	29.588	173.712

As you can see, Takahashi’s algorithm appears to be approximately 5x faster than matrix exponentiation by repeated squaring. However, I have not yet worked out the asymptotic complexity of the algorithm.