php - インタープリター言語で非常に大きな整数を操作すると、予期しない結果が生じる

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 などの他のインタープリター言語にも同じ問題がありますか?

score 101 · Accepted Answer

あなたの Go コードは、正確な答えを出すのに十分なビット数の整数演算を使用しています。PHP や Node.js に触れたことはありませんが、結果から、浮動小数点数を使用して計算が行われていると思われるため、この大きさの数値については正確ではないことが予想されます。

score 21 · Accepted Answer

私の推測では、合計がネイティブの容量int(2 ³¹ -1 = 2,147,483,647) を超えると、Node.js と PHP は浮動小数点表現に切り替わり、丸めエラーが発生し始めます。Go のような言語は、可能な限り整数形式 (64 ビット整数など) に固執しようとするでしょう (実際、最初から整数形式でなかったとしても)。答えは 64 ビット整数に収まるので、計算は正確です。

score 19 · Accepted Answer

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

score 14 · Accepted Answer

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 ビットには高すぎました。

score 11 · Accepted Answer

大きな整数のものには 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 が使用されます。これは、より高速な任意精度ライブラリの 1 つです。

score 3 · Accepted Answer

32 ビット Windows 上の ActivePerl v5.10.1、インテル core2duo 2.6:

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

結果：5分で5.00000000067109e+017。

「use bigint」スクリプトを使用すると、2 時間動作し、さらに動作するはずでしたが、停止しました。遅すぎる。

score 3 · Accepted Answer

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

score 3 · Accepted Answer

CFスクリプトで何が起こったのか見たかった

<cfscript>
ttl = 0;

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

私は5.00000000067E+017を得ました

これはかなり巧妙な実験でした。もっと努力すれば、これをもう少しうまくコーディングできたと確信しています。

score 3 · Accepted Answer

I don't have enough reputation to comment on @postfuturist's Common Lisp answer, but it can be optimized to complete in ~500ms with SBCL 1.1.8 on my machine:

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

score 3 · Accepted Answer

これにより、整数キャストが強制されるため、PHP で適切な結果が得られます。

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

score 3 · Accepted Answer

完全を期すために、Clojureで（美しいがあまり効率的ではない）：

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

score 3 · Accepted Answer

Common Lisp は、最速のインタープリター* 言語の 1 つであり、デフォルトで任意の大きな整数を正しく処理します。これには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 を行っている可能性がありますが、コードをすぐに実行するという動的なエクスペリエンスは同じです。

score 3 · Accepted Answer

Rebolで正常に動作します:

>> sum: 0
== 0

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

>> type? sum
== integer!

これは、32 ビットでコンパイルされているにもかかわらず、64 ビット整数を使用する Rebol 3 を使用していました (32 ビット整数を使用した Rebol 2 とは異なります)。

score 2 · Accepted Answer

港：

proc Main()

   local sum := 0, i

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

   ? sum

   return

結果は500000000500000000. (windows/mingw/x86 と osx/clang/x64 の両方)

score 2 · Accepted Answer

完全を期すためにのみ。

MATLAB では、型の自動選択に問題はありません。

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

Elapsed time is 0.004471 seconds. ans = 5.000005000000000e+11

また、F# インタラクティブでは、自動ユニットタイプによってオーバーフローエラーが発生します。タイプ int64 を割り当てると、正しい答えが得られます。

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

val it : int64 = 500000500000L

注:効率に目立った変化がなくても代わりに
使用できます。ただし、自動単位タイプを使用すると、オーバーフローエラーではなく間違った応答が返されます。計算時間は 0.5 秒未満ですが、私は現在怠け者なので、より正確な時間を取得するために .NET ストップウォッチクラスをインポートしていません。Seq.reduce (+)Seq.sumSeq.reduce (+)

score 2 · Accepted Answer

面白いことに、PHP 5.5.1 は 499999999500000000 (~ 30 秒) を返しますが、Dart2Js は 500000000067109000 を返します (実行されるのは JS であるため、これは予想されることです)。CLI Dart は正しい答えを即座に提供します。

score 2 · Accepted Answer

その他の解釈された言語のカテゴリ:

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 内に配置して、バイトコンパイルします。

score 2 · Accepted Answer

スモールトーク:

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

"500000000500000000"

score 2 · Accepted Answer

PHP コードの場合、答えは次のとおりです。

整数のサイズはプラットフォームに依存しますが、最大値は約 20 億が通常の値です (符号付き 32 ビット)。通常、64 ビットプラットフォームの最大値は約 9E18 です。PHP は符号なし整数をサポートしていません。PHP 4.4.0 および PHP 5.0.5 以降では、整数サイズは定数 PHP_INT_SIZE を使用して決定でき、最大値は定数 PHP_INT_MAX を使用して決定できます。

score 2 · Accepted Answer

PHP と Node.js コードが期待どおりに機能しない理由については、すでにいくつかの回答で説明されているため、ここでは繰り返しません。これは「解釈された言語とコンパイルされた言語」とは何の関係もないことを指摘したいだけです。

おそらくこれはインタープリター言語の問題であり、それが Go のようなコンパイル済み言語で機能する理由でしょうか?

「言語」は、明確に定義された一連のルールにすぎません。言語の実装は、解釈またはコンパイルされたものです。主要な実装がコンパイルされている言語 (Go など) を使用して、その言語用のインタープリターを作成することもできます (逆も同様です)。言語の仕様に従っている必要があります。実際、PHP と Node.js の結果は言語の仕様に従っており (他の回答が指摘しているように)、これはこれらの言語の主要な実装が解釈されるという事実とは何の関係もありません。定義上、コンパイルされた言語の実装も同じ結果を生成する必要があります。

これらすべての具体的な例は、広く使用されているコンパイル済み実装と解釈済み実装の両方を持つ Python です。解釈された実装でプログラムの翻訳されたバージョンを実行します。

>>> total = 0 
>>> for i in xrange(1000000001):
...     total += i
... 
>>> print total
500000000500000000

Python の定義により、コンパイル済みの実装で実行した場合とは異なる出力になってはなりません。

total = 0
for i in xrange(1000000001):
    total += i

print total

500000000500000000

score 1 · Accepted Answer

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]

score 0 · Accepted Answer

他の人が指摘しているように、(言語に関係なく) この計算を行う最速の方法は、(CPU を集中的に使用するループではなく) 単純な数学関数を使用することです。

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

ただし、言語によっては、32/64 ビットの整数/浮動小数点数の問題を解決する必要があります。

score 0 · Accepted Answer

Javascript (および場合によっては PHP) は、すべての数値を double として表し、整数値に丸めます。これは、(int64 および Java long によって提供される 64 ビットの代わりに) 53 ビットの精度しか持たないことを意味し、大きな値では丸め誤差が発生します。

score 0 · Accepted Answer

そしてルビーのもの：

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

適切な数を取得するようです。

php - インタープリター言語で非常に大きな整数を操作すると、予期しない結果が生じる

36 に答える 36

Tcl:

Related

Reference