4

O(log(n)) 時間と呼び出しで実行する必要がある行列累乗アルゴリズムから派生したアルゴリズムを使用して、高速倍加を介してかなり標準的なフィボナッチ関数を作成しましたが、約 1,000,000 以上で失速します。約25回の通話。

コード：

"""
O(log(n)) time fibonacci algorithm using fast doubling derived from the matrix
squaring algorithm for the same thing.
"""

def fibonacci(num):
    "O(log(n)) implementation of fibonacci using fast doubling."
    if num >= 0:
        return fib_helper(num)[0]

def fib_helper(num):
    "Helper function for fibonacci()."
    if num == 0:
        return (0, 1)
    elif num == 1:
        return (1, 1)
    else:
        f_k, f_k_1 = fib_helper(num // 2)
        f_k_even = f_k * (2 * f_k_1 - f_k)
        f_k_odd = f_k_1 * f_k_1 + f_k * f_k
        return (f_k_even, f_k_odd) if num % 2 == 0 else (f_k_odd, f_k_even +
                f_k_odd)

このコードは、fib_helper への log(n) 呼び出しと、fibonacci への 1 つの呼び出しのみを生成する必要があります。1,000,000 を超える数値の場合は、失速して戻りません。

関数呼び出しをカウントするための基本的なデコレータを実装しようとしましたが、2^32 に対して 32 回の呼び出ししか実行していないことがわかりますが、最後に停止します。

これが大きな整数で停止するのはなぜですか?

4

2 に答える 2

9

このようなコードを実行してみてください

print "calculating fib(1000000)"
res = fib(1000000)
print "displaying the result..."
print res

問題は、それfib(1000000)が非常に大きな数であることです (>10 200000 )。すべてがバイナリで行われるため、コンピューターはこれらの数値を非常に迅速に処理できます。

数値を表示しようとすると、基数 10 に変換する必要があります。これには非常に時間がかかります。

16 進数への変換ははるかに簡単です。ビットを 4 つにグループ化する必要があるだけなので、

print hex(res)

すぐに物を吐き始めます

于 2013-10-31T03:33:12.443 に答える
3

私のdecimalコメントはどうやら不可解だったので、参考までに ;--)、コードは次のとおりです。

import decimal
from decimal import Decimal as D
DO = D(0)
D1 = D(1)

def fibonacci(num):
    from math import log10
    if num >= 0:
        ndigits = int(log10(1.62) * num + 100)
        decimal.getcontext().prec = ndigits
        decimal.getcontext().Emax = ndigits
        return fib_helper(num)[0]

def fib_helper(num):
    if num == 0:
        return (D0, D1)
    elif num == 1:
        return (D1, D1)

の残りの部分fib_helper()は変更されていません (元のメッセージを参照してください)。Python 3 ではdecimalC で実装されており、計算時間はネイティブ (バイナリ) 整数を使用する場合と同等です。しかしポイントは、10 進文字列への出力変換の時間です。これは、大きなボトルネックではなく、ランタイムの些細な部分になります。

たとえば、fibonacci(100000000)(1 億) はこのボックスで約 30 秒かかりますが、その後は次のようになります。

>>> from time import clock as now # on this box, `clock()` is wall-clock time
>>> if 1:
...    t = now()
...    print(len(str(x)))
...    print(now()-t)
...
20898764
0.10466078789343337

つまり、10 分の 1 秒で 2000 万以上の 10 進数の文字列が生成されます。引数 10 億の場合、208,987,640 桁の 10 進数文字列を生成するのに約 0.9 秒かかります。10 進数の桁数は明らかに線形です。

注:は、10 進浮動小数点および固定小数点の計算をdecimal実際に目指しています。高精度の整数計算には問題なく使用できますが、必要な桁数と最大指数を事前に指定する必要があります。「無制限」モードはありません。上記のコードでは、fibonacci(n)にほぼ等しい を使用してい1.618**nます。

于 2013-10-31T05:23:45.633 に答える