Momento Coder …. Acelera Fibonacci a tope!!!

Hace mucho que no ponemos ningún reto … a sí que a la carga!!!


Hoy no vamos a hablar ni de empresa, ni de servicios, ni de web ni nada, hoy toca picarse a ver quién es el más rápido!


Recuerdas tus primeros pinitos en la algoritmia? hacer piramides, ordenar números… si? y recuerdas Fibonacci? 😉


No voy a explicarlo de nuevo, la red esta llena de explicaciones y algoritmos de retos de este tipo de cosas. Te propongo un reto, para coders con algo de tiempo ( en casa o en el trabajo )  …



¿Cómo de rápido eres haciendo Fibonacci del 1 al 44? Me explico… tiempo acumulado utilizado en calcular Fibonacci para los números enteros comprendidos entre el 1 y el 44, ambos incluidos 🙂


Ojo, el algoritmo es bien conocido, implementado de una forma más o menos bonita, pero se te ocurre alguna forma de hacer la ejecución más rápida?


Como condición… tiene que compilar con Visual Studio 2008 y ser código .NET ( ahora bien, puedes usar herramientas/librerías instaladas sobre Visual Studio 2008 )


Te parece bien hasta este domingo 22/11/08 a las 6pm en tiempo GMT+1?


Para hacer esto un poco más interesante… habrá un detalle para el más rápido…. a no ser que gane yo 😉


Como el detalle te lo mandaré a casa, me temo que lo tenemos que restringir a los participantes de España ( lo siento por el resto, pero si no, os iba a salir el detalle caro de narices en la aduana :_) )


Los que os animéis… cuando estéis listos podéis enviarme vuestros proyectos / soluciones a david.salgado en microsoft.com


Publicaré el ganador el lunes 13/11/08 23/11/08 (tnx phobeo)


Happy Coding!!!

Publicado por

19 comentarios en “Momento Coder …. Acelera Fibonacci a tope!!!”

  1. estoy presuponiendo que no quieres la solucion en tiempo constante (que consiste en tener una bonita tabla con 44 entradas precalculadas :P)

    Que otras restricciones tenemos? (del estilo de “el algoritmo no puede usar constantes precalculadas”) ;D

  2. por cierto, el ganador no lo puedes publicar el 13/11/08 a no ser que tengas una maquina del tiempo que te permita volver atras a anunciar el ganador, y en ese caso no ha ganado nadie porque ya lo habrias publicado asi que… para que participar?

  3. Juas :_)

    ok..corregido lo de la máquina del tiempo, pensé q todos teníais una!

    Como has indicado, no vale tener el cálculo hecho y hacer un writeline 🙂 Puedes intentar acelerar el algoritmo, pero hay q calcularlo! 😀

    No voy a entrar en muchos detalles m’as pq se ve todo ya 😛

  4. +1 al comentario de Ricardo.

    Y añado: ¿Podrías definir “rápido”? Si hablamos de milisegundos, no me parece justo ya que dependería de muchos, muchísimos factores (qué entorno de pruebas usarías para evaluar?). Si hablamos de ciclos de CPU, habría que tener en cuenta la posibilidad de emplear C# 4.0 y paralelismo, lo cual desvirtuaría un tanto la comparación en cuanto a ciclos de CPU se refiere.

    btw, muy interesante el reto 🙂

  5. vengaaaa no seais puntillosos… 😛

    Cómo se medirá la velocidad?
    en mi laptop, un lenovo T61p con vista sp1 y 2G RAM, negro y con la pantalla sucia.

    En el código, con Stopwatch y el elapsed, y el más rápido gana.

    Hay unas cuantas formas de sacarle punta al algoritmo base, pero aqui lo que cuenta no es decir nombres de APIs, o especular con como sería o no, lo que cuenta es mandar un proyecto y que corra como alma que lleva el diablo! 😀

    Como un profesor de mi universidad… “no vale con mirar el papel compañero del metal, los problemas se resuelven empezando con ellos!”

  6. Nah, esta pirada de pinza de salgado (a la que nos arrastra), tiene dos problemas.

    Por un lado es muy facil hacer el fibonacci de toda la vida, asi que no tiene tanta gracia. Pero por otro lado, es muy jodido mejorarlo, lo cual no tiene tampoco nada de gracia cuando te das cuenta el tiempo que llevas dedicado a esta chorrada en vez de a otras cosas mas productivas, como viciar o dormir.

    Cosas que darian mucho juego serian movidas como un algoritmo al que le vamos a pasar un numero que pertenece a la serie de fibonacci y tiene que calcular el siguiente, que eso tiene mas chicha (sin usar lo de phi que no es exacto).

    Yo, despues de pelearme un rato con lo que propuso David, he decidido que en un arranque de originalidad voy a hacer algoritmos de fibonacci MAS LENTOS (pero bonitos, eso si), que siempre queda chulo.

    PD: Hasta leer a Varela pensaba hacerlo yo también, una pena (eh, que fijo que no todo el mundo se da cuenta)

  7. Nos falta un poco más de definición, creo. ¿Basta con imprimir el 44-ésimo? ¿O hay que imprimir los 44 en la consola? Entonces nos pasará como a Juan… Y si no se imprime nada, habrá que usar ticks en vez de milisegundos – mi portátil ya está viejito (recuerda como cascó en Guadalajara 🙂 y obtengo 0 ms…

    Abrazo – Octavio

  8. oks…

    la salida debería ser algo así…

    f(1) = …
    f(2) = …
    f(3) = …
    f(4) = …

    f(44) = …

    Y para medir el tiempo (los q ya me lo hab’eis mandado no os preocupéis que lo cambio yo)

    Stopwatch sw = new Stopwatch()
    sw.Start();
    //pon tu calculo aqui
    sw.Stop();
    Console.WriteLine(sw.Elapsed); 🙂

    #Razhan te picarías si proponemos un concurso de quines? 😀

  9. Tiempo al tiempo… a lo mejor alguno se sorprende de la “utilidad” del planteamiento de David.

    Yo pondré mis dos centavos, y os aseguro que es muy interesante la pregunta y posibles planteamientos que se pueden sacar de este ejercicio teórico-práctico. 😉

  10. Uff, quines.

    No se el resto de gente, pero de hacerlo, casi mejor en una epoca con menos trabajo.

    Una opcion seria el puente de la constitucion (aunque creo que de puente tiene poco este año).

    No prometo nada, pero si las fechas me son propicias y no estoy hasta el cuello de curro, lo mirare.

  11. Hola David
    El reto es interesante pero creo que no está bien planteado.
    En primer lugar, con los ordenadores actuales los 44 primeros números de la sucesión de fibonacci la hace en un suspiro. En mi caso estoy en torno a 0.0000019 segundos. Aunque cada vez que lo ejecuto me dan cosas distintas.
    Si se piden todos los términos, la opción más rápida es la más natural, ir sumando los 2 términos anteriores. Lo interesante es calcular directamente el término 44 o algo más grande como él termino 100 o el 200, con lo que se pueden hacer atajos. Quizás se pueda ir dando saltos y calcular los huecos en otros hilos.
    Otra posibilidad es hacer cálculo matricial usando Lapack y Blas. Y ya puestos usar CUDA. Aunque en tan poco tiempo no me va a dar tiempo a investigar en el tema. Además con los tiempos que hablamos, no hay mucha posibilidad de mejora.

  12. Hola.

    Yo quizá me pierdo algo, pero coincido con Andres. Si se nos piden todos los términos no veo que haya mucho donde optimizar.
    He estado investigando un poquillo sobre el tema… calculo fibonacci de hasta 6 formas distintas y la más trivial és la más rápida…

    Otra cosa seria que nos pidieses que calculasemos fibonacci solamente de los números primos entre 1 y 5000… ahí es nada 🙂 Aunque el problema es que fibonacci de 5000 no cabe ni en un looooooong (así con muchas os :p).

    Saludos!

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *