我的斐波那契生成器给出了不正确的结果

Question

我正在尝试开发一个函数，该函数接受一个值n并输出nth斐波那契数列中的数字。我有一个循环函数，它的工作原理似乎如下：

def fibonacci_v1(n):

    a = b = 1

    for _ in range(1, n):

        a, b = b, a + b

    return a

我正在尝试开发一个使用比奈公式的版本，如下所述：

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()文档没有说明其准确性级别...这是我的功能的问题还是有其他问题？math.sqrt

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

for x in range(1, 73):

    print(fibonacci_v1(x))

    print(fibonacci_v2(x))

Answer 1

如果您追求速度和准确性，请改用 Python 生成器。下面在 5 毫秒内计算前 10,000 个斐波那契数，然后在约 17 秒内计算（但不存储） F 0到 F 999,999 ，然后打印 F 1,000,000中的位数。由于它使用整数数学而不是浮点，因此速度更快并且没有任何错误。import timedef fib():    a,b = 0,1    while True:        yield a        a,b = b,a+bs = 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.00522112846374511717.795812129974365208988

Answer 2

math.sqrt这与浮点数在 python 中的表示方式关系不大。默认实现如今（2000 年 11 月）几乎所有机器都使用 IEEE-754 浮点算法，并且几乎所有平台都将 Python 浮点映射到 IEEE-754“双精度”。您可以使用十进制模块来解决这种不准确性与基于硬件的二进制浮点不同，十进制模块具有用户可更改的精度如果您需要更准确的表示，您可以使用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 aPhi = (1 + Decimal(5).sqrt()) / 2# V2 implementation using the decimal moduledef 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=806515533049393n=74: v1=1304969544928657, v2=1304969544928657n=75: v1=2111485077978050, v2=2111485077978050n=76: v1=3416454622906707, v2=3416454622906707n=77: v1=5527939700884757, v2=5527939700884757n=78: v1=8944394323791464, v2=8944394323791464n=79: v1=14472334024676221, v2=14472334024676221