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

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

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，所以我决定尝试另一种语言。

GO

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

但是它能够正常运行！那么我的 PHP 和 Node.js 代码出了什么问题呢？

也许这是解释性语言的问题，所以它能在像 Go 这样的编译语言中工作？如果是这样，其他解释性语言如 Python 和 Perl 会有相同的问题吗？

- Baba

---

你需要使用这个：http://php.net/manual/zh/book.bc.php，否则你将不停地陷入IEEE 754的问题中。 - tereško

在PHP中处理大数（即64位），请使用GMP函数，例如gmp_add()。 - Jeffrey

为了达到超高效的目的，你的循环应该从1开始而不是0。 :P - Graham Borland

求1到N的整数和等于(N/2)*(N+1)。 - Phong

@Baba，对于你的计算来说，0是多余的，因此没有必要在循环中额外迭代将0加到0上。 - Brian Warshaw

Answer 1

Python起作用了：

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

或者：

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

Python的int会自动转换为支持任意精度的Python long。它在32位或64位平台上都能产生正确的答案。

这可以通过将2的幂次方提高到远远超过平台比特宽度来证明：

>>> 2**99
633825300114114700748351602688L

你可以通过Python演示，PHP中出现错误值的原因是因为当数值大于2 ** 32-1时，PHP会将其提升为浮点数：

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

- dawg

---

你在32位或64位系统上运行了这个吗？ - Baba

无论是32位还是64位，它都应该能正常工作，因为Python整数会自动升级到任意精度而不是溢出。但可能需要更长的时间才能完成。 - dawg

在这种情况下，任何系统上的Python都可以工作，因为Python会自动切换到长整型，如果需要的话。如果这仍然不足够，它也会切换到大整型。 - Alok Singhal

有点严厉。OP本人投了赞成票。他特别问这个问题是否与Python上的类似问题相似。回答是，不是。提供证明代码来表明不是相似的问题。到底怎么了？ - dawg

Python的示例太长了，只需使用sum(xrange(int(1e9)+1))（....sum适用于可迭代对象） - Jay M

Answer 2

您的Go代码使用有足够位数的整数算术运算来得出精确答案。虽然我没有接触过PHP或Node.js，但从结果推断出它们使用浮点数进行数学计算，因此对于这种数量级的数字不应该期待完全准确。

- zzzz

---

是的。如果 PHP 遇到超出整数类型范围的数字，它会将其解释为浮点数。此外，如果一个操作的结果超出整数类型的范围，它也会返回一个浮点数。-http://php.net/manual/en/language.types.integer.php - Nate

在NodeJS（以及JavaScript的普遍使用）中，所有算术运算（除了位运算）的行为都像是使用浮点数进行的。它们是否实际上是这样做的，是取决于各个JavaScript引擎的决策的底层区别。 - Peter Olson

在JavaScript规范中，没有整数类型。所有数字都是浮点数。 - toasted_flakes

@grasGendarme 有。ES5规范指定了各种整数转换方法，并要求它们在按位移位时被调用，例如。也就是说，在JavaScript中使用整数类型，但是所有算术运算符在对操作数进行任何处理之前都将它们转换为浮点数（除了编译器优化）。 - Peter Olson

这是代码(http://play.golang.org/p/46a_d3dDG5)，我猜它出了问题，因为我使用了float64而不是int64..刚刚确认它与32位或64位无关。 - Baba

Answer 3

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

PHP 的最大整数值为:

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

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

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

如果整数值未超过这些限制，则您可以放心使用。否则，您将不得不寻找任意精度整数库。

- user568109

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

有一个限制: 由Microsoft提供的编译器明确不支持14年前的C99标准，因此在Visual Studio中运行这个程序是个问题。

- CyberSkull

---

MSVC++是一种C++编译器，而C++11标准中增加了long long类型。不过，这个类型在MSVC++和g++中已经作为扩展使用了几年时间。 - MSalters

@MSalters，所以作为C++的一个特性，它并不能真正帮助任何编译纯C程序的人。我从未尝试过从C切换到C++，所以我不知道这种解决方法是否实际可行。 - CyberSkull

而且，GCC或Clang与优化将整个循环转换为movabsq $500000000500000000, %rsi。 - Tor Klingberg

只需使用gcc -O3 或 clang -O3命令进行编译。我不知道具体优化的名称，基本上编译器会注意到循环的结果不依赖于任何参数，并在编译时对其进行计算。 - Tor Klingberg

C99的long long类型具有最小的64位大小，据我所知，在32位和64位平台上都是64位。我还没有看到对四元组或八元组整数的普遍支持。 - Devin Lane

Answer 5

我的猜测是，当总和超过本机int的容量(2³¹-1 = 2,147,483,647)时，Node.js和PHP会切换到浮点表示，并且你会开始得到舍入误差。像Go这样的语言可能会尽可能地坚持使用整数形式(例如64位整数)(如果它确实没有从那里开始)。由于答案适合64位整数，所以计算是精确的。

- Ted Hopp

---

Node.js明确没有int类型，它是在float类型中工作的。 - greyfade

@greyfade - 是的，我想这对所有符合EcmaScript标准的环境都是适用的。 - Ted Hopp

那不是（2 ** 31 - 1）吗？ - Zach Hunter

@ZacharyHunter - 确实是这样。感谢你发现了那个错误。 - Ted Hopp

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

- Miguel Prz

---

你是在32位还是64位系统上运行了这个？ - Baba

它在64位系统上执行。 - Miguel Prz

在 Perl v5.16.1 MSWin32-x86 上，4.99999999067109e+017 表示的是一个数值。 - Qtax

如果您需要处理大数字，可以使用 bignum 或 bigint。它们都是 Perl 核心模块，即它们随 Perl v5.8.0 或更高版本一起安装。请参阅 http://perldoc.perl.org/bignum.html 和 http://perldoc.perl.org/bigint.html。 - shawnhcorey

我在一台32位PPC Mac上运行Perl 5.12.4时得到了500000000500000000的结果。 - CyberSkull

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遇到超过整数类型限制的数字，它将被解释为FLOAT。此外，导致结果超出整数类型范围的操作也将返回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数学返回的FLOAT值将不再精确。

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

九千零七亿一千一百九十二万五千七百四十

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

九京零七兆一千九百九十二亿五千四百七十四万零九百九十二

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

9,007,199,254,740,994

这个例子展示了 PHP 失去精度的点。首先，最后一个有效位将被删除，导致前两个表达式的结果相等 - 而它们实际上是不相等的。

从现在开始，当使用默认数据类型时，整个数学运算都会出错。

•其他解释型语言例如 Python 或 Perl 是否存在同样的问题？

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

但是，每种语言对于这种情况可能都有不同的处理方式。

- dognose

Answer 8

其他答案已经解释了这里发生了什么（通常是浮点精度问题）。

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

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

- linac

---

@Baba 这与 OP 中的 Node.js/JavaScript 相同。至于为什么是 500000000067109000 vs. 500000000067108992 … 我不知道。 - linac

也许巴巴对使用点作为千位分隔符感到好奇：英语通常使用逗号。您也可以使用下划线作为更中性的方式。 - didierc

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位。

- Esailija

Answer 10

在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

- cgenco

---

对1到10亿的所有数字求和。 - Magnuss

@Magnuss：这就是我一开始尝试的，但它导致了大量的内存泄漏。你的方法似乎可以工作... - cgenco