[Php] 在解释型语言中使用非常大的整数时会出现意外的结果


Answers

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

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会有同样的问题吗?




有趣的是,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



港口:

proc Main()

   local sum := 0, i

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

   ? sum

   return

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




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

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



我没有足够的声望评论@ postfuturist的Common Lisp答案,但可以使用我的机器上的SBCL 1.1.8在〜500ms内完成优化:

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



短暂聊天:

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

"500000000500000000"



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

<cfscript>
ttl = 0;

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

我得到了5.00000000067E + 017

这是一个非常简洁的实验。 我相当确信我可以通过更多的努力将这一点编码得更好一些。




实际上这个问题很酷。

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




在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



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



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's long long数据类型。 它提供了C可以管理的最大的原始存储,它的运行真的非常快。 long long类型也可以在大多数32位或64位机器上工作。

有一点需要注意:微软提供的编译器明确不支持14岁的C99标准,因此在Visual Studio中运行这个标准是一个不错的选择。




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



其他答案已经解释了这里发生了什么(像往常一样浮点精度)。

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

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




用红宝石花了很长时间,但给出了正确的答案:

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