在解释型语言中使用非常大的整数时会出现意外的结果

我试图得到1 + 2 + ... + 1000000000的总和，但是我在PHP和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 

正确的答案可以使用计算

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

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

走

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

但它工作正常！ 那么我的PHP和Node.js代码有什么问题？

也许这是一个解释语言的问题，这就是为什么它使用像Go这样的编译语言？ 如果是这样，其他解释型语言如Python和Perl会有同样的问题吗？

Answer 1

Python的作品：

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

要么：

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

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

这可以通过将2提高到比平台的位宽大得多的力量来看出：

 >>> 2**99 633825300114114700748351602688L 

你可以用Python演示一下你在PHP中得到的错误值是因为当值大于2时，PHP被提升为float ** 32-1：

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

Answer 2

你的Go代码使用整数算术和足够的位来给出确切的答案。 从来没有碰过PHP或者Node.js，但是从结果来看，我怀疑这个math是用浮点数来完成的，所以对于这个数值应该是不准确的。

Answer 3

原因是你的整数variablessum的值超过了最大值。 而你得到的sum就是浮点运算的结果，它涉及到四舍五入的结果。 由于其他答案没有提到确切的限制，我决定发布它。

PHP的最大整数值为：

• 32位版本是2147483647
• 64位版本是9223372036854775807

所以这意味着要么使用32位CPU或32位操作系统，要么使用32位PHP编译版本。 它可以使用PHP_INT_MAXfind。 如果你在64位的机器上完成， sum将被正确计算。

JavaScript中的最大整数值是9007199254740992 。 您可以使用的最大准确积分值是2 ⁵³ （取自此问题 ）。 sum超过这个限制。

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

Answer 4

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; } 

在这种情况下的关键是使用C99的 long long数据types。 它提供了C可以pipe理的最大的原始存储，而且运行真的很快。 long long型也可以在大多数32位或64位的机器上工作。

有一点需要注意的是：微软提供的编译器显然不支持14岁的C99标准，所以在Visual Studio中运行这个标准是一个不错的select。

Answer 5

我的猜测是，当总和超过本地int （2 ³² -1 = 2,147,483,647）的容量，Node.js和PHP切换到浮点表示，你开始得到舍入误差。 像Go这样的语言可能会尽可能长地使用整数forms（例如，64位整数）（如果它确实不是以此开始的话）。 由于答案符合64位整数，计算是确切的。

Answer 6

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 

Answer 7

对此的回答“令人惊讶”很简单：

首先，正如大多数人可能知道的那样，一个32位整数的范围是-2,147,483,648到2,147,483,647 。 那么，如果PHP得到一个结果会发生什么，比这更大？

通常会期望立即出现“溢出”，导致2,147,483,647 + 1变成-2,147,483,648 。 但是，情况并非如此。 如果PHP遇到一个更大的数字，它返回FLOAT而不是INT。

如果PHP遇到超出整数types范围的数字，它将被解释为float。 此外，导致超出整数types范围的数字的操作将返回一个浮点数。

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

这就是说，知道PHP FLOAT实现是遵循IEEE 754双精度格式，就是说，PHP能够处理高达52位的数字，而不会失去精度。 （在32位系统上）

所以，在点，你的总和点击9,007,199,254,740,992 （这是2 ^ 53 ）由PHPmath返回的浮点值将不再足够精确。

 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

这个例子显示了PHP在哪里丢失精度。 首先，最后一个有意义的位将被丢弃，导致前两个expression式产生相同的数字 – 而事实并非如此。

从现在开始，使用默认数据types时，整个math将出错。

•对于其他解释型语言（如Python或Perl）是否也有同样的问题？

我不这么认为。 我认为这是一个没有types安全的语言的问题。 虽然上面提到的整数溢出将会在使用固定数据types的每种语言中发生，但没有types安全性的语言可能会尝试用其他数据types来捕捉这种语言。 但是，一旦他们达到了“自然”（系统给定）边界，他们可能会返回任何东西，但结果是正确的。

但是，对于这种情况，每种语言可能有不同的线程。

Answer 8

其他的答案已经解释了这里发生了什么（像往常一样浮点精度）。

一种解决scheme是使用足够大的整数types，或者希望语言在需要时select一个。

另一个解决scheme是使用一个总结algorithm，了解精度问题并解决它。 下面你find相同的总和，首先与64位整数，然后与64位浮点，然后再次使用浮点，但与Kahan求和algorithm 。

用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 

卡汉总结给出了一个美丽的结果。 计算当然需要很长的时间。 是否要使用它取决于a）您的性能与精度需求，b）您的语言如何处理整数与浮点数据types。

Answer 9

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

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

在Javascript中，您必须使用任意数字库，例如BigInteger ：

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

即使使用Go和Java等语言，您最终也不得不使用任意数字库，但是您的编号恰巧足够小到64位，但是对于32位而言却是太高了。

Answer 10

在Ruby中：

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

打印500000000500000000 ，但我的2.6 GHz英特尔i7需要4分钟。

---

Magnuss和Jaunty有更多的Ruby解决scheme：

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

---

运行一个基准：

 $ 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 

Answer 11

我使用node-bigint作为大整数的东西：
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); 

它不像可以使用本机64位的东西那样快，但是如果你的数字大于64位，它使用libgmp，这是更快的任意精度库之一。

Answer 12

在ruby花了很多年，但给出了正确的答案：

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

Answer 13

为了在PHP中获得正确的结果，我想你需要使用BCmath运算符： http : //php.net/manual/en/ref.bc.php

这是在斯卡拉正确的答案。 你必须使用Longs否则你溢出的数字：

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

Answer 14

这个问题其实有一个很酷的窍门。

假设它是1-100。

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

100 + 99 + 98 + 97 + … + 51

=（101 + 101 + 101 + 101 + … + 101）= 101 * 50

式：

对于N = 100：输出= N / 2 *（N + 1）

对于N = 1e9：输出= N / 2 *（N + 1）

这比循环所有这些数据要快得多。 你的处理器会为你感谢。 关于这个问题，这里有一个有趣的故事：

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

Answer 15

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 

• 通过解释，我的意思是，我从REPL运行这个代码，SBCL可能在内部做了一些JITing，使其运行速度很快，但是立即运行代码的dynamic体验是一样的。

Answer 16

我没有足够的信誉来评论@ postfuturist的Common 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 

Answer 17

类别其他解释型语言：

TCL：

如果使用Tcl 8.4或更早版本，则取决于是否使用32位或64位编译。 （8.4是生命的尽头）。

如果使用Tcl 8.5或更新的任意大整数，它会显示正确的结果。

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

我把这个testing放在一个proc中，以便进行字节编译。

Answer 18

这通过强制整型强制转换在PHP中给出正确的结果。

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

Answer 19

球拍v 5.3.4（MBP;时间以毫秒为单位）：

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

Answer 20

Erlang也给出了预期的结果。

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

并使用它：

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

Answer 21

在Rebol工作正常：

 >> sum: 0 == 0 >> repeat i 1000000000 [sum: sum + i] == 500000000500000000 >> type? sum == integer! 

这是使用Rebol 3，尽pipe是32位编译它使用64位整数（不像Rebol 2使用32位整数）

Answer 22

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

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

我得到了5.00000000067E + 017

这是一个非常简洁的实验。 我相当肯定，我可以用更多的努力将这一点编码得更好一些。

Answer 23

32位Windows上的ActivePerl v5.10.1，intel core2duo 2.6：

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

结果：5分钟内5.00000000067109e + 017。

用“使用bigint”脚本工作了两个小时，工作会更多，但是我停了下来。 太慢了。

Answer 24

短暂聊天：

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

Answer 25

为了完整起见，在Clojure（漂亮但不是非常高效）：

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

Answer 26

AWK：

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

产生与PHP相同的错误结果：

 500000000067108992 

看起来AWK在数字真的很大时使用浮点数，所以至less答案是正确的数量级。

testing运行：

 $ 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 

Answer 27

对于PHP代码，答案在这里 ：

整数的大小是依赖于平台的，尽pipe最大值约为20亿是通常的值（这是32位的）。 64位平台的最大值通常约为9E18。 PHP不支持无符号整数。 整数大小可以使用常量PHP_INT_SIZE确定，最大值使用自PHP 4.4.0和PHP 5.0.5以来的常量PHP_INT_MAX。

Answer 28

港口：

 proc Main() local sum := 0, i for i := 0 to 1000000000 sum += i next ? sum return 

结果在500000000500000000 。 （在windows / mingw / x86和osx / clang / x64上）

Answer 29

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

结果：41>无用：from_sum（1,1000000000）。 500000000500000000

Answer 30

有趣的是，PHP 5.5.1给出了499999999500000000（约30秒），而Dart2Js给出了500000000067109000（这是可以预料的，因为它是JS被执行的）。 CLI Dart立即给出正确的答案。