ぎるばーとの日記

もっともっと遠くへ行きたい 空が広く見える場所まで

GCD(0, 0) = ?

 前回わざと触れなかったところ。

 最大公約数は普通正の数に対して考えますが、実は片方が0でもOKです。
 「すべての整数は0の約数(0を割り切る)」と考えれば、0でないnと0の最大公約数はnになります。
 では、両方とも0の場合はどうすればいいでしょうか?

  • 案A:∞とする

 すべての整数に最大値はないので、∞。または定義しない。
 論理的にはこれが正しいような……。

  • 案B:0とする

 こちらは実用上の便利さを考慮すると捨てがたい案。
 3つ以上の数(うち1つ以上は0でない)の最大公約数を、例えばGCD(a, b, c) = GCD(GCD(a, b), c)として求めることができます。

 案Aは元の定義を重視して、案Bは結合的な二項演算の再定義という感じ?
 コンピュータ用なら、案Bを採用するのが無難かなーと思います。
 (参考:JavaBigIntegerCommons MathGuavaなどは案B。)