This library provides a decorator that disassembles the function's bytecode, checks if it calculates linear recurrences, and tries to reduce the algorithm's time complexity from O(n) to O(log n) using the fast matrix exponentiation.

Detailed description: Russian, English.

Inspired by the Alexander Skidanov's optimizing interpreter.

Suppose we want to calculate the ten millionth Fibonacci number in Python. The function with a trivial algorithm is rather slow:

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

result = fib(10 ** 7)

# Time: 25 min 31 sec

But if we apply the optimizing decorator, the function will give you the answer much faster:

from cpmoptimize import cpmoptimize

@cpmoptimize()
def fib(n):
    a = 0
    b = 1
    for i in xrange(n):
        a, b = b, a + b
    return a

result = fib(10 ** 7)

# Time: 18 sec (85x faster)

You can install the stable version of the library using pip:

sudo pip install cpmoptimize

Or install a previously downloaded and extracted package:

sudo python setup.py install

Copyright (c) 2014, 2015 Alexander Borzunov