Big Integers in Memoized Recursive Fibonacci (Y)

Question

I've written a version of Y that automatically caches old values in a closure using memoization.

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

Now, when almostFibonacci (defined below) is passed into the above function, it returns the value of a large Fibonacci number comfortably.

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

However, after a certain value (Number.MAX_SAFE_INTEGER), integers in JavaScript (owing to their IEEE-754 double precision format) are not accurate. So, considering the fact that the only mathematical operations in the Fibonacci function above are addition and subtraction and since operators cannot be overloaded in JavaScript, I wrote naïve implementations of the sum and difference functions (that both use strings to support big integers) which are as follows.

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

Now, by themselves, both these functions work perfectly.¹

I have now updated the almostFibonacci function to as follows to use the sum function instead of + and the difference function instead of the - operator.

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

As you may have guessed, this does work. It crashes the fiddle in case of even a small number like 10.

Question: What could be wrong? All the functions here work perfectly individually. But in tandem, they seem to fail. Can anyone here help me debug this particularly complex scenario?

¹Except an edge case for the difference function. It requires the first argument to be larger than the second.

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.

And that's the problem. In your fibonacci algorithm you're at some point calculating difference("2", "2"), which needs to yield "0" to work. It does however return the empty string "", which is not tested against as your guard condition for the recursion. When in the next step computing difference("", "1"), the function will fall into an infinite loop.

Solutions:

• Fix that edge case (you still won't need to cope with negative numbers)

• Don't use strings for the ordinal number, but only for the fibonacci number itself. You hardly will try the compute the (2⁵³+1)th fibonacci number, will you? I would assume this to be a significant speed improvement as well.

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