Python フィボナッチ数列

Question

Pythonにおいてフィボナッチ数列のプログラミングを書いた際に、公式にそのまま入れる方と行列の積で解くものと、何故か公式の方はOverflowしてしまいます。この理由を教えていただけると幸いです。

import math
import time
def fib_general_term(n):
    return math.floor((1/math.sqrt(5))*(((1+math.sqrt(5))/2)**n-((1-math.sqrt(5))/2)**n))

start = time.time()
print(fib_general_term(40))
try:
    fib_general_term(30000)
except OverflowError:
    print("OverflowError")
process_time = time.time() - start
print("Time :" + str(process_time) + '[s]')

def make_matrix(row_len,column_len):
    matrix_c = [[0]*column_len for _ in range(row_len)]
    return matrix_c

def matrix_mul(a,b):
    c = make_matrix(len(a),len(b[0]))
    for i in range(len(a)):
        for k in range(len(b)):
            for j in range(len(b[0])):
                c[i][j] +=  a[i][k] * b[k][j]
    return c

def matrix_pow(a,n):
    b = make_matrix(len(a), len(a))
    for i in range(len(a)):
        b[i][i] = 1
    while(n>0):
        if(n & 1):
            b = matrix_mul(a,b)
        else:
            pass
        a = matrix_mul(a,a)
        n >>= 1
    return b

def fib_matrix(n):
    if n == 0:
        return 0
    a = make_matrix(2,2)
    a[0][0] = 1 
    a[0][1] = 1
    a[1][0] = 1 
    a[1][1] = 0
    a = matrix_pow(a, n)
    return a[1][0]

start = time.time()
print(fib_matrix(40))
fib_matrix(30000)
process_time = time.time() - start
print("Time :" + str(process_time) + '[s]')

102334155
OverflowError
Time :0.00012803077697753906[s]
102334155
Time :0.002933025360107422[s]

Answer 1

普通にfloat型が桁あふれしただけです。
ほとんどの環境においてPython3.xのfloat型は64bitの倍精度浮動小数点数(C言語のdouble)で実装されていて、その最大値は1.79769e+308です。
((1+√5)/2)^nだとn=1470あたりが限度ですね。

ちなみにint型は多倍長整数なので、整数で演算している限り桁数に制限はないです。あまり大きいと計算が終わりませんが。

追記
無理数を計算してるので桁が大きくなると誤差がでます。この例だとn=100くらいまでしか正しく計算できないみたいです。

Answer 2

この辺の話では？
Pythonの再帰回数の上限を確認・変更

Comments

[kairi003]

再帰してないので関係無いと思います。

[退会済みユーザー]

あーほんとだ＾＾；
指摘ありがとう。