6

So, I started out by trying to find the 100th Fibonacci number using a recursive function and by memoizing the function using the following code.

Function.prototype.memoize = function () {
    var originalFunction = this,
        slice = Array.prototype.slice;
        cache = {};
    return function () {
        var key = slice.call(arguments);
        if (key in cache) {
            return cache[key];
        } else {
            return cache[key] = originalFunction.apply(this, key);
        }
    };
};

var fibonacci = function (n) {
    return n === 0 || n === 1 ? n : fibonacci(n - 1) + fibonacci(n - 2);
}.memoize();

console.log(fibonacci(100));

Now, as you can see in this fiddle, JavaScript logs 354224848179262000000 as the result. The hundredth Fibonacci number is actually 354224848179261915075 according to WolframAlpha which is correct.

Now, my question is this. Why does the number compute incorrectly, even though the algorithm is completely sane? My thoughts point to JavaScript because according to Google's calculator1, the two numbers are equal.

What is it about JavaScript that causes such an error? The number is safely within limits of the maximum value of an IEEE 754 number, which is 1.7976931348623157e+308.

1In case this could be a bug on my platform, I have tested this on both Chromium and Firefox on Ubuntu.

Siddharth
  • 1,146
  • 3
  • 15
  • 28
  • 2
    http://stackoverflow.com/questions/307179/what-is-javascripts-max-int-whats-the-highest-integer-value-a-number-can-go-t – nullability Aug 21 '14 at 17:40
  • 3
    Careful, the `cache` variable is leaking. – elclanrs Aug 21 '14 at 17:42
  • precision is only there till +/- 9007199254740992, read my similar answer to your question here: http://stackoverflow.com/questions/21726932/32-bit-of-precision-what-does-it-mean/21727431#21727431 – CodeFanatic Aug 21 '14 at 17:42
  • @elclanrs, yes. I didn't bother to cap the cache's size. Consider it a naïve implementation just to demonstrate the issue with simplicity. – Siddharth Aug 21 '14 at 17:48

2 Answers2

13

As your number gets bigger, your lose precision, the maximum safe number in JavaScript is actually Number.MAX_SAFE_INTEGER === 9007199254740991

For every extra bit that is required you lose 1 bit of precision because the last bit is assumed to be zero.

according to IEEE754 354224848179262000000 equals in binary to:

0 10001000011 0011001100111101101101110110101001111100010110010110

The exponent, 10001000011 is 1091, which results to 68 if you subtract 1023.
This means you are using 68 bits to represent your significant, since their are only 52 bits available for the significant, the last 16 bits are assumed to be zero. Any calculations that fall in those 16 bits will have no effect.

Willem D'Haeseleer
  • 19,661
  • 9
  • 66
  • 99
4

Because IEEE-754 double precision floating point only provides 15 to 17 significant digits of precision.

Robert Harvey
  • 178,213
  • 47
  • 333
  • 501