He escrito una versión de Y que almacena automáticamente en caché los valores antiguos en un cierre utilizando la memorización.

var Y = function (f, cache) {
    cache = cache || {};
    return function (x) {
        if (x in cache) return cache[x];
        var result = f(function (n) {
            return Y(f, cache)(n);
        })(x);
        return cache[x] = result;
    };
};

Ahora, cuando almostFibonacci (definido a continuación) se pasa a la función anterior, devuelve el valor de un gran número de Fibonacci cómodamente.

var almostFibonacci = function (f) {
    return function (n) {
        return n === '0' || n === '1' ? n : f(n - 1) + f(n - 2);
    };
};

Sin embargo, después de un cierto valor (Number.MAX_SAFE_INTEGER), los enteros en JavaScript (debido a su formato de doble precisión IEEE-754 ) no son precisos. Entonces, considerando el hecho de que las únicas operaciones matemáticas en la función Fibonacci anterior son la suma y la resta y dado que los operadores no se pueden sobrecargar en JavaScript, escribí implementaciones ingenuas de las funciones de suma y diferencia (que usan cadenas) para admitir enteros grandes) que son los siguientes.

String.prototype.reverse = function () {
    return this.split('').reverse().join('');
};

var difference = function (first, second) {
    first = first.reverse();
    second = second.reverse();
    var firstDigit,
    secondDigit,
    differenceDigits = [],
        differenceDigit,
        carry = 0,
        index = 0;
    while (index < first.length || index < second.length || carry !== 0) {
        firstDigit = index < first.length ? parseInt(first[index], 10) : 0;
        secondDigit = index < second.length ? parseInt(second[index], 10) : 0;
        differenceDigit = firstDigit - secondDigit - carry;
        differenceDigits.push((differenceDigit + (differenceDigit < 0 ? 10 : 0)).toString());
        carry = differenceDigit < 0 ? 1 : 0;
        index++;
    }
    differenceDigits.reverse();
    while (differenceDigits[0] === '0') differenceDigits.shift();
    return differenceDigits.join('');
};

var sum = function (first, second) {
    first = first.reverse();
    second = second.reverse();
    var firstDigit,
    secondDigit,
    sumDigits = [],
        sumDigit,
        carry = 0,
        index = 0;
    while (index < first.length || index < second.length || carry !== 0) {
        firstDigit = index < first.length ? parseInt(first[index], 10) : 0;
        secondDigit = index < second.length ? parseInt(second[index], 10) : 0;
        sumDigit = firstDigit + secondDigit + carry;
        sumDigits.push((sumDigit % 10).toString());
        carry = sumDigit > 9 ? 1 : 0;
        index++;
    }
    sumDigits.reverse();
    while (sumDigits[0] === '0') sumDigits.shift();
    return sumDigits.join('');
};

1

Ahora he actualizado la función almostFibonacci de la siguiente manera para usar la función suma en lugar de + y la función diferencia en lugar de - operador.

var almostFibonacci = function (f) {
    return function (n) {
        return n === '0' || n === '1' ? n : sum(f(difference(n, '1')), f(difference(n, '2')));
    };
};

Como habrás adivinado, esto funciona. Se bloquea el violín en caso de que incluso un pequeño número como 10.

Pregunta: ¿Qué podría estar mal? Todas las funciones aquí funcionan perfectamente individualmente. Pero en conjunto, parecen fallar. ¿Alguien puede ayudarme a depurar este escenario particularmente complejo?

1 Excepto un caso de borde para la función de diferencia. Requiere que el primer argumento sea mayor que el segundo.

3
Siddharth 28 ago. 2014 a las 17:50

2 respuestas

La mejor respuesta

Ahora, por sí mismas, ambas funciones funcionan perfectamente: excepto un caso límite para la función de diferencia. Requiere que el primer argumento sea mayor que el segundo.

Y ese es el problema. En su algoritmo de Fibonacci, en algún momento está calculando difference("2", "2"), que necesita producir "0" para funcionar. Sin embargo, devuelve la cadena vacía "", que no se prueba como su condición de protección para la recurrencia. Cuando en el siguiente paso computando difference("", "1"), la función caerá en un bucle infinito.

Soluciones:

  • Arregle ese caso límite (aún no tendrá que lidiar con números negativos)
  • No use cadenas para el número ordinal, sino solo para el número de Fibonacci en sí. Difícilmente intentará calcular el (2 53 +1) número de fibonacci, ¿verdad? Supongo que esto también es una mejora significativa de la velocidad.

    var fibonacci = Y(function(fib) {
        return function(n) {
            if (n == 0) return "0";
            if (n == 1) return "1";
            return sum(fib(n-1), fib(n-2));
        };
    });
    
2
Bergi 29 ago. 2014 a las 10:53

Así es como resolví el problema en cuestión.

Cambios :

  • Eliminé la declaración while (differenceDigits[0] === '0') differenceDigits.shift();. Aunque esto genera diferencias sin ceros iniciales truncados, genera un '0' en caso de un caso de borde como difference('2', '2').
  • Edité la declaración de devolución en la función almostFibonacci a return n == 0 || n == 1 ? n : sum(f(difference(n, '1')), f(difference(n, '2')));. Observe que estoy buscando 0 y no '0' con un operador de igualdad no estricto. 1

1 La razón por la que estoy haciendo n == 0 en lugar de n === '0' es porque en JavaScript, '00000' == 0 pero '00000' !== '0' y en mi nueva función de diferencia actualizada, sin ceros iniciales truncados, no puedo garantizar el número de ceros para una salida cero. Bueno, en realidad sí puedo. Habría tantos ceros como la longitud de n.

100o Fibonacci - JSFiddle

-1
Community 20 jun. 2020 a las 09:12