0votos

Fibonacci rapido en Haskell

por josejuan hace 6 años

Por cierto, la solución más rápida para N alto es calcularlo directamente (sin usar recurrencias). El único problema es que la solución implica números irracionales, por tanto deben usarse tantos decimales en el cálculo para asegurar redondeo correcto (si dispusiéramos de infinitos decimales no habría que redondear). Aquí pongo la expresión general (¡que es Haskell!), aunque puede verse en (eg) wikipedia.

1 1 2 3 5 8 ... algunos ya conoceran este problema,pero lo interesante o dificil es obtener la solucion mas rapida.

1
f(n) = (((1+sqrt(5))/2)^n - ((1-sqrt(5))/2)^n)/sqrt(5) 
1 comentario
0votos

Escrito por josejuan hace 6 años

Por ejemplo, definidas mis dos últimas soluciones, la primera discrepancia aparece en:

> take 1 $ dropWhile (\(x,y) -> x == y) $ zip (f 0 1) (tail $ map (round.fib) [1..])
[(3416454622906707,3416454622906706)]

es decir, en el 77 fibonacci.

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.