php - 在解释语言上处理非常大的整数时出现意外结果

Question

我试图得到的总和1 + 2 + ... + 1000000000，但我在 PHP 和Node.js中得到了有趣的结果。

PHP

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

节点.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）会不会有同样的问题？

score 155 · Accepted Answer

Python 工作：

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

或者：

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

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

这可以通过将 2 提高到远大于平台位宽的幂来看出：

>>> 2**99
633825300114114700748351602688L

您可以（使用 Python）证明您在 PHP 中获得的错误值是因为当值大于 2**32-1 时 PHP 正在提升为浮点数：

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

score 101 · Accepted Answer

您的 Go 代码使用具有足够位数的整数运算来给出准确的答案。从未接触过 PHP 或 Node.js，但从结果来看，我怀疑数学是使用浮点数完成的，因此对于这种数量级的数字应该不准确。

score 45 · Accepted Answer

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

PHP 的最大整数值：

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

所以这意味着您使用的是 32 位 CPU 或 32 位操作系统或 32 位编译版本的 PHP。可以使用PHP_INT_MAX. 这sum如果您在 64 位机器上执行此操作，则将正确计算

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

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

score 28 · Accepted Answer

为了完整起见，这是 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 位机器。

有一个警告：Microsoft 提供的编译器明确不支持已有 14 年历史的 C99 标准，因此让它在 Visual Studio 中运行是一个废话。

score 21 · Accepted Answer

我的猜测是，当总和超过本机的容量时int（2 ³¹ -1 = 2,147,483,647），Node.js 和 PHP 切换到浮点表示，并且您开始出现舍入错误。像 Go 这样的语言可能会尝试尽可能长时间地使用整数形式（例如，64 位整数）（如果它确实不是以整数形式开始的）。由于答案适合 64 位整数，因此计算是准确的。

score 19 · Accepted Answer

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

score 17 · Accepted Answer

对此的答案“出人意料”地简单：

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

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

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

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

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

因此，在您的 Sum 达到9,007,199,254,740,992（即2^53）时，PHP Maths 返回的浮点值将不再足够精确。

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）是否也存在同样的问题？

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

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

score 15 · Accepted Answer

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

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

另一种解决方案是使用了解精度问题并解决它的求和算法。下面你会发现相同的求和，首先使用 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）您的语言如何处理整数与浮点数据类型。

score 14 · Accepted Answer

如果你有 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 位来说太高了。

score 12 · Accepted Answer

在红宝石中：

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

打印500000000500000000，但在我的 2.6 GHz Intel 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

score 11 · Accepted Answer

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

score 4 · Accepted Answer

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

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

score 4 · Accepted Answer

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

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

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

score 3 · Accepted Answer

Racket v 5.3.4（MBP；时间以毫秒为单位）：

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

score 3 · Accepted Answer

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

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

score 3 · Accepted Answer

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

score 3 · Accepted Answer

为了完整起见，在 Clojure 中（漂亮但效率不高）：

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

score 3 · Accepted Answer

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

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

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

使用“使用 bigint”脚本工作了两个小时，并且会工作更多，但我停止了它。太慢了。

score 3 · Accepted Answer

在 Rebol 中运行良好：

>> sum: 0
== 0

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

>> type? sum
== integer!

这是使用 Rebol 3，尽管它是 32 位编译的，但它使用 64 位整数（与使用 32 位整数的 Rebol 2 不同）

score 3 · Accepted Answer

我想看看 CF Script 中发生了什么

<cfscript>
ttl = 0;

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

我得到了 5.00000000067E+017

这是一个非常巧妙的实验。我相当肯定我可以通过更多的努力更好地编写这个代码。

score 3 · Accepted Answer

3

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

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

于 2013-08-05T18:03:35.823 回答

score 3 · Accepted Answer

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 以使其快速运行，但立即运行代码的动态体验是相同的。

score 3 · Accepted Answer

AWK：

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

score 2 · Accepted Answer

短暂聊天：

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

"500000000500000000"

score 2 · Accepted Answer

二郎作品：

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

score 2 · Accepted Answer

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

整数的大小取决于平台，尽管通常值约为 20 亿的最大值（即 32 位有符号）。64 位平台的最大值通常约为 9E18。PHP 不支持无符号整数。自 PHP 4.4.0 和 PHP 5.0.5 起，可以使用常量 PHP_INT_SIZE 确定整数大小，使用常量 PHP_INT_MAX 确定最大值。

score 2 · Accepted Answer

类别其他解释语言：

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

我将测试放在 proc 中以对其进行字节编译。

score 2 · Accepted Answer

仅出于完整性考虑。

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

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

Elapsed time is 0.004471 seconds. ans = 5.000005000000000e+11

而在 F# 交互中，自动单元类型会产生溢出错误。分配类型 int64 给出正确答案：

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

val it : int64 = 500000500000L

注意：
可以使用Seq.reduce (+)而不是Seq.sum没有明显的效率变化。但是，使用Seq.reduce (+)自动单元类型会给出错误的答案，而不是溢出错误。
计算时间 <.5 秒，但我目前很懒，所以我没有导入 .NET 秒表类来获得更准确的时间。

score 2 · Accepted Answer

有趣的是，PHP 5.5.1 给出了 499999999500000000（大约 30 秒），而 Dart2Js 给出了 500000000067109000（这是意料之中的，因为执行的是 JS）。CLI Dart 立即给出了正确的答案。

score 2 · Accepted Answer

一些答案已经解释了为什么你的 PHP 和 Node.js 代码不能按预期工作，所以我不会在这里重复。我只想指出，这与“解释语言与编译语言”无关。

也许这是解释语言的问题，这就是为什么它可以在像 Go 这样的编译语言中工作？

“语言”只是一组定义明确的规则；语言的实现是解释或编译的。我可以采用一种其主要实现已编译的语言（如 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

score 2 · Accepted Answer

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

score 2 · Accepted Answer

港口：

proc Main()

   local sum := 0, i

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

   ? sum

   return

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

score 1 · Accepted Answer

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

score 0 · Accepted Answer

正如其他人指出的那样，进行此计算（无论使用哪种语言）的最快方法是使用简单的数学函数（而不是 CPU 密集型循环）：

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

不过，您仍然需要解决任何 32/64 位整数/浮点问题，具体取决于语言。

score 0 · Accepted Answer

而红宝石的：

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

似乎得到了正确的数字。

score 0 · Accepted Answer

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

php - 在解释语言上处理非常大的整数时出现意外结果

36 回答 36

Tcl：

Related

Reference