As I read an article about solving the 8-queen problem storing the board in a 64bit integer (French) I wanted to test it in Javascript. I knew that numbers where not stored as int64 but who knows, maybe it would have worked!

As you may have expected, it failed, giving completly off results. The reason behind this is a lack of precision, the least significant bits are being ignored.

(0x8040201008040201).toString(2)
//  10000000 01000000 00100000 00010000 00001000 00000100 00000010 00000001
>> "10000000 01000000 00100000 00010000 00001000 00000100 00000000 00000000"
                                                                ^         ^

Floating Points

The reason behind this behavior is the fact that numbers are stored as floating points! The best way to know what's the exact storage system is to look at the specifications:

The type Number is a set of values representing numbers. In ECMAScript, the set of values represents the double-precision 64-bit format IEEE 754 values including the special "Not-a-Number" (NaN) values, positive infinity, and negative infinity.

Source: ECMA 262 - 4.3.20 Number Type

Looking at Wikipedia we've got this table:

Total bits Sign Exponent Significand
64 1 11 52

If you don't know how floating point values are working, let me quick explain it to you. It's in fact really simple. You start with a normal unsigned integer, in this case of 52 bits. You shift it left or right with the value of the exponent, here stored on 11 bits. And if the sign bit is set, you mark it as negative. (This is a really simplistic view, but serve the purpose here!)

Example:

Significand: 1000 1100 1001, Exponent: 4, Sign: 1
 
- 1000 1100 1001 0000
                < <<<

As you can see, when the exponent is set, 0 are being added at the end of the number. This is the source of our precision loss.

Maximum Integer

With this in mind we can guess the biggest number that does not suffer from this. We have to fill the significand with 1, set the exponent to 0 and the sign to 0. It is the number 253-1.

Significand: 111..111 ~ 52, Exponent: 0, Sign: 0
 
  1111 1111 .... 1111 = 2 ^ 53 - 1

Now let's see what happen if we want to write 253.

Significand: 100..000 ~ 52, Exponent: 1, Sign: 0
 
1 0000 0000 .... 0000 = 2 ^ 53
                    <

It still works due to the fact that the least significant bit is set to 0 during the shift. However this is impossible to write 253+1, the next number we can write is 253+2!

Significand: 100..001 ~ 52, Exponent: 1, Sign: 0
 
1 0000 0000 .... 0010 = 2 ^ 53 + 2
                    <

When Trouble Arises!

Finally, we can provide the first example such as n == n + 1!

Math.pow(2, 53) == Math.pow(2, 53) + 1
>> true

You should take care using traditional loops with big numbers, they will go infinite after that maximum integer value.

// WARNING: DO NOT TRY THIS AT HOME!
 
var MAX_INT = Math.pow(2, 53); // 9 007 199 254 740 992
for (var i = MAX_INT; i < MAX_INT + 2; ++i) {
  // infinite loop
}

Conclusion

The integer part of the Number type in Javascript is safe in [-253 .. 253] (253 = 9 007 199 254 740 992). Beyond this there will be precision loss on the least significant numbers.

If you want to use bigger integers there are several options:

  • String: if you don't want to perform arithmetic operations on them.
  • Combine Multiple Numbers: One number gives you 52 bits of precision. It's possible to use an array of them to achieve the precision you need. See Closure Long (Int64) and Leemon Big Integer for examples.
If you liked this article, you might be interested in my Twitter feed as well.
 
 

Related Posts

  • September 25, 2011 Javascript Object Difference (5)
    This article is about a difference algorithm. It extracts changes from one version of an object to another. It helps storing a smaller amount of information. Template In a project, I have a template object with all the default settings for a widget. var template = { achievement: { ...
  • October 26, 2011 Javascript Presentation – Slides & Video (2)
    I've done the Javascript presentation. It went alright and I hope that I taught things to people. I'm sorry for my blog reader but it's in French :) Few remarks: The code in the slide was not big enough, people in the back couldn't read it. It also appears crappy in the video. I allo...
  • August 29, 2011 Javascript: Improve Cache Performance: Reduce Lookups (2)
    In my Binary Decision Diagram Library, the performance bottleneck was the uniqueness cache. By reducing the number of cache lookup, it is possible to greatly improve the performances. Common pattern In order to test if the key is already in the cache, the usual pattern is to use key in cache....
  • September 11, 2011 WebGL – Julia 3D Representation (0)
    At school we've been studying Lie Algebra and we were asked to make a 3D representation of a Lie Group. We chose to represent Julia Set in the Quaternion domain. We were really impressed to see that it was possible to generate many different forms given such a simple equation. Feel...
  • November 4, 2013 Bitwise Truthiness (0)
    In this blog post, I explore another form of truthiness in Javascript. What happens if you use a bitwise operator on a value like 0|value or ~~value. Context We recently turned on the JSHint bitwise rule by default and the following code was caught. var isValid = false; for (var i = 0...