Получить точные значения для больших чисел Фибоначчи в питоне, используя формулу Бине - PullRequest
Новая
       5

Получить точные значения для больших чисел Фибоначчи в питоне, используя формулу Бине

0 голосов
/ 01 февраля 2019

Я изучал itertools и пытался проверить точность формулы Бине, реализованной в python.Причиной использования 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() я использовал round() в fib1(), и результат составил 

(308061521170130, 308061521170129)

Что можно сделать для повышения точности реализации формулы моего бинета?

1 Ответ

0 голосов
/ 01 февраля 2019

decimal это путь.Кстати, в конце нет смысла islice с 1, когда вы можете просто сделать next(r): 

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 секунд).

...