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.
Update (Feb 2022): This library was created in 2014 and only supports Python 2.6-2.7 (not Python 3). I don't plan to upgrade it myself but I'd be happy to help anyone willing to do that (this is a good exercise to understand how it works). If you're interested, please open an issue.
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 secBut 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 cpmoptimizeOr install a previously downloaded and extracted package:
sudo python setup.py installCopyright (c) 2014, 2015 Alexander Borzunov