q-matrix <3

fastfib.py

import cProfile


def fibonacci(n):
    if n < 0:
        raise ValueError("Negative arguments not implemented")
    print _fib(n)[0]


def _fib(n):
    if n == 0:
        return (0, 1)
    else:
        a, b = _fib(n // 2)
        c = a * (b * 2 - a)
        d = a * a + b * b
        if n % 2 == 0:
            return (c, d)
        else:
            return (d, c + d)


cProfile.run('fibonacci(2000)')

$ python fastfibonacci.py
4224696333392304878706725602341482782579852840250681098010280137314308584370130707224123599639141511088446087538909603607640194711643596029271983312598737326253555802606991585915229492453904998722256795316982874482472992263901833716778060607011615497886719879858311468870876264597369086722884023654422295243347964480139515349562972087652656069529806499841977448720155612802665404554171717881930324025204312082516817125
         15 function calls (4 primitive calls) in 0.000 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 <string>:1(<module>)
     12/1    0.000    0.000    0.000    0.000 fastfibonacci.py:10(_fib)
        1    0.000    0.000    0.000    0.000 fastfibonacci.py:4(fibonacci)
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}