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"
^ ^ |
(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
< <<< |
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 |
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
< |
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
< |
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 |
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
} |
// 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.