Faster Fibonacci sequence calculations (Python version)

I also tried Speeding up Fibonacci sequence calculation (Ruby version) in Python.

The definitions are the same.

python


#normal version
def fib1(n):
    if n <= 1:
        return n
    n0, n1 = 0, 1
    for _ in range(n):
        n0, n1 = n1, n0+n1
    return n0

#High speed version
def fib2(n):
    if n <= 1:
        return n
    result = [1, 0, 0, 1]
    matrix = [1, 1, 1, 0]
    while n > 0:
        if n % 2:
            result = mul(matrix, result)
        matrix = mul(matrix, matrix)
        n //= 2
    return result[2]

def mul(a, b):
    return [a[0]*b[0] + a[1]*b[2],
            a[0]*b[1] + a[1]*b[3],
            a[2]*b[0] + a[3]*b[2],
            a[2]*b[1] + a[3]*b[3]]

I can do it properly.

python


print([fib1(i) for i in range(11)])
print([fib2(i) for i in range(11)])
>>>
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

measurement of time.

python


%timeit fib1(100000)
%timeit fib2(100000)
%timeit fib1(1000000)
%timeit fib2(1000000)
>>>
10 loops, best of 3: 75.7 ms per loop
100 loops, best of 3: 10.6 ms per loop
1 loops, best of 3: 6.9 s per loop
1 loops, best of 3: 374 ms per loop

More than 10 times faster than Ruby!

By the way, using numpy, I could only calculate up to 1476 (≒ 1.3e309).

that's all

Recommended Posts

Faster Fibonacci sequence calculations (Python version)
Fibonacci sequence using Python
Algorithm learned with Python 5th: Fibonacci sequence
I tried recursion with Python ② (Fibonacci sequence)
PYTHON2.7 64bit version
Python fast fibonacci
Implementation of Fibonacci sequence
Python version switching (pyenv)
Check version with python
[2020 version] Let Python do all the tax and take-home calculations
Memoization recursion and dynamic programming known by Python Fibonacci sequence
[Python] Use a string sequence
Breadth-first search / bidirectional search (Python version)
Petit stray Python version output
Version upgrade of python Anaconda
Python version does not switch
Check OpenSSL version of python 2.6
Fibonacci and prime implementations (python)
Python release cycle is faster!
Faster loading of Python images
Introduction to Python (Python version APG4b)
How to change Python version
Specify python version with virtualenv
tesseract-OCR for Python [Japanese version]
Error resolution python version check