195

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?

29
  • 36
    you need this: php.net/manual/en/book.bc.php , or else wou will bash your head against IEEE 754 till hell freezes over.
    – tereško
    Aug 4, 2013 at 18:49
  • 5
    For handling large numbers in PHP (i.e. 64-bit), use the GMP functions, in this case gmp_add().
    – Jeffrey
    Aug 4, 2013 at 22:11
  • 113
    For super efficiency, your loops should really start at 1 instead of 0. :P Aug 4, 2013 at 23:27
  • 55
    sum(1 to N) = (N/2)*(N+1)
    – Phong
    Aug 5, 2013 at 0:42
  • 5
    @Baba 0 is superflous for your calculation, so there's no need to have an extra iteration of the loop to add 0 to 0. Aug 5, 2013 at 11:29

36 Answers 36

155
+100

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
7
  • Did you run this on 32 or 64 bit system ?
    – Baba
    Aug 4, 2013 at 19:29
  • 4
    It should work regardless (32 vs 64 bit) since Python ints auto promote to arbitrary precision rather than overflow. Might take a while longer tho.
    – dawg
    Aug 4, 2013 at 19:36
  • 3
    Python on any system will work in this case, since Python switches to long integers automatically if needed. And if that's not enough, it will switch to big integers as well. Aug 4, 2013 at 19:37
  • 12
    @0x499602D2: That is kinda harsh. The OP himself voted it up. He asked specifically if this was similar problem on Python. Answer, no it is not. Code to show that it is not. WTH?
    – dawg
    Aug 4, 2013 at 19:50
  • 10
    The Python example is overly long, just use sum(xrange(int(1e9)+1)) (....sum works on iterables)
    – Jay M
    Aug 4, 2013 at 20:09
101

Your Go code uses integer arithmetic with enough bits to give an exact answer. Never touched PHP or Node.js, but from the results I suspect the math is done using floating point numbers and should be thus expected not to be exact for numbers of this magnitude.

15
  • 47
    Yep. If PHP encounters a number beyond the bounds of the integer type, it will be interpreted as a float instead. Also, an operation which results in a number beyond the bounds of the integer type will return a float instead. - php.net/manual/en/language.types.integer.php
    – Nate
    Aug 4, 2013 at 19:54
  • 3
    And in NodeJS (and JavaScript in general) all arithmetic operations (except bit operations) behave as if they were done with floating point numbers. Whether or not they actually are is an under-the-hood distinction subject to the decisions of individual JavaScript engines. Aug 4, 2013 at 21:02
  • 13
    In javascript's specification, there's no integer types. All numbers are floating points. Aug 4, 2013 at 22:27
  • 8
    @grasGendarme There are. The ES5 spec specifies various integer conversions and mandates that they be called in bitwise shifts, for example. That is to say behind the scenes, integers types are used in Javascript, but all the arithmetic operators convert their operands to floating point numbers before doing anything with them (barring compiler optimizations). Aug 5, 2013 at 1:40
  • 2
    here is the code i guess its messed up because i used float64 and not int64 .. Just confirmed it has nothing to do with 32 or 64 bits
    – Baba
    Aug 12, 2013 at 13:03
46

The reason is that the value of your integer variable sum exceeds the maximum value. And the sum you get is result of float-point arithmetic which involves rounding off. Since other answers did not mention the exact limits, I decided to post it.

The max integer value for PHP for:

  • 32-bit version is 2147483647
  • 64-bit version is 9223372036854775807

So it means either you are using 32 bit CPU or 32 bit OS or 32 bit compiled version of PHP. It can be found using PHP_INT_MAX. The sum would be calculated correctly if you do it on a 64 bit machine.

The max integer value in JavaScript is 9007199254740992. The largest exact integral value you can work with is 253 (taken from this question). The sum exceeds this limit.

If the integer value does not exceed these limits, then you are good. Otherwise you will have to look for arbitrary precision integer libraries.

0
28

Here is the answer in C, for completeness:

#include <stdio.h>

int main(void)
{
    unsigned long long sum = 0, i;

    for (i = 0; i <= 1000000000; i++)    //one billion
        sum += i;

    printf("%llu\n", sum);  //500000000500000000

    return 0;
}

The key in this case is using C99's long long data type. It provides the biggest primitive storage C can manage and it runs really, really fast. The long long type will also work on most any 32 or 64-bit machine.

There is one caveat: compilers provided by Microsoft explicitly do not support the 14 year-old C99 standard, so getting this to run in Visual Studio is a crapshot.

13
  • 3
    MSVC++ is a C++ compiler, and C++ got long long in the C++11 standard. It's been a MSVC++ and g++ extension for a few years, though.
    – MSalters
    Aug 5, 2013 at 10:11
  • 1
    @MSalters So being a C++ feature it won't really help anyone compiling a straight C program. I never tried switching from C to C++, so I don't know if that workaround would actually work.
    – CyberSkull
    Aug 5, 2013 at 12:23
  • 19
    And nicely, GCC or Clang with optimizations turn the whole loop into movabsq $500000000500000000, %rsi Aug 5, 2013 at 12:59
  • 3
    Just gcc -O3 or clang -O3. I don't know the name of the specific optimization. Basically the compiler notices that the result of the loop does not depend on any argument, and calculates it at compile time. Aug 5, 2013 at 13:25
  • 1
    C99 long long has a minimum size of 64 bits and as far as I know is 64 bit on both 32-bit and 64-bit platforms. I haven't seen general support for quad or octo ints.
    – Devin Lane
    Aug 5, 2013 at 17:37
21

My guess is that when the sum exceeds the capacity of a native int (231-1 = 2,147,483,647), Node.js and PHP switch to a floating point representation and you start getting round-off errors. A language like Go will probably try to stick with an integer form (e.g., 64-bit integers) as long as possible (if, indeed, it didn't start with that). Since the answer fits in a 64-bit integer, the computation is exact.

4
  • Node.js explicitly does not have an int type. It's working in a float type.
    – greyfade
    Aug 7, 2013 at 2:40
  • @greyfade - Yeah, I guess that's true of all EcmaScript-compliant environments.
    – Ted Hopp
    Aug 7, 2013 at 4:37
  • Isn’t that (2**31 - 1)? Sep 20, 2019 at 15:32
  • @ZacharyHunter - Indeed it is. Thanks for catching that error.
    – Ted Hopp
    Sep 20, 2019 at 17:53
19

Perl script give us the expected result:

use warnings;
use strict;

my $sum = 0;
for(my $i = 0; $i <= 1_000_000_000; $i++) {
    $sum += $i;
}
print $sum, "\n";  #<-- prints: 500000000500000000
5
  • 3
    Did you run this on 32 or 64 bit system ?
    – Baba
    Aug 4, 2013 at 19:22
  • 2
    it was executed on 64 bits system
    – Miguel Prz
    Aug 4, 2013 at 20:16
  • 3
    4.99999999067109e+017 on Perl v5.16.1 MSWin32-x86.
    – Qtax
    Aug 4, 2013 at 22:57
  • 7
    If you really need big numbers, use the bignum or bigint. Both are core modules, that is, they are install with Perl v5.8.0 or higher. See http://perldoc.perl.org/bignum.html and http://perldoc.perl.org/bigint.html Aug 4, 2013 at 23:20
  • I got 500000000500000000 running this on a 32-bit PPC Mac, running Perl 5.12.4.
    – CyberSkull
    Aug 4, 2013 at 23:39
18

The Answer to this is "surprisingly" simple:

First - as most of you might know - a 32-bit integer ranges from −2,147,483,648 to 2,147,483,647. So, what happens if PHP gets a result, that is LARGER than this?

Usually, one would expect a immediate "Overflow", causing 2,147,483,647 + 1 to turn into −2,147,483,648. However, that is NOT the case. IF PHP Encounters a larger number, it Returns FLOAT instead of INT.

If PHP encounters a number beyond the bounds of the integer type, it will be interpreted as a float instead. Also, an operation which results in a number beyond the bounds of the integer type will return a float instead.

http://php.net/manual/en/language.types.integer.php

This said, and knowing that PHP FLOAT implementation is following the IEEE 754 double precision Format, means, that PHP is able to deal with numbers upto 52 bit, without loosing precision. (On a 32-bit System)

So, at the Point, where your Sum hits 9,007,199,254,740,992 (which is 2^53) The Float value returned by the PHP Maths will no longer be precise enough.

E:\PHP>php -r "$x=bindec(\"100000000000000000000000000000000000000000000000000000\"); echo number_format($x,0);"

9,007,199,254,740,992

E:\PHP>php -r "$x=bindec(\"100000000000000000000000000000000000000000000000000001\"); echo number_format($x,0);"

9,007,199,254,740,992

E:\PHP>php -r "$x=bindec(\"100000000000000000000000000000000000000000000000000010\"); echo number_format($x,0);"

9,007,199,254,740,994

This example Shows the Point, where PHP is loosing precision. First, the last significatn bit will be dropped, causing the first 2 expressions to result in an equal number - which they aren't.

From NOW ON, the whole math will go wrong, when working with default data-types.

•Is it the same problem for other interpreted language such as Python or Perl?

I don't think so. I think this is a problem of languages that have no type-safety. While a Integer Overflow as mentioned above WILL happen in every language that uses fixed data types, the languages without type-safety might try to catch this with other datatypes. However, once they hit their "natural" (System-given) Border - they might return anything, but the right result.

However, each language may have different threadings for such a Scenario.

15

The other answers already explained what is happening here (floating point precision as usual).

One solution is to use an integer type big enough, or to hope the language will chose one if needed.

The other solution is to use a summation algorithm that knows about the precision problem and works around it. Below you find the same summation, first with with 64 bit integer, then with 64 bit floating point and then using floating point again, but with the Kahan summation algorithm.

Written in C#, but the same holds for other languages, too.

long sum1 = 0;
for (int i = 0; i <= 1000000000; i++)
{
    sum1 += i ;
}
Console.WriteLine(sum1.ToString("N0"));
// 500.000.000.500.000.000

double sum2 = 0;
for (int i = 0; i <= 1000000000; i++)
{
    sum2 += i ;
}
Console.WriteLine(sum2.ToString("N0"));
// 500.000.000.067.109.000

double sum3 = 0;
double error = 0;
for (int i = 0; i <= 1000000000; i++)
{
    double corrected = i - error;
    double temp = sum3 + corrected;
    error = (temp - sum3) - corrected;
    sum3 = temp;
}
Console.WriteLine(sum3.ToString("N0"));
//500.000.000.500.000.000

The Kahan summation gives a beautiful result. It does of course take a lot longer to compute. Whether you want to use it depends a) on your performance vs. precision needs, and b) how your language handles integer vs. floating point data types.

2
  • @Baba It's the same as with Node.js/JavaScript in the OP. As to why 500000000067109000 vs. 500000000067108992 … no idea.
    – linac
    Aug 5, 2013 at 12:09
  • Perhaps Baba is intrigued by the use of dots for thousand separators: english usually expects commas. You could also use underscores as a more neutral mean.
    – didierc
    Aug 5, 2013 at 20:23
14

If you have 32-Bit PHP, you can calculate it with bc:

<?php

$value = 1000000000;
echo bcdiv( bcmul( $value, $value + 1 ), 2 );
//500000000500000000

In Javascript you have to use arbitrary number library, for example BigInteger:

var value = new BigInteger(1000000000);
console.log( value.multiply(value.add(1)).divide(2).toString());
//500000000500000000

Even with languages like Go and Java you will eventually have to use arbitrary number library, your number just happened to be small enough for 64-bit but too high for 32-bit.

12

In Ruby:

sum = 0
1.upto(1000000000).each{|i|
  sum += i
}
puts sum

Prints 500000000500000000, but takes a good 4 minutes on my 2.6 GHz Intel i7.


Magnuss and Jaunty have a much more Ruby solution:

1.upto(1000000000).inject(:+)

To run a benchmark:

$ time ruby -e "puts 1.upto(1000000000).inject(:+)"
ruby -e "1.upto(1000000000).inject(:+)"  128.75s user 0.07s system 99% cpu 2:08.84 total
2
  • 10
    1.upto(1000000000).inject(:+)
    – Magnuss
    Aug 5, 2013 at 17:36
  • @Magnuss : That's what I thought I tried at first, but it caused a massive memory leak. Yours seems to work...
    – cgenco
    Aug 5, 2013 at 17:59
11

I use node-bigint for big integer stuff:
https://github.com/substack/node-bigint

var bigint = require('bigint');
var sum = bigint(0);
for(var i = 0; i <= 1000000000; i++) { 
  sum = sum.add(i); 
}
console.log(sum);

It's not as quick as something that can use native 64-bit stuff for this exact test, but if you get into bigger numbers than 64-bit, it uses libgmp under the hood, which is one of the faster arbitrary precision libraries out there.

4

took ages in ruby, but gives the correct answer:

(1..1000000000).reduce(:+)
 => 500000000500000000 
4

To get the correct result in php I think you'd need to use the BC math operators: http://php.net/manual/en/ref.bc.php

Here is the correct answer in Scala. You have to use Longs otherwise you overflow the number:

println((1L to 1000000000L).reduce(_ + _)) // prints 500000000500000000
0
3

There's actually a cool trick to this problem.

Assume it was 1-100 instead.

1 + 2 + 3 + 4 + ... + 50 +

100 + 99 + 98 + 97 + ... + 51

= (101 + 101 + 101 + 101 + ... + 101) = 101*50

Formula:

For N= 100: Output = N/2*(N+1)

For N = 1e9: Output = N/2*(N+1)

This is much faster than looping through all of that data. Your processor will thank you for it. And here is an interesting story regarding this very problem:

http://www.jimloy.com/algebra/gauss.htm

1
  • 11
    Do you think it might be possible to walk across every bridge across the Pregel in Kaliningrad, without crossing any bridge twice? Many people have tried and failed, but no-one has yet established that it is impossible. This seems like a challenge you would be uniquely qualified to solve.
    – jwg
    Aug 5, 2013 at 11:36
3

This gives the proper result in PHP by forcing the integer cast.

$sum = (int) $sum + $i;
0
3

Common Lisp is one of the fastest interpreted* languages and handles arbitrarily large integers correctly by default. This takes about 3 second with SBCL:

* (time (let ((sum 0)) (loop :for x :from 1 :to 1000000000 :do (incf sum x)) sum))

Evaluation took:
  3.068 seconds of real time
  3.064000 seconds of total run time (3.044000 user, 0.020000 system)
  99.87% CPU
  8,572,036,182 processor cycles
  0 bytes consed

500000000500000000
  • By interpreted, I mean, I ran this code from the REPL, SBCL may have done some JITing internally to make it run fast, but the dynamic experience of running code immediately is the same.
3
  • Can be simplified as (time (loop for x from 1 to 1000000000 sum x)). I got ~5x speed by adding declaration: (time (locally (declare (optimize (speed 3) (safety 0))) (loop for i of-type fixnum from 1 to 1000000000 sum i of-type fixnum)))
    – huaiyuan
    Aug 5, 2013 at 20:29
  • This is erroneous. Don't let you be blinded by the other languages! The correct way to write it in lisp is: (defun sum-from-1-to-n (n) (/ (* n (1+ n)) 2)) (time (sum-from-1-to-n 1000000000)) took 14 microseconds (0.000014 seconds) to run. During that period, and with 4 available CPU cores, 0 microseconds (0.000000 seconds) were spent in user mode 0 microseconds (0.000000 seconds) were spent in system mode --> 500000000500000000 Aug 6, 2013 at 8:26
  • @informatimago : It's not erroneous. I was copying the imperative loop style of the question and as many have pointed out, the question itself mentions there is an easier way to calculate. Chillax. Aug 6, 2013 at 17:23
3

I don't have enough reputation to comment on @postfuturist's Common Lisp answer, but it can be optimized to complete in ~500ms with SBCL 1.1.8 on my machine:

CL-USER> (compile nil '(lambda () 
                        (declare (optimize (speed 3) (space 0) (safety 0) (debug 0) (compilation-speed 0))) 
                        (let ((sum 0))
                          (declare (type fixnum sum))
                          (loop for i from 1 to 1000000000 do (incf sum i))
                          sum)))
#<FUNCTION (LAMBDA ()) {1004B93CCB}>
NIL
NIL
CL-USER> (time (funcall *))
Evaluation took:
  0.531 seconds of real time
  0.531250 seconds of total run time (0.531250 user, 0.000000 system)
  100.00% CPU
  1,912,655,483 processor cycles
  0 bytes consed

500000000500000000
3

Racket v 5.3.4 (MBP; time in ms):

> (time (for/sum ([x (in-range 1000000001)]) x))
cpu time: 2943 real time: 2954 gc time: 0
500000000500000000
1
  • 1
    Deleted my answer posted 6 minutes after you, once I noticed yours. :) Aug 5, 2013 at 19:10
3

Works fine in Rebol:

>> sum: 0
== 0

>> repeat i 1000000000 [sum: sum + i]
== 500000000500000000

>> type? sum
== integer!

This was using Rebol 3 which despite being 32 bit compiled it uses 64-bit integers (unlike Rebol 2 which used 32 bit integers)

3

I wanted to see what happened in CF Script

<cfscript>
ttl = 0;

for (i=0;i LTE 1000000000 ;i=i+1) {
    ttl += i;
}
writeDump(ttl);
abort;
</cfscript>

I got 5.00000000067E+017

This was a pretty neat experiment. I'm fairly sure I could have coded this a bit better with more effort.

3

ActivePerl v5.10.1 on 32bit windows, intel core2duo 2.6:

$sum = 0;
for ($i = 0; $i <= 1000000000 ; $i++) {
  $sum += $i;
}
print $sum."\n";

result: 5.00000000067109e+017 in 5 minutes.

With "use bigint" script worked for two hours, and would worked more, but I stopped it. Too slow.

1
  • Can anyone confirm that that's really how long adding that many bigints takes?
    – jwg
    Aug 6, 2013 at 8:21
3

For the sake of completeness, in Clojure (beautiful but not very efficient):

(reduce + (take 1000000000 (iterate inc 1))) ; => 500000000500000000
2
  • 1
    The only tiny bit of useful that the $MY_FAVOURITE_LANGUAGE answers have is if they provide the result...
    – jwg
    Aug 6, 2013 at 8:21
  • @jwg yeah sorry I missed the end of the line -- updated answer.
    – Blacksad
    Aug 6, 2013 at 13:24
3

AWK:

BEGIN { s = 0; for (i = 1; i <= 1000000000; i++) s += i; print s }

produces the same wrong result as PHP:

500000000067108992

It seems AWK uses floating point when the numbers are really big, so at least the answer is the right order-of-magnitude.

Test runs:

$ awk 'BEGIN { s = 0; for (i = 1; i <= 100000000; i++) s += i; print s }'
5000000050000000
$ awk 'BEGIN { s = 0; for (i = 1; i <= 1000000000; i++) s += i; print s }'
500000000067108992
2

Category other interpreted language:

Tcl:

If using Tcl 8.4 or older it depends if it was compiled with 32 or 64 bit. (8.4 is end of life).

If using Tcl 8.5 or newer which has arbitrary big integers, it will display the correct result.

proc test limit {
    for {set i 0} {$i < $limit} {incr i} {
        incr result $i
    }
    return $result
}
test 1000000000 

I put the test inside a proc to get it byte-compiled.

2

For the PHP code, the answer is here:

The size of an integer is platform-dependent, although a maximum value of about two billion is the usual value (that's 32 bits signed). 64-bit platforms usually have a maximum value of about 9E18. PHP does not support unsigned integers. Integer size can be determined using the constant PHP_INT_SIZE, and maximum value using the constant PHP_INT_MAX since PHP 4.4.0 and PHP 5.0.5.

2

Harbour:

proc Main()

   local sum := 0, i

   for i := 0 to 1000000000
      sum += i
   next

   ? sum

   return

Results in 500000000500000000. (on both windows/mingw/x86 and osx/clang/x64)

2

Erlang works:

from_sum(From,Max) ->
    from_sum(From,Max,Max).
from_sum(From,Max,Sum) when From =:= Max ->
    Sum;
from_sum(From,Max,Sum) when From =/= Max -> 
    from_sum(From+1,Max,Sum+From).

Results: 41> useless:from_sum(1,1000000000). 500000000500000000

2

Funny thing, PHP 5.5.1 gives 499999999500000000 (in ~ 30s), while Dart2Js gives 500000000067109000 (which is to be expected, since it's JS that gets executed). CLI Dart gives the right answer ... instantly.

2

Erlang gives the expected result too.

sum.erl:

-module(sum).
-export([iter_sum/2]).

iter_sum(Begin, End) -> iter_sum(Begin,End,0).
iter_sum(Current, End, Sum) when Current > End -> Sum;
iter_sum(Current, End, Sum) -> iter_sum(Current+1,End,Sum+Current).

And using it:

1> c(sum).
{ok,sum}
2> sum:iter_sum(1,1000000000).
500000000500000000
2

Smalltalk:

(1 to: 1000000000) inject: 0 into: [:subTotal :next | subTotal + next ]. 

"500000000500000000"

Not the answer you're looking for? Browse other questions tagged or ask your own question.