javascript - 内存递归斐波那契 (Y) 中的大整数

Question

我编写了一个 Y 版本，它使用内存自动将旧值缓存在闭包中。

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;
    };
};

现在，当 almostFibonacci(定义如下)被传递到上面的函数中时，它会轻松返回一个大斐波纳契数的值。

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

但是，在某个值 (Number.MAX_SAFE_INTEGER) 之后，JavaScript 中的整数(由于它们的 IEEE-754 double 格式)不准确。因此，考虑到上述斐波那契函数中唯一的数学运算是加法和减法，并且由于运算符在 JavaScript 中不能重载，我编写了求和函数和差函数的朴素实现(它们都使用字符串支持大整数)，如下所示。

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('');
};

现在，这两个功能本身就可以完美运行。¹

我现在已经将 almostFibonacci 函数更新为如下所示，以使用 sum 函数代替 + 和 difference 函数而不是 - 运算符。

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

您可能已经猜到了，这确实有效。即使是像 10 这样的小数字，它也会使 fiddle 崩溃。

问题:可能出了什么问题？这里的所有功能都可以完美地独立运行。但一前一后，他们似乎失败了。这里有人可以帮我调试这个特别复杂的场景吗？

¹差异函数的边缘情况除外。它要求第一个参数大于第二个。

Answer 1

Now, by themselves, both these functions work perfectly - Except an edge case for the difference function. It requires the first argument to be larger than the second.

这就是问题所在。在您的斐波那契算法中，您有时会计算 difference("2", "2")，这需要产生 "0" 才能工作。但是，它确实返回空字符串 ""，它没有作为递归的保护条件进行测试。在下一步计算difference("", "1")时，函数会陷入死循环。

解决方案:

• 修复边缘情况(您仍然不需要处理负数)

• 不要将字符串用于序数，而只能用于斐波那契数本身。您几乎不会尝试计算第 (2⁵³+1) 个斐波那契数，对吗？我认为这也会显着提高速度。

  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));
      };
  });