Cálculo de número de Fibonacci n-ésima utilizando las fórmulas en pitón

Question

estoy calcular el número de Fibonacci n-ésima utilizando (a) un enfoque lineal, y (b) this expresión

Python código:

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

Para n> 71 veo que las dos funciones devuelven valores diferentes.

¿Esto se debe a la aritmética de coma flotante involucrada en efib()? Si es así, ¿es aconsejable calcular el número usando el matrix form?

Answer 1

De hecho, está viendo errores de redondeo.

El formulario de la matriz es el más preciso y algoritmo mucho más rápido. Literateprograms.org enumera una buena aplicación, pero también enumera el siguiente algoritmo basado en los números de 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 

Tome un vistazo a Lecture 3 of the MIT Open Courseware course on algorithms para un buen análisis del enfoque de la matriz.

Tanto el algoritmo anterior como el enfoque matricial tienen complejidad Θ (lg n), al igual que el método de cuadratura recursiva ingenua que usaste, pero sin los problemas de redondeo. El enfoque de los números de Lucas tiene el costo más bajo constante, por lo que es el algoritmo más rápido (aproximadamente el doble de rápido que el método de la matriz):

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

Se debe esto a la aritmética de coma flotante involucrado en EFIB()?

Sí, lo es. Dentro efib tiene

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

y Python floats have about 53 bits of precision en hardware x86-64, por lo que se está ejecutando cerca del borde.

Answer 3

Tengo un código muy simple puramente pitón ...

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