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

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)) / 2def 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 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

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 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