Fibo(1000): códigos y comentarios.

[dggluz]

Disculpen por "arruinarles" este divertido desafío, pero me encontré teniendo que ingeniármelas para entender los códigos que posteaban. Me resultó interesantísimo cuando entendí (al menos en parte) qué es lo que hacían. Decidí entonces facilitarles la tarea a los demás navegantes y explicar una solución, para que no tengan que romperse la cabeza (o que sí lo hagan, pero que no se frustren si no lo entienden).
El código que me quedó calcula bien y rápidamente fibo(1000).

ADVERTENCIA: si quieres resolver el desafío completamente por tu cuenta, no sigas leyendo mi comentario.

Gracias a la comunidad de ForosDelWeb en general por las magníficas ideas aportadas.
Si no sabes qué es la Serie de Fibonacci, primero dedícate a averiguar qué es y luego sigue leyendo el post.

Explicación: la serie de Fibonacci, traducida literalmente de la matemática a la computación resulta una función recursiva como la siguiente:

Código Javascript:

function fibonacci(n)
{
    if(n==0)
    {
        return 0;
    }
    if(n<=2)
    {
        return 1;
    }
    return fibonacci(n-1)+fibonacci(n-2);
}
 

El problema con esa solución es que la computadora hace mucho más proceso que el necesario. Y eso no es sólo porque evaluar recursivamente una función requiera más procesamiento que dentro de un bucle, sino porque sencillamente se calcula de más:
Cada vez que se requiere calcular un fibonacci(n) con n>2, deben calcularse dos números de fibonacci y así recursivamente; pero se calculan muchas veces los mismos números. Veamos un ejemplo:
fibonacci(6):
- Debe calcular fibonacci(5) y fibonacci(4).
fibonacci(5):
- Debe calcular fibonacci(4) y fibonacci(3).
fibonacci(4):
- Debe calcular fibonacci(3) y fibonacci(2).
fibonacci(3):
- Debe calcular fibonacci(2) y fibonacci(1).
fibonacci(2) y fibonacci(1):
- Es 1 (f(0)=0, f(1)=1, f(2)=1)

¿Me siguieron? Para calcular el fibonacci(6) hay que calcular una vez el fibonacci(5), 2 veces el fibonacci(4), 3 veces el fibonacci(3), 5 veces el fibonacci(2) y 3 veces el fibonacci(1) ¡14 cálculos! (más la suma final: ¡15!). Si no me creen háganse una prueba de escritorio con lápiz y papel... les quedará un lindo arbolito.

Obviamente el fibonacci(k) siendo k constante siempre será el mismo, por lo cual calcularlo más de una vez es innecesario. Y lo peor es que la situación empera drásticamente al tener que calcular fibonacci(1000). Hay algunas soluciones computacionales a esto, como memoization.
Pero el problema se evita pensando el cálculo desde otra perspectiva: sólo se necesitan dos variables (más una auxiliar) para calcular cualquier número de fibonacci, siendo que estas variables contienen una el fibonacci(n-1) y la otra el fibonacci(n-2), pero sin necesidad de llamar a la función recursivamente para calcularlos, sino calculándolos a partir de fibonacci(1) y fibonacci(2) y guardando siempre los resultados parciales en estas mismas variables (esta idea la tomé de la solución de Caricatos en este post):

Código Javascript:

function fiboN(n)
{
    var f1=1;
    var f2=1;
    var aux;
    for(var i=n; i>2; i--)
    {
        aux=f1;
        f1+=f2;
        f2=aux;
    }
    return f1;
}
 

Esta solución es sensiblemente más veloz (muchísimo más veloz de hecho, sólo calcula n-2 veces para fibonacci(n)) que la anterior. Pero tiene un problema: Javascript (así como la gran mayoría de lenguajes de programación, una buena excepción es Python) no tiene cálculos aritméticos exactos cuando se trata de números muy grandes (o muy pequeños), sino que usan para almacenarlos en memoria una notación exponencial, que si bien es muy eficiente, es inexacta. Por eso, cuando se intentan calcular fibonacci's grandes, los números empiezan a dar resultados erróneos. La solución que encontré a esto es almacenar los números como cadenas de caracteres. Para ello es necesario definir una suma de cadenas de caracteres como si de números se tratara (el algoritmo que uno utiliza cuando suma "a mano", con arrastre y todo), de modo que la computadora nunca tenga que manejar números grandes (de hecho, nunca mayores a 20). Entonces sí, el código final (muuuuuuuy similar al de Nahuel2k10):

Código Javascript:

function fibo(n)
{
    var f1='1';
    var f2='1';
    var aux;
    for(var i=n; i>2; i--)
    {
        aux=f1;
        f1=sumar(f1,f2);
        f2=aux;
    }
    return f1;
}
 
function sumar(a,b)
{
    // Siempre a es mayor o igual que b      %
    var arrastre=false;
    var ret='';
    var suma;
    var dif=a.length-b.length;
    for(var i=a.length-1; i>=0; i--)
    {
        suma=arrastre?1:0;
        suma+=parseInt(a.charAt(i))+parseInt(((i-dif)>=0)?b.charAt(i-dif):'0');
        if(suma>=10)
        {
            arrastre=true;
            suma=suma%10;
        }
        else
        {
            arrastre=false;
        }
        ret=suma+ret;
    }
    if(arrastre)
    {
        ret='1'+ret;
    }
    return ret;
}
 

¡Suerte!