root/hodgestar/PythonCode/Fibonacci/fibonacci_logn.py

#!/usr/bin/env python

import numpy

def fib(n):
    """Calculate the n'th Fibonacci number in O(log n) time.

       The method used is described at:
          http://davmac.org/davpage/algrthm/fibonacci.html
       and uses
         | 0 1 |^n == | fib(n-1) fib(n)   |
         | 1 1 |      | fib(n)   fib(n+1) |
       It breaks the n matrix muliplications by dividing n by 2
       contintually in order to build up the n'th power.
       """
    a = numpy.matrix([[0, 1], [1, 1]])
    x = numpy.matrix([[1, 0], [0, 1]])
    while n > 0:
        if n % 2 == 1:
            x = x*a
        a = a**2
        n = n >> 1
    return x[0,1]


if __name__ == "__main__":
    for n in [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]:
        print n, ":", fib(n)