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

php Node.js

西里Tom

2020-03-23

我试图得到的总和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)是否会有相同的问题?

第3083篇《在解释语言上使用非常大的整数时出现意外结果》来自Winter(https://github.com/aiyld/aiyld.github.io)的站点

27个回答
老丝小小 2020.03.23

短暂聊天:

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

"500000000500000000"
猿小胖 2020.03.23

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
乐米亚 2020.03.23

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

阿飞理查德 2020.03.23

有趣的是,PHP 5.5.1给出了499999999500000000(约30秒),而Dart2Js给出了500000000067109000(这是可以预料的,因为要执行的是JS)。CLI Dart立即提供正确的答案。

AHarry 2020.03.23

对于PHP代码,答案在这里

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

Itachi 2020.03.23

港口:

proc Main()

   local sum := 0, i

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

   ? sum

   return

结果500000000500000000(在Windows / mingw / x86和osx / clang / x64上)

MandyTony 2020.03.23

分类其他解释语言:

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

AStafan 2020.03.23

在Rebol中工作正常:

>> sum: 0
== 0

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

>> type? sum
== integer!

这使用的是Rebol 3,尽管经过32位编译,但仍使用64位整数(与使用32位整数的Rebol 2不同)

LGil 2020.03.23

为了完整起见,在Clojure中(美丽但不太有效):

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

在32位Windows上的ActivePerl v5.10.1,intel core2duo 2.6:

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

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

使用“ use bigint”脚本可以工作两个小时,并且可以工作更多,但是我停止了。太慢了。

西里神奇 2020.03.23

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

<cfscript>
ttl = 0;

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

我有5.00000000067E + 017

这是一个非常简洁的实验。我很确定我可以通过付出更多的努力来编写更好的代码。

古一古一 2020.03.23

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

> (time (for/sum ([x (in-range 1000000001)]) x))
cpu time: 2943 real time: 2954 gc time: 0
500000000500000000
西门猿阿飞 2020.03.23

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

通过强制执行整数强制转换,可以在PHP中获得正确的结果。

$sum = (int) $sum + $i;
蛋蛋西门 2020.03.23

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

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

蛋蛋 2020.03.23

在红宝石中使用了很长时间,但是给出了正确的答案:

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

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

这是Scala中的正确答案。您必须使用Longs,否则将导致数字溢出:

println((1L to 1000000000L).reduce(_ + _)) // prints 500000000500000000
猴子村村 2020.03.23

在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
Gil斯丁 2020.03.23

其他答案已经说明了这里发生的情况(与往常一样,浮点精度)。

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

另一种解决方案是使用求和算法,该求和算法了解精度问题并加以解决。在下面您可以找到相同的求和,首先使用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)语言如何处理整数和浮点数据类型。

飞云 2020.03.23

如果您有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位则太大。

十三 2020.03.23

我的猜测是,当总和超过本机容量int(2 31 -1 = 2,147,483,647)时,Node.js和PHP切换为浮点表示形式,并且开始出现舍入错误。像Go这样的语言可能会尽可能地坚持使用整数形式(例如64位整数)(如果确实不是从此开始)。由于答案适合64位整数,因此计算是精确的。

Tom凯 2020.03.23

答案很简单:

首先-正如您大多数人所知道的-32位整数范围从−2,147,483,6482,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 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

此示例显示了PHP失去精度的要点。首先,最后一个有效位将被丢弃,从而导致前两个表达式的结果相等,但不是。

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

•其他解释语言(例如Python或Perl)是否也存在相同的问题?

我不这么认为。我认为这是没有类型安全性的语言的问题。尽管上面提到的整数溢出会在使用固定数据类型的每种语言中发生,但是没有类型安全性的语言可能会尝试将其与其他数据类型相结合。但是,一旦碰到“自然”(系统赋予的)边界,他们可能会返回任何东西,但结果正确。

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

卡卡西Near 2020.03.23

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

PHP的最大整数值:

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

因此,这意味着您正在使用32位CPU或32位OS或32位PHP编译版本。可以使用找到PHP_INT_MAXsum如果在64位计算机上进行计算将可以正确计算出。

JavaScript中的最大整数值为9007199254740992您可以使用的最大精确整数值为2 53(从此问题中获取)。sum超过此限制。

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

MandyPro 2020.03.23

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
Harry路易 2020.03.23

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

猴子 2020.03.23

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
斯丁 2020.03.23

为了完整性,这是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中运行是一个废话。

问题类别

JavaScript Ckeditor Python Webpack TypeScript Vue.js React.js ExpressJS KoaJS CSS Node.js HTML Django 单元测试 PHP Asp.net jQuery Bootstrap IOS Android