重複の可能性:
Python での非常に大きな数の処理
フィボナッチ数を生成する python 関数があります。
def fib(n):
return ((1+math.sqrt(5))**n - (1-math.sqrt(5))**n)/(2**n*math.sqrt(5))
fib 関数番号を 700 までフィードできます。
OverflowError: (34, 'Numerical result out of range')
これを回避するには、 long のような特別なタイプを使用する必要がありますか?
問題は、値の計算に double を使用していて、double がオーバーフローしていることです。double は約 85 番目のフィボナッチ数に対してのみ正確な解を与えます。
高速で正確な計算が必要な場合は、より良い再帰関係に基づくアルゴリズムを使用し、python bignum 整数を使用することをお勧めします。
特に、次を使用できます。
fib(2*n) = fib(n)^2 + fib(n-1)^2
fib(2*n-1) = fib(n)*(2*fib(n-1)+fib(n))
または、同等の行列累乗式 (見苦しい書式設定を許してください)
[ F_n F_{n-1} ] [ 1 1 ] ^N
[ ] = [ ]
[ F_{n-1} F_{n-2} ] [ 1 0 ]
これらはどちらも、O(log(N))ではなく計算を必要とするアルゴリズムになりO(N)ます。
これが疑似コードの完全なソリューションです
double と明示的な数式を使用して計算を実行したい場合は、数式を微調整して、約 1500 番目のフィボナッチ数までオーバーフローせず、バージョンと同じ精度を維持する高速なものを提供できます。IIRCそれは次のとおりです。
def fib(n):
return round( ((1+math.sqrt(5))/2)**n / math.sqrt(5) )
エラーを特定するのは簡単です
>>> (1+math.sqrt(5))**700
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
OverflowError: (34, 'Numerical result out of range')
浮動小数点数の精度が十分でないため、この方法はうまく機能しません。
たとえば、ここ
>>> (1+math.sqrt(5))**600
1.024664165563927e+306
最初の15桁程度で作業しています。算術演算を行うと、残りの291はゼロとして扱われます
浮動小数点数の精度の問題の詳細については、ウィキペディアを参照してください
いつでもこのアプローチを試すことができます：
def fib(n, memo={0:0, 1:1}):
if n not in memo:
memo[n] = fib(n-1) + fib(n-2)
return memo[n]
print fib(800)
出力：
69283081864224717136290077681328518273399124385204820718966040597691435587278383112277161967532530675374170857404743017623467220361778016172106855838975759985190398725
実際にそのアルゴリズムを使用したい場合、および組み込みの制限を超えて作業したい場合はfloat、はい、別のタイプが必要です。
例外ではなく、おおよその答えを得たいだけなら、それは簡単です。箱から出して無限の範囲を得ることができます。ただし、丸め誤差も排除したい場合は、無限の精度を持つことはできません (無限の時間/空間が必要になります)。そのため、入力の範囲に必要な精度を計算する方法を知る必要があります。（これは読者の演習として残しておきます。）
標準ライブラリの種類decimal.Decimalだけで十分かもしれません。IEEE-854 標準に従って、任意精度の固定小数点または浮動小数点の 10 進数演算を提供します。十分な数学関数を提供しないために使用できない場合が多くありますが、必要なのは基本的な算術演算と だけで十分ですsqrt。fibまた、巨大な数の場合は遅くなる可能性がありますが、いくつかの 3 桁の数を計算したいだけであれば十分です。
が不十分な場合Decimal、多くのサードパーティ モジュールがあり、通常は bigfloat などの gmp/mpfr などの業界標準の C ライブラリをラップします。
無限の範囲を取得する方法は次のとおりですが、丸め誤差は組み込みの float とほぼ同じスケールになります。
>>> s5 = decimal.Decimal(5).sqrt()
>>> def fib(n):
... return ((1+s5)**n - (1-s5)**n)/(2**n*s5)
>>> fib(800)
Decimal('6.928308186422471713629008226E+166')
>>> int(fib(800))
69283081864224717136290082260000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000L
>>> s5 = bigfloat.sqrt(5)
>>> def fib(n):
... return ((1+s5)**n - (1-s5)**n)/(2**n*s5)
>>> fib(800)
BigFloat.exact('6.9283081864226567e+166', precision=53)
>>> int(fib(800))
69283081864226566841137772774650010139572747244991592044952506898599601083170460360533811597710072779197410943266632999194601974766803264653830633103719677469311107072L
しかし、これらはいずれも、完全に計算した場合に実際に得られる答えではないことに注意してください。丸め誤差で 24 桁を失いました。(値が異なる理由はbigfloat、基数 2、基数 10 で丸められているためですdecimal。)
それを修正するには、より精度が必要です。すべてのライブラリは、精度を変更する何らかの方法を提供します。bigfloatほとんどのオプションよりも便利なオプションがありますが、面倒すぎるものはありません。
>>> decimal.getcontext().prec = 300
>>> s5 = decimal.Decimal(5).sqrt()
>>> def fib(n):
... return ((1+s5)**n - (1-s5)**n)/(2**n*s5)
>>> fib(800)
69283081864224717136290077681328518273399124385204820718966040597691435587278383112277161967532530675374170857404743017623467220361778016172106855838975759985190398725.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000048
>>> def fibp(n, p):
... with bigfloat.precision(p):
... s5 = bigfloat.sqrt(5)
... return ((1+s5)**n - (1-s5)**n)/(2**n*s5)
>>> fibp(800, 125)
BigFloat.exact('6.92830818642247171362900776814484912138e+166', precision=125)
>>> int(fibp(800, 125))
69283081864224717136290077681448491213794574774712670552070914552025662674717073354503451578576268674564384721027806323979200718479461097490537109958812524476157132800L