python - 使用比奈公式在 python 中获取较大斐波那契数的准确值

Question

我正在学习 itertools，并试图测试用 python 实现的 Binet 公式的准确性。使用 itertools 的原因是我假设这将需要大量迭代，并且只有在大量迭代之后才会出现差异。

from math import sqrt
import itertools
#fibonacci function 2
def fib1():
    n = -1
    while True:
        n += 1
        yield int(((1+sqrt(5))**n-(1-sqrt(5))**n)/(2**n*sqrt(5)))

#fibonacci function 1
def fib2():
    a,b = 0,1
    while True:
        yield a
        a, b = b, a + b


r=itertools.dropwhile(lambda x: x[0]==x[1],itertools.zip_longest(fib1(),fib2()))
for item in itertools.islice(r,0,1):
    print(item)

输出:

(498454011879265, 498454011879264)

在使用int()之前，我在fib1()中使用了round()，结果是

(308061521170130, 308061521170129)

可以采取哪些措施来提高我的比奈公式实现的准确性？

Answer 1

十进制 是正确的选择。顺便说一句，最后，当您可以执行 next(r) 时，没有必要将 islice 减 1:

from decimal import *
from math import sqrt
import itertools

getcontext().prec = 100

r5 = Decimal('5').sqrt()

#fibonacci function 2
def fib1():
    n = -1
    while True:
        n += 1
        yield round(((1+r5)**n-(1-r5)**n)/(2**n*r5))

#fibonacci function 1
def fib2():
    a,b = 0,1
    while True:
        yield a
        a, b = b, a + b


r = itertools.dropwhile(lambda x: x[0]==x[1],itertools.zip_longest(fib1(),fib2()))
print(next(r))

精度为100，结果为

(196191955446197556957565929345772792668594307949581132632670453793550007197467505024573547039776940, 196191955446197556957565929345772792668594307949581132632670453793550007197467505024573547039776939)

已实现。相当令人印象深刻!我使用的精度为 1000，结果

(1269356787836526638292881388412062563384016584999139363845916252828272232391810020280832776534348222207097659424636568046262415695352482639760055677447593862489663810195738708939477943905134153356636045977981999863686835051315779906086619798132074368682560092328661225751314808679246693245387236063332746366841928263523362820098118474833094929286676587582542369660341001022447403731596463443972162558919745776554315895623816909167795557047770582177376717988622403278870301415328956789820495406257373628508043139338202820103414370691678600911481661883803507957985612992446553943499307293537223525134209303990984810141957868318317038241920752310815343034067670415777278631587961096314226337926487733666947275129471624775876156460533864928511199003774695438447857706244332893210973780928258183512460663452551185318925295791590656959561960353727992207635442970269567411956580203564583038131744735283364875667417153145494305056027330033836269453405615559944082171014269659283681044165083851285941191290, 1269356787836526638292881388412062563384016584999139363845916252828272232391810020280832776534348222207097659424636568046262415695352482639760055677447593862489663810195738708939477943905134153356636045977981999863686835051315779906086619798132074368682560092328661225751314808679246693245387236063332746366841928263523362820098118474833094929286676587582542369660341001022447403731596463443972162558919745776554315895623816909167795557047770582177376717988622403278870301415328956789820495406257373628508043139338202820103414370691678600911481661883803507957985612992446553943499307293537223525134209303990984810141957868318317038241920752310815343034067670415777278631587961096314226337926487733666947275129471624775876156460533864928511199003774695438447857706244332893210973780928258183512460663452551185318925295791590656959561960353727992207635442970269567411956580203564583038131744735283364875667417153145494305056027330033836269453405615559944082171014269659283681044165083851285941191291)

尽管代码确实需要一段时间才能运行(约 30 秒)。