Obliczanie n-liczbę Fibonacciego przy użyciu formuły pytona

Question

ja obliczenia n-liczbę Fibonacciego pomocą (a) liniowy sposób i (B) this ekspresji

Pythona Kod:

'Different implementations for computing the n-th fibonacci number' 

def lfib(n): 
    'Find the n-th fibonacci number iteratively' 
    a, b = 0, 1 
    for i in range(n): 
     a, b = b, a + b 
    return a 

def efib(n): 
    'Compute the n-th fibonacci number using the formulae' 
    from math import sqrt, floor 
    x = (1 + sqrt(5))/2 
    return long(floor((x**n)/sqrt(5) + 0.5)) 


if __name__ == '__main__': 
    for i in range(60,80): 
    if lfib(i) != efib(i): 
     print i, "lfib:", lfib(i) 
     print " efib:", efib(i) 

Dla n> 71 widzę, że te dwie funkcje zwracają różne wartości.

Czy wynika to z arytmetyki zmiennoprzecinkowej związanej z efib()? Jeśli tak, to czy jest to wskazane, aby obliczyć liczbę za pomocą matrix form?

Answer 1

Rzeczywiście widzisz błędy zaokrąglania.

Forma macierzowa jest bardziej dokładnym algorytmem o znacznie szybszym działaniu: i. Literateprograms.org wymienia dobre wykonanie, ale również wymienia następujący algorytm oparty na liczbach Lucas

def powLF(n): 
    if n == 1:  return (1, 1) 
    L, F = powLF(n//2) 
    L, F = (L**2 + 5*F**2) >> 1, L*F 
    if n & 1: 
     return ((L + 5*F)>>1, (L + F) >>1) 
    else: 
     return (L, F) 

def fib(n): 
    if n & 1: 
     return powLF(n)[1] 
    else: 
     L, F = powLF(n // 2) 
     return L * F 

przyjrzeć Lecture 3 of the MIT Open Courseware course on algorithms dobrego analizy podejścia matrycy.

Zarówno powyższy algorytm, jak i podejście macierzowe mają złożoność Θ (lg n), podobnie jak naiwna metoda rekursywnego kwadratu, z której korzystałeś, ale bez problemów z zaokrąglaniem. Liczby podejście Lucas ma najniższe koszty stałe, dzięki czemu jest szybszy algorytm (około dwa razy szybciej niż podejście MATRIX):

>>> timeit.timeit('fib(1000)', 'from __main__ import fibM as fib', number=10000) 
0.40711593627929688 
>>> timeit.timeit('fib(1000)', 'from __main__ import fibL as fib', number=10000) 
0.20211100578308105 

Answer 2

Czy to ze względu na arytmetyce zmiennoprzecinkowej zaangażowany w efib()?

Tak, jest. W ciągu efib masz

>>> log(x**72)/log(2) 
49.98541778140445 

i Python floats have about 53 bits of precision na x86-64 sprzętu, więc używasz blisko krawędzi.

Answer 3

Mam bardzo prostego kodu Pythona czysto ...

def fibonum(n): # Give the nth fibonacci number 
    x=[0,1] 
    for i in range(2,n): 
     x.append(x[i-2]+x[i-1]) 
    print(x[n-1])