在解释语言上使用非常大的整数时，会产生意想不到的结果。

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

我想求1 + 2 +的和。+ 1000000000，但是我在PHP和Node.js中得到了有趣的结果。

PHP

PHP

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

Node.js

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.

正确答案= 500000000000000，所以我决定尝试另一种语言。

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?

但它工作正常!PHP和节点有什么问题。js代码?

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?

也许这是解释语言的一个问题，这就是为什么它在像Go这样的编译语言中工作?如果是这样，其他解释语言(如Python和Perl)是否也会遇到同样的问题?

36 个解决方案

#1

Python works:

Python的作品:

>>> 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.

Python的int auto升级为Python long，支持任意精度。它将在32或64位平台上生成正确的答案。

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

这可以通过将2提升到远高于平台位宽的功率来体现:

>>> 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:

您可以(通过Python)演示在PHP中遇到的错误值，因为当值大于2* 32-1时，PHP将提升为浮点数:

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

#2

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.

你的Go代码使用整数算法，有足够的比特来给出精确的答案。从未接触过PHP或节点。但是，从结果来看，我怀疑数学是用浮点数算出来的，因此，对于这样大小的数字，不应该期望是精确的。

#3

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:

PHP的最大整数值为:

• 32-bit version is 2147483647
• 32位版本是2147483647
• 64-bit version is 9223372036854775807
• 64位版本是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.

这意味着你要么使用32位CPU，要么32位操作系统或32位编译版本的PHP。可以使用PHP_INT_MAX找到它。如果你在64位机器上做的话，这个和就会被正确地计算出来。

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

JavaScript的最大整数值是9007199254740992。你能算出的最大的整数值是253(从这个问题中得出)。这笔款子超过了这个限额。

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

如果整型值不超过这些限制，那么就很好。否则，您将不得不寻找任意的精度整数库。

#4

Here is the answer in C, for completeness:

这里是C的答案，为了完整:

#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.

在这种情况下，关键是使用C99的长数据类型。它提供了C可以管理的最大的原始存储，运行速度非常非常快。长长类型也适用于大多数32位或64位机器。

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.

有一点需要注意:Microsoft提供的编译器明确地不支持已有14年历史的C99标准，因此在Visual Studio中运行这个标准是一个大问题。

#5

My guess is that when the sum exceeds the capacity of a native int (2³²-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.

我的猜测是，当总和超过了本机int的容量(232-1 = 2,147,483,647)时，节点。js和PHP切换到浮点表示法，您将开始获得舍入错误。像Go这样的语言可能会尽可能长时间地使用整数形式(例如64位整数)(如果它不是从整数开始的话)。因为答案是一个64位整数，所以计算是准确的。

#6

Perl script give us the expected result:

Perl脚本给出了预期的结果:

use warnings;
use strict;

my $sum = 0;
for(my $i = 0; $i <= 1_000_000_000; $i++) {
    $sum += $i;
}
print $sum, "\n";  #<-- prints: 500000000500000000

#7

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?

第一,你可能知道,一个32位整数的大多数−2147483648到2147483647不等。如果PHP得到一个大于这个的结果会怎样?

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.

通常,一个期望立即“溢出”,导致变成−2147483647 + 2147483647。然而，事实并非如此。如果PHP遇到较大的数字，它将返回FLOAT而不是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.

如果PHP遇到一个超出整数类型界限的数字，它将被解释为浮点数。此外，如果操作的结果超出整数类型的界限，则返回一个浮点数。

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

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)

这说明，并且知道PHP浮动实现遵循IEEE 754双精度格式，这意味着PHP能够处理52位的数字，而不会失去精度。(在32位系统上)

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.

在这一点,你的金额达到9007199254740992(2 ^ 53)返回的浮动值PHP数学将不再是足够精确的。

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

9,007,199,254,740,992

9007199254740992年

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

9,007,199,254,740,992

9007199254740992年

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

9,007,199,254,740,994

9007199254740994年

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.

这个示例展示了PHP失去精度的地方。首先，最后一个有意义的位将被删除，导致前两个表达式的结果是一个相等的数字，但它们不是。

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?

•其他解释语言(如Python或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.

然而，每种语言对于这样的场景可能有不同的解读。

#8

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.

另一个解决方案是使用一个知道精度问题并围绕它工作的求和算法。下面是相同的求和，首先是64位整型，然后是64位浮点型，然后再用浮点型，不过是用Kahan求和算法。

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

用c#编写，但其他语言也是如此。

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.

卡罕的总结给出了一个美丽的结果。当然，它需要更长的时间来计算。是否要使用它取决于a)性能和精度需求，b)语言如何处理整数和浮点数据类型。

#9

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

如果你有32位的PHP，你可以用bc来计算:

<?php

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

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

在Javascript中，你必须使用任意的数字库，例如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.

即使是像Go和Java这样的语言，你最终也必须使用任意的数字库，你的数字刚好足够小到64位，但是对于32位来说太高了。

#10

In Ruby:

在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.

打印500000000500000000，但在我的2.6 GHz Intel i7上花了4分钟。

---

Magnuss and Jaunty have a much more Ruby solution:

Magnuss和Jaunty有一个更Ruby的解决方案:

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

#11

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

我使用node-bigint做大整数:https://github.com/substack/nodebigint。

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.

它的速度不如使用本地64位代码的测试快，但是如果您使用比64位更大的数字，它会在底层使用libgmp，这是比较快的任意精度库之一。

#12

took ages in ruby, but gives the correct answer:

在ruby中花了很长时间，但给出了正确的答案:

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

#13

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

要在php中得到正确的结果，我认为您需要使用BC数学运算符: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:

这是Scala的正确答案。你必须使用Longs，否则你会溢出数字:

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

#14

There's actually a cool trick to this problem.

这个问题有一个很酷的技巧。

Assume it was 1-100 instead.

假设是1-100。

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

1 + 2 + 3 + 4 +…+ 50 +

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

100 + 99 + 98 + 97 +…+ 51

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

=(101 + 101 + 101 + 101 + 101 +…)+ 101)= 101 * 50

Formula:

公式:

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

N= 100:输出= N/2*(N+1)

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

对于N = 1e9:输出= 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

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

#15

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

Common Lisp是最快的解释*语言之一，默认情况下可以正确地处理任意大的整数。使用SBCL大约需要3秒:

* (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.
• 通过解释，我的意思是，我从REPL运行了这段代码，SBCL可能在内部做了一些JITing操作以使它运行得更快，但是立即运行代码的动态体验是一样的。

#16

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:

我没有足够的声誉去评论@ post未来主义者的常见的Lisp答案，但是我的机器上有SBCL 1.1.8，它可以在~500ms内完成:

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

#17

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).

如果使用Tcl 8.4或更高版本，则取决于它是用32位还是64位编译的。(8.4是生命的终结)。

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

如果使用具有任意大整数的Tcl 8.5或更新版本，它将显示正确的结果。

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.

我把测试放在一个proc中，以得到它的字节编译。

#18

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

通过强制执行整数转换，这将给PHP带来适当的结果。

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

#19

Racket v 5.3.4 (MBP; time in ms):

球拍v 5.3.4(MBP;在女士):

> (time (for/sum ([x (in-range 1000000001)]) x))
cpu time: 2943 real time: 2954 gc time: 0
500000000500000000

#20

Erlang gives the expected result too.

Erlang也给出了预期的结果。

sum.erl:

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

#21

Works fine in Rebol:

在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)

这是使用Rebol 3尽管它是32位编译的它使用64位整数(不像Rebol 2使用32位整数)

#22

I wanted to see what happened in CF Script

我想看看CF脚本中发生了什么

<cfscript>
ttl = 0;

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

I got 5.00000000067E+017

我得到了5.00000000067 e + 017

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

这是一个非常棒的实验。我敢肯定，如果再努力一点，我可以把它写得更好一点。

#23

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

ActivePerl v5.10.1在32位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.

结果:5.00000000067109e+017分钟。

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

使用“使用bigint”脚本可以工作两个小时，可以工作得更多，但是我停止了。太慢了。

#24

Smalltalk:

Smalltalk:

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

"500000000500000000"

#25

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

为了完整性起见，在Clojure中(美观但不是很有效):

(reduce + (take 1000000000 (iterate inc 1))) ; => 500000000500000000

#26

AWK:

AWK:

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

produces the same wrong result as PHP:

产生与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.

当数字很大时，AWK似乎使用了浮点数，所以至少答案是正确的数量级。

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

#27

For the PHP code, the answer is here:

对于PHP代码，答案是:

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.

一个整数的大小依赖于平台，尽管通常的值是20亿(即32位)。64位平台的最大值通常为9E18。PHP不支持无符号整数。可以使用常量PHP_INT_SIZE确定整数大小，并使用PHP 4.4.0和PHP 5.0.5之后使用常量PHP_INT_MAX来确定最大值。

#28

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)

结果在500000000500000000。(windows/mingw/x86和osx/clang/x64)

#29

Erlang works:

Erlang工作原理:

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

结果:41 >无用:from_sum(1 1000000000)。500000000500000000

#30

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.

有趣的是，PHP 5.5.1给出了499999999999500000000(在30到30之间)，而dar2js提供500000000067109000(这是可以预料的，因为它是被执行的JS)。CLI Dart给出了正确的答案……立即。