4votos

Fibonacci rapido en Haskell

por josejuan hace 6 años

Gorka ya ha dado la solución eficiente ¿se podrá realizar alguna optimización?, la mía en Haskell creo que es muy chula :P

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

1
2
3
4
5
-- inifinitos fibonacci 
f a b = c: f b c where c = a + b 
 
-- para recuperar el n-ésimo 
(f 0 1)!!n 
3 comentarios
0votos

Escrito por JoseRaul hace 6 años

La solucion mas eficiente es usar la exponenciacion de matrices.

http://es.wikipedia.org/wiki/Sucesi%C3%B3ndeFibonacci

Se encuentra en la seccion algoritmo de calculo.

Aunque el algoritmo no es O(log n) por que el tiempo que se tarda en hacer las multiplicaciones es muy grande.

Si usamos el algoritmo normal o el que conocemos de multiplicacion O(N*M) N y M la cantidad de digitos de cada numero , usando el teorema master nos queda un algoritmo O(N^2) ,igual que el iterativo cada adiccion necesita O(N), La forma optima depende de que de rapido sea el algoritmo de multiplicacion.

La forma es buscar una biblioteca de numeros grandes la cual soporte estos algoritmos de multiplicacion,Los cuales son bastante tedioso y complejos de programar,La biblioteca en Java su algoritmo de multiplicacion es de O(N*M) y por extencion los lenguajes base Java(Clojure,Scala,JRuby...),Creo que GMP soporta estas formas optimas y Haskell las usa.

En resumen implementar la forma por exponenciacion de matrices en Haskell.
0votos

Escrito por josejuan hace 6 años

"La solucion mas eficiente"

rizando el rizo ¿eh? XD XD, la que comentas es la segunda que he indicado, y como bien dices para calcular la exponencial, la que comentas.
0votos

Escrito por JoseRaul hace 6 años

Jeje un lapsus queria decir "la solucion mas eficiente que conosco",por que la solucion directa,el manejo de irracionales no permite que funcione correctamente.

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.