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