9007199254740992

July 15, 2008 at 10:31 pm (JavaScript)
Tags: , , , , , , ,

After my discussion of JavaScript’s numeric limitations when working with integers, I was curious. There must be some integer that’s the biggest one that JavaScript can represent.

A brute force method (my favorite kind) would simply increment a variable and see when it stops going up. Add one. Add one. Add one. Stuck.

That number is so large, though, that even I didn’t have the patience to wait for the loop to end. So I broke the problem up into two pieces.

First I set a variable to 1. I keep doubling it until I find a number that is the same as that number plus one. That’s my high limit and half that number is valid.

Then I do a binary search inside that range. The code looks like this:

    a=1;
    b=2;
    //find one that fails
    while (a!=b) {
        old=a;
        a+=a;
        b=a+1;
    }
    //do binary search
    low=old;
    high=a;
    while (high-low>1) {
        mid=parseInt((low+high)/2,10);
        a=mid;
        b=a+1;
        if (a==b) {
            high=mid;
        } else {
            low=mid;
        }
    }
    console.log(high);

The answer is 9007199254740992. Something over 9 quadrillion. Makes more sense why it would be a limit when you look at the number in hexadecimal. That’s 0x020000000000000.

That’s right. JavaScript can tell the difference between 9007199254740991 and 9007199254740992, but it thinks that 9007199254740992 and 9007199254740993 are the same. That falls out from the IEEE-754 double-precision floating-point spec that JavaScript uses to represent all numbers.

Remember that next time you want to write a for loop that counts to 10 quadrillion–it’s an infinite loop. You’ll never get there.

14 Comments

JavaScript Numbers Can Bite

July 15, 2008 at 5:20 am (JavaScript)
Tags: , , , , , , , , , ,

Sooner or later, JavaScript’s numbers will bite you. They bit me in a probability function, and I didn’t even see it coming.

Maybe you took a probability and statistics class and learned about combinations and permutations. You may remember that the formulas for those involve factorials. Let’s take a look at my combination routine.

    //---------------------------------------------------------
    // Function: combinations
    //   returns the combinations of k objects from a set of n objects
    combinations=function(n,k) {
        function factorial(a) {
            return a<2 ? 1 : a*factorial(a-1);
        }
        return Math.round(factorial(n)/(factorial(k)*factorial(n-k)));
    }

Kind of an interesting looking function, isn’t it? When you find the number of possible ways that you can put together a k objects from a set of n objects, you need to do three factorial functions. Since I didn’t need factorial anywhere else, I stuffed it inside the combinations function.

But what’s the Math.round doing there? Aren’t we dealing with whole numbers here? Yep. In most languages, we’d explicitly declare the variables for this function to be integers, but that’s just not an option in JavaScript–all numbers in JavaScript are floating point numbers.

Trouble Ahead

So where do we run into trouble? If n is 23 and k is 2, combinations returns 253.00000000000003.

Even more frustrating is this answer because it’s one we can come up with off the top of our heads: If n is 24 and k is 23, we get 23.999999999999996.

What’s happening? Our numbers are growing so large in factorial that they can no longer be represented exactly in JavaScript. The solution? In this case, I fix the result with Math.round().

Playing Computer

But we can do better if we play computer with even a small case. Let’s take n=5, k=2;

combinations=(5*4*3*2*1) / ((3*2*1) * (2*1));
//largest number calculated is 120

That could be changed to

combinations=(5*4) / (2*1);
//largest number calculated is 20

A huge change. Much better. Three floating point operations rather than nine. Less chance for mischief.

Factorial is a well known function, and the combination formula is easy to write in terms of factorial, but that ease of representation comes at a huge computational cost, and in the case of JavaScript, sometimes a cost of precision.

If we rewrite the function to take advantage of this insight, we’ll be able to support much larger parameters before we run into trouble.

The General Idea

The solution to most of these problems is to rearrange the math so intermediate results don’t get as big.

This was a nasty problem to catch, because many results were calculated correctly. But it didn’t take long to come up with a couple solutions.

3 Comments