5

(a) 線形アプローチと (b)この式を使用して、n 番目のフィボナッチ数を計算しています。

Python コード:

'Different implementations for computing the n-th fibonacci number'

def lfib(n):
    'Find the n-th fibonacci number iteratively'
    a, b = 0, 1
    for i in range(n):
        a, b = b, a + b
    return a

def efib(n):
    'Compute the n-th fibonacci number using the formulae'
    from math import sqrt, floor
    x = (1 + sqrt(5))/2
    return long(floor((x**n)/sqrt(5) + 0.5))


if __name__ == '__main__':
  for i in range(60,80):
    if lfib(i) != efib(i):
      print i, "lfib:", lfib(i)
      print "   efib:", efib(i)

n > 71 の場合、2 つの関数が異なる値を返すことがわかります。

これは、efib() に含まれる浮動小数点演算によるものですか? もしそうなら、行列形式を使用して数を計算することをお勧めしますか?

4

3 に答える 3

11

あなたは確かに丸め誤差を見ています。

行列形式は、より正確ではるかに高速なアルゴリズムです。Literateprograms.orgには優れた実装がリストされていますが、ルーカス数に基づく次のアルゴリズムもリストされています。

def powLF(n):
    if n == 1:     return (1, 1)
    L, F = powLF(n//2)
    L, F = (L**2 + 5*F**2) >> 1, L*F
    if n & 1:
        return ((L + 5*F)>>1, (L + F) >>1)
    else:
        return (L, F)

def fib(n):
    if n & 1:
        return powLF(n)[1]
    else:
        L, F = powLF(n // 2)
        return L * F

マトリックス アプローチの適切な分析については、アルゴリズムに関する MIT オープン コースウェア コースの講義 3 を参照してください。

上記のアルゴリズムと行列のアプローチの両方に、丸めの問題がなくても、使用した単純な再帰的な二乗法と同じように、Θ(lg n) の複雑さがあります。ルーカス数アプローチは定数コストが最も低く、より高速なアルゴリズムになります (行列アプローチの約 2 倍の速さ)。

>>> timeit.timeit('fib(1000)', 'from __main__ import fibM as fib', number=10000)
0.40711593627929688
>>> timeit.timeit('fib(1000)', 'from __main__ import fibL as fib', number=10000)
0.20211100578308105
于 2012-08-24T06:01:22.040 に答える
3

これは、efib() に含まれる浮動小数点演算によるものですか?

はい、そうです。efibあなたの中にある

>>> log(x**72)/log(2)
49.98541778140445

Python float はx86-64 ハードウェアで約 53 ビットの精度を持っているため、エッジの近くで実行しています。

于 2012-08-24T06:05:13.197 に答える