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

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

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

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

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

Python 工作原理：

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

艺术

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

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

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

>>> 2**99
633825300114114700748351602688L

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

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

类别 其他解释性语言：

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 中以对其进行字节编译。

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

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

假设它是 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 的数据类型。它提供了 C 可以管理的最大的原始存储，并且运行速度非常非常快。该类型也适用于大多数 32 位或 64 位计算机。long longlong long

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

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

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

卡汉总和给出了一个漂亮的结果。当然，计算确实需要更长的时间。是否要使用它取决于 a） 性能与精度需求，以及 b） 您的语言如何处理整数与浮点数据类型。

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

PHP 的最大整数值：

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

因此，这意味着您使用的是 32 位 CPU 或 32 位操作系统或 32 位编译版本的 PHP。可以使用 找到它。如果您在 64 位计算机上执行此操作，则会正确计算。PHP_INT_MAXsum

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

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

在 Ruby 中：

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

打印，但在我的 4 GHz Intel i2.6 上需要 7 分钟。500000000500000000

---

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

结果为 。 （在 Windows/mingw/x86 和 OSX/CLANG/x64 上）500000000500000000

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

在 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 中的正确答案。您必须使用 Longs，否则会溢出数字：

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）。 500000000500000000

球拍 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 给出了 499999999500000000（在 ~ 30 秒内），而 Dart2Js 给出了500000000067109000（这是意料之中的，因为执行的是 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 位整数（与使用 32 位整数的 Rebol 2 不同）

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

<cfscript>
ttl = 0;

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

我得到了 5.00000000067E+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 在 32 位 Windows 上，intel core2duo 2.6：

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

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

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

而红宝石的：

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

似乎得到了正确的数字。

仅供参考。

---

在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

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

这个问题的答案“出奇地”简单：

首先，正如你们大多数人可能知道的那样，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 位系统上）

因此，当您的总和达到 9,007,199,254,740,992（即 2^53）时，PHP 数学返回的 Float 值将不再足够精确。

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）来说，这个问题是否相同？

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

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

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

一些答案已经解释了为什么你的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