Crazy optimization

fib.py

# This was a relevation for me:
# <http://kukuruku.co/hub/algorithms/automatic-algorithms-optimization-via-fast-matrix-exponentiation.html>

def fib(n):
    u_n = 1
    u_n1 = 0
    for i in xrange(1, n):
        u_n1, u_n = u_n, (u_n1 + u_n)
    return u_n

class Matrix22(object):

    def __init__(self, a, b, c, d):
        """
        | a  b |
        | c  d |
        """
        self.a = a
        self.b = b
        self.d = d
        self.c = c

    def __mul__(self, other):
        if isinstance(other, Matrix22):
            a = self.a * other.a + self.b * other.c
            b = self.a * other.b + self.b * other.d
            c = self.c * other.a + self.d * other.c
            d = self.c * other.b + self.d * other.d
            return Matrix22(a, b, c, d)
        else:
            return NotImplemented

    def __pow__(self, other):
        if isinstance(other, int):
            if other == 0:
                return Matrix22(1, 0, 1, 0)
            elif other == 1:
                return Matrix22(self.a, self.b, self.c, self.d)
            elif (other % 2) == 0:
                return (self * self) ** (other / 2)
            else:
                return self * ((self * self) ** ((other - 1)/2))
        else:
            return NotImplemented


def fibm(n):
    m = Matrix22(1, 1, 1, 0) ** n
    return m.c

import cProfile

cProfile.run('fib(5000000)')
cProfile.run('fibm(5000000)')

#         3 function calls in 202.173 seconds
#
#   Ordered by: standard name
#
#   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
#        1    0.000    0.000  202.173  202.173 <string>:1(<module>)
#        1  202.173  202.173  202.173  202.173 fib.py:1(fib)
#        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
#
#
#         138 function calls (116 primitive calls) in 5.196 seconds
#
#   Ordered by: standard name
#
#   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
#        1    0.000    0.000    5.196    5.196 <string>:1(<module>)
#       31    0.000    0.000    0.000    0.000 fib.py:10(__init__)
#       29    5.195    0.179    5.195    0.179 fib.py:20(__mul__)
#     23/1    0.001    0.000    5.196    5.196 fib.py:30(__pow__)
#        1    0.000    0.000    5.196    5.196 fib.py:44(fibm)
#       52    0.000    0.000    0.000    0.000 {isinstance}
#        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}