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

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

走

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自动升级到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

Answer 2

您的Go代码使用具有足够位的整数运算来给出确切的答案.从未接触过PHP或Node.js,但是从结果中我怀疑数学是使用浮点数完成的,因此应该预计不会对这个数量的数字精确.

Answer 3

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

PHP的最大整数值:

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

所以它意味着要么使用32位CPU,要么使用32位操作系统或32位编译版本的PHP.它可以找到使用PHP_INT_MAX.的sum,如果你做一个64位机器上会被正确地计算.

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数据类型.它提供了C可以管理的最大的原始存储,它运行真的非常快.该long long类型也适用于大多数32或64位机器.

有一点需要注意:Microsoft提供的编译器明确地不支持14年前的C99标准,因此在Visual Studio中运行它是一个难题.

Answer 5

我的猜测是,当总和超过本机的容量int(2 ³² -1 = 2,147,483,647)时,Node.js和PHP切换到浮点表示,你开始得到舍入错误.像Go这样的语言可能会尽可能地尝试使用整数形式(例如,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遇到超出整数类型边界的数字,它将被解释为浮点数.此外,导致超出整数类型边界的数字的操作将返回浮点数.

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

这说,并且知道PHP FLOAT实现遵循IEEE 754双精度格式,意味着PHP能够处理高达52位的数字,而不会失去精度.(在32位系统上)

因此,在Point,您的Sum达到9,007,199,254,740,992(即2 ^ 53)时,PHP Maths返回的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

此示例显示了Point,其中PHP失去了精度.首先,最后一个有效位将被删除,导致前两个表达式产生相同的数字 - 它们不是.

从现在开始,使用默认数据类型时,整个数学将出错.

•对于其他解释性语言(例如Python或Perl),它是否也是同一个问题？

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

但是,每种语言对于此类场景可能具有不同的线程.

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)语言如何处理整数与浮点数据类型.

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

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,这是一个更快的任意精度库.