我的斐波那契发电机给出了错误的结果

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的数字时会中断。。。我怀疑这与数学的准确性有关。sqrt（）函数，但此处的文档没有说明其精度级别。。。这是否是数学的问题。sqrt或者我的函数是否有其他问题？

出于测试目的，我使用以下For循环：

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

Answer 1

如果您希望提高速度和准确性，请改用Python生成器。下面在5毫秒内计算前10000个斐波那契数，然后在~17s内计算（但不存储）F₀到F₉₉₉₉₉₉，然后打印F_1000000中的位数。因为它使用整数数学而不是浮点，所以速度更快，并且没有不准确的地方。

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

Answer 2

这与数学的关系不大。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 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