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

Question

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

phpnode.jsprecisioninteger-overflowinteger-arithmetic

194

我正在尝试计算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

36

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

5

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

113

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

55

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

5

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

显示剩余24条评论

36个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Samuel Henry · Answer 1

Smalltalk:

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

"500000000500000000"

- user2307487 · Answer 2

仅为完整性考虑。

MATLAB中自动类型选择没有问题:

tic; ii = 1:1000000; sum(ii); toc; ans

经过的时间为0.004471秒。 ans = 5.000005000000000e+11

在F#交互式中，自动单位类型会导致溢出错误。分配int64类型可以得到正确的答案：

seq {int64 1.. int64 1000000} |> Seq.sum

val it : int64 = 500000500000L

注：
可以使用Seq.reduce (+)代替Seq.sum而不会对效率造成明显影响。但是，使用自动单位类型的Seq.reduce (+)将给出错误的答案而不是溢出错误。
计算时间小于0.5秒，但我目前有点懒，所以没有导入.NET秒表类来获得更精确的时间。

- Steve Wilhelm · Answer 3

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

- Tom Chapin · Answer 4

正如其他人所指出的，无论使用哪种语言，执行这个计算的最快方法是使用一个简单的数学函数（而不是一个占用CPU的循环）：

number = 1000000000;
result = (number/2) * (number+1);

不过，根据语言的不同，您仍需要解决任何32/64位整数/浮点数问题。

- user2650994 · Answer 5

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

- Hartator · Answer 6

还有 Ruby 的：

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

看起来得到了正确的数字。