Unexpected results when working with very big integers on interpreted languages

Baba picture Baba · Aug 4, 2013 · Viewed 28k times · Source

I am trying to get the sum of 1 + 2 + ... + 1000000000, but I'm getting funny results in PHP and Node.js.

PHP

$sum = 0;
for($i = 0; $i <= 1000000000 ; $i++) {
    $sum += $i;
}
printf("%s", number_format($sum, 0, "", ""));   // 500000000067108992

Node.js

var sum = 0;
for (i = 0; i <= 1000000000; i++) {
    sum += i ;
}
console.log(sum); // 500000000067109000

The correct answer can be calculated using

1 + 2 + ... + n = n(n+1)/2

Correct answer = 500000000500000000, so I decided to try another language.

GO

var sum , i int64
for i = 0 ; i <= 1000000000; i++ {
    sum += i
}
fmt.Println(sum) // 500000000500000000

But it works fine! So what is wrong with my PHP and Node.js code?

Perhaps this a problem of interpreted languages, and that's why it works in a compiled language like Go? If so, would other interpreted languages such as Python and Perl have the same problem?

Answer

dawg picture dawg · Aug 4, 2013

Python works:

>>> sum(x for x in xrange(1000000000 + 1))
500000000500000000

Or:

>>> sum(xrange(1000000000+1))
500000000500000000

Python's int auto promotes to a Python long which supports arbitrary precision. It will produce the correct answer on 32 or 64 bit platforms.

This can be seen by raising 2 to a power far greater than the bit width of the platform:

>>> 2**99
633825300114114700748351602688L

You can demonstrate (with Python) that the erroneous values you are getting in PHP is because PHP is promoting to a float when the values are greater than 2**32-1:

>>> int(sum(float(x) for x in xrange(1000000000+1)))
500000000067108992