我的 Fibonacci 生成器给出了错误的结果

Question

我正在尝试处理一个接受值 n 并输出斐波那契数列中的 nth 数字的函数。我有一个循环函数，它看起来像这样工作：

def fibonacci_v1(n):
    a = b = 1
    for _ in range(1, n):
        a, b = b, a + b
    return a

我正在尝试开发一个使用 Binet 公式的版本 here:

Phi = (1 + math.sqrt(5)) / 2


def fibonacci_v2(n):
    c = pow(Phi, n)
    return math.floor((c - pow(-1, n) / c) / math.sqrt(5))

这似乎适用于 n 的低值，但在输入高于 72 的数字时中断......我怀疑这与 math.sqrt() 的准确性有关功能，但文档 here 没有说明其准确性级别......这是 math.sqrt 的问题还是我的功能有其他问题？

出于测试目的，我使用了这个 for 循环：

for x in range(1, 73):
    print(fibonacci_v1(x))
    print(fibonacci_v2(x))

Answer 1

这与 math.sqrt 的关系不如 floating-point 数字在 python 中的表示方式。默认实现

Almost all machines today (November 2000) use IEEE-754 floating point arithmetic, and almost all platforms map Python floats to IEEE-754 “double precision”.

您可以在此处阅读有关 limitation of in-built floating-point 的更多信息。

您可以使用 decimal 模块来解决这个错误

Unlike hardware based binary floating point, the decimal module has a user alterable precision

如果您需要更准确的表示，您可以使用 getContext() 来调整精度

from decimal import *
# Your Existing v1 implementation 
def fibonacci_v1(n):
    a = b = 1
    for _ in range(1, n):
        a, b = b, a + b
    return a

Phi = (1 + Decimal(5).sqrt()) / 2
# V2 implementation using the decimal module
def fibonacci_v2(n):
    getcontext().prec = 4096 # You need to tweak this number based on your precision requirements 
    c = Decimal(Phi) ** n
    fib = (c - (Decimal(-1)** n) / c) / Decimal(5).sqrt()
    return fib.quantize(Decimal('1.'), rounding=ROUND_UP)


for x in range(73, 80):
    print(f"n={x}: v1={fibonacci_v1(x)}, v2={fibonacci_v2(x)}")

输出：

n=73: v1=806515533049393, v2=806515533049393
n=74: v1=1304969544928657, v2=1304969544928657
n=75: v1=2111485077978050, v2=2111485077978050
n=76: v1=3416454622906707, v2=3416454622906707
n=77: v1=5527939700884757, v2=5527939700884757
n=78: v1=8944394323791464, v2=8944394323791464
n=79: v1=14472334024676221, v2=14472334024676221

Answer 2

如果您追求速度和准确性，请改用 Python 生成器。下面在 5 毫秒内计算前 10,000 个斐波那契数，然后在 ~17 秒内计算（但不存储）F₀ 到 F_999,999，并且然后打印 F_1,000,000 中的位数。由于它使用整数数学而不是浮点数，因此速度更快并且没有错误。

import time

def fib():
    a,b = 0,1
    while True:
        yield a
        a,b = b,a+b

s = time.time()
it = fib()
f = [next(it) for _ in range(10000)] # list of F[0] - f[9999]
print(time.time() - s)

s = time.time()
it = fib()
for _ in range(1000000): # Skip over F[0]-F[999999]
    next(it)
print(time.time() - s)
print(len(str(next(it)))) # display no. of digits in F[1000000].

f = [next(it) for _ in range(10000)]
it = fib()
for _ in range(1000000): # Skip over F[0]-F[999999]
    next(it)
print(len(str(next(it)))) # display no. of digits in F[1000000].

输出：

0.005221128463745117
17.795812129974365
208988

我的 Fibonacci 生成器给出了错误的结果

My Fibonacci generator is giving incorrect results

python

fibonacci

python-3.x