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

我试图得到 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

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

去吧

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

但是它工作得很好! 那么我的 PHP 和 Node.js 代码有什么问题吗？

也许这是一个解释语言的问题，这就是为什么它在围棋这样的编译语言中起作用的原因？如果是这样，其他解释语言(如 Python 和 Perl)是否也存在同样的问题？

28612 次浏览
小开

您的 Go 代码使用带有足够位的整数算术来给出准确的答案。从未触及 PHP 或 Node.js，但从结果来看，我怀疑数学是使用 浮点数浮点数完成的，因此应该不会精确到这个数量级。

小开

Javascript (可能还有 PHP)将所有数字表示为 double，并将它们四舍五入为整数值。这意味着它们只有53位的精度(而不是 int64和 Java long 提供的64位) ，并且会导致对大值的舍入错误。

小开

我的猜测是，当总和超过本机 int(231-1 = 2,147,483,647)的容量时，Node.js 和 PHP 会切换到浮点表示，然后就会出现舍入错误。像 Go 这样的语言可能会尽可能长时间地坚持使用整数形式(例如，64位整数)(如果它确实没有以这种形式开始的话)。因为答案是一个64位整数，所以计算是精确的。

小开

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
小开

我用 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，这是目前最快的任意精度库之一。

小开

巨蟒的作品:

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

或者:

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

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

这可以通过将2提高到一个远大于平台位宽度的幂来看到:

>>> 2**99
633825300114114700748351602688L

您可以证明(使用 Python)在 PHP 中得到的错误值是因为当值大于2 * * 32-1时 PHP 正在提升为 float:

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

类别其他直译语言:

翻译:

如果使用 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

我将测试放在一个处理程序中，以便对它进行字节编译。

小开

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

<?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位来说太高了。

小开

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

假设是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

小开

以下是 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数据类型。它提供了 C 所能管理的最大的基本存储空间，而且它运行得非常快，真的。long long类型也适用于大多数32位或64位机器。

有一个警告: 微软提供的编译器显然不支持已有14年历史的 C99标准，因此让它在 Visual Studio 中运行是一件很麻烦的事情。

小开

对于 PHP 代码，答案是 给你:

整数的大小依赖于平台，尽管最大值约为20亿是通常的值(即32位有符号)。64位平台的最大值通常为9E18左右。PHP 不支持无符号整数。可以使用常量 PHP _ INT _ SIZE 确定整数大小，并使用 PHP 4.4.0和 PHP 5.0.5以来的常量 PHP _ INT _ MAX 确定最大值。

小开

其他的答案已经解释了这里发生的情况(浮点精度和往常一样)。

一种解决方案是使用一个足够大的整数类型，或者希望语言在需要时会选择一个。

另一种解决方案是使用一种求和算法，这种算法了解精度问题并能够解决这个问题。下面你会发现相同的求和，首先是64位整数，然后是64位浮点数，然后再次使用浮点数，但是使用的是 Kahan 求和算法。

是用 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

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

小开

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

PHP for 的最大整数值:

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

因此，这意味着您要么使用32位 CPU，要么使用32位操作系统，要么使用32位编译版本的 PHP。可以使用 PHP_INT_MAX找到它。如果在64位机器上计算，那么 sum将被正确计算。

JavaScript 中的最大整数值是 9007199254740992。您可以使用的最大精确整数值是253(取自此 有个问题)。sum超过了这个限制。

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

小开

在 Ruby 中:

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

打印 500000000500000000，但在我的2.6 GHz 英特尔 i7上花了整整4分钟。

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

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
小开

在红宝石上花了很长时间，但给出了正确的答案:

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

这在 PHP 中通过强制整数强制转换得到了正确的结果。

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

海港:

proc Main()


local sum := 0, i


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


? sum


return

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

小开

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 可能在内部进行了一些 JIT 以使其快速运行，但是立即运行代码的动态体验是相同的。
小开

在 Ruby 中，与功能相似的解决方案(返回正确答案)完成这些任务所需的时间显著不同:

$ time ruby -e "(1..1000000000).inject{|sum, n| sum + n}"
real    1m26.005s
user    1m26.010s
sys 0m0.076s


$ time ruby -e "1.upto(1000000000).inject(:+)"
real    0m48.957s
user    0m48.957s
sys 0m0.045s


$ ruby -v
ruby 1.9.2p180 (2011-02-18 revision 30909) [x86_64-darwin10.8.0]
小开

要在 php 中得到正确的结果，我认为需要使用 BC 数学运算符: http://php.net/manual/en/ref.bc.php

下面是 Scala 中的正确答案。你必须使用 Long 否则会溢出数字:

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

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)。 500000000500000000000000000000000000000000000000000000000000000000000000000000

小开

球拍 v 5.3.4(MBP; 以毫秒为单位的时间) :

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

我没有足够的声誉来评论@postFuturist 的 Common Lisp 答案，但是它可以通过在我的机器上使用 SBCL 1.1.8优化到500毫秒内完成:

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
小开

有趣的是，PHP 5.5.1给出的是49999999500000000(大约30秒) ，而 Dart2J 给出的是5000000000067109000(这是意料之中的，因为执行的是 JS)。CLI Dart 马上给出了正确的答案。

小开

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
小开

在 Rebol 工作得很好:

>> sum: 0
== 0


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


>> type? sum
== integer!

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

小开

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

<cfscript>
ttl = 0;


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

我得到了5.0000000067 E + 017

这是一个相当巧妙的实验。我相当肯定，如果我再努力一点，我可以编写得更好一些。

小开

正如其他人指出的那样，进行这种计算的最快方法(不管使用什么语言)是使用一个简单的数学函数(而不是 CPU 密集型循环) :

number = 1000000000;
result = (number/2) * (number+1);

但是，您仍然需要解决任何32/64位整数/浮点数问题，这取决于语言。

小开

为了完整起见，在 Clojure 中(漂亮但效率不高) :

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

闲聊:

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


"500000000500000000"
小开

ActivePerl v5.10.1 on 32 bit windows，intelcore2do2.6:

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

结果: 5分钟内5.0000000067109 e + 017。

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

小开

还有红宝石的:

[15] pry(main)> (1..1000000000).inject(0) { |sum,e| sum + e }
=> 500000000500000000

好像打对了号码。

小开

仅供参考。

在 MATLAB 中，自动选择类型没有问题:

tic; ii = 1:1000000; sum(ii); toc; ans

运行时间为0.004471秒。
S = 5.000000000050000000e + 11

在 F # 交互式中，自动单元类型会出现溢出错误，赋值 int64类型会得到正确答案:

seq {int64 1.. int64 1000000} |> Seq.sum

val it : int64 = 500000500000L

备注:
可以使用 Seq.reduce (+)而不是 Seq.sum，效率没有明显的变化。但是，使用带有自动单元类型的 Seq.reduce (+)将得到错误的答案，而不是溢出错误。
计算时间是 < .5秒，但是我现在很懒，所以我没有导入。NET 秒表类获得更精确的时间。

小开

这个问题的答案“出人意料地”简单:

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

通常情况下，人们会期待一个立即“溢出”，导致 2,147,483,647 + 1变成 2,147,483,648。然而，事实并非如此。如果 PHP 遇到较大的数字，它返回 FLOAT 而不是 INT。

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

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

也就是说，知道 PHP FLOAT 实现遵循 IEEE 754双精度格式，意味着 PHP 能够处理高达52位的数字，而不会损失精度。(在32位系统上)

因此，在这一点上，您的和命中 9,007,199,254,740,992(即 2 ^ 53)的浮点数值返回的 PHP 数学将不再是足够精确。

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 正在失去精度的点。首先，最后一个有意义的位将被删除，导致前2个表达式得到一个相等的数字——它们不是。

从现在开始，当使用默认数据类型时，整个计算将出错。

• Python 或 Perl 等其它直译语言也存在同样的问题吗？

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

但是，对于这样的场景，每种语言可能有不同的线程。

小开

沃克:

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

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

500000000067108992

似乎 AWK 在数字非常大的时候使用浮点数，所以至少答案是正确的数量级。

试运行:

$ 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
小开

有几个答案已经解释了为什么 PHP 和 Node.js 代码不能像预期的那样工作，因此我在这里不再重复。我只是想指出，没什么与“解释语言与编译语言”有关。

也许这是一个解释语言的问题，这就是为什么它在围棋这样的编译语言中起作用的原因？

“语言”仅仅是一组定义良好的规则; 语言的 实施是解释或编译的内容。我可以选择一种主要实现是编译的语言(比如 Go) ，并为其编写一个解释器(反之亦然) ，但是解释器处理的每个程序都应该产生与通过编译实现运行程序相同的输出，并且这个输出应该符合该语言的规范。PHP 和 Node.js 的结果实际上符合语言的规范(正如其他一些回答所指出的) ，这与这些语言的主要实现被解释的事实无关; 根据定义，这些语言的编译实现也必须产生相同的结果。

Python 就是一个切实的例子，它具有广泛使用的编译和解释实现。在解释实现中运行程序的翻译版本:

>>> total = 0
>>> for i in xrange(1000000001):
...     total += i
...
>>> print total
500000000500000000

通过 Python 的 定义，不能产生与在编译实现中运行它不同的输出:

total = 0
for i in xrange(1000000001):
total += i


print total

500000000500000000

提交答案