9
9

More than 5 years have passed since last update.

# フィボナッチ数列の計算の高速化(Python版)

Last updated at Posted at 2016-02-16

フィボナッチ数列の計算の高速化(Ruby版)をPythonでもやってみました。

python
``````# 通常版
def fib1(n):
if n <= 1:
return n
n0, n1 = 0, 1
for _ in range(n):
n0, n1 = n1, n0+n1
return n0

# 高速版
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]]
``````

ちゃんとできてます。

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]
``````

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
``````

Rubyより10倍以上、速い！

ちなみに、numpy使うと、1476項(≒1.3e309)までしか計算できませんでした。

9
9
0

Register as a new user and use Qiita more conveniently

1. You get articles that match your needs
2. You can efficiently read back useful information
3. You can use dark theme
What you can do with signing up
9
9