第8章 その他の Java 8 機能を理解する : 問題 3 : ユークリッドの互除法

問題

ユークリッドの互除法で、2つの整数の最大公約数を求めよ

2つ整数のどちらかが負でも、最大公約数は正の数になる（なぜなら反数も約数であり、正数の方が大きいからである）

そして余りの計算に

• %
• Math.floorMode(int, int)
• 数学的な剰余計算（余りは常に正）

の3つの使い分けよ

解答

ユークリッドの互除法は、負の値がこないと仮定すれば非常にシンプルである

■ ユークリッドの互除法

public static int gcd(int a, int b) {
    // a ≧ 0, b ≧ 0 を仮定する
    while (a != 0 && b != 0) {
        if (a >= b) {
            a %= b;
        } else {
            b %= a;
        }
    }
    return a == 0 ? b: a;
}

負の値も考慮しなければいけないのなら、メソッドの先頭で

a = Math.abs(a);
b = Math.abs(b);

とするだけだが、これじゃ練習問題にならんのでしょうな

■ 剰余計算の仕様

	4÷3	4÷(-3)	(-4)÷3	(-4)÷(-3)
%	1	1	-1	-1
floorMode	1	-2	2	-1
数学的	1	1	2	2

ユークリッドの互除法が使っている剰余は自然数を想定しているので、負の値に無理やり適用しても意味がない

4 を 3 で割った余りが符号によっては 2 になるというのを、ユークリッドの互除法に適用するのは変だと思う

ただ a を b で割った余りを r としたとき、ユークリッドの互除法は

r と b の約数は a と b の約数と同じ

という事実を基にしているが

(b - r) と b の約数も a と b の約数と同じ

なので

4 を 3 で割った余りが 1 だろうが 2 だろうが、どっちでもいいか

■ 結論

出題者に反旗を翻して、3つの剰余計算を使い分けるのはやめます

素直に、以下のコードで十分でしょう

public static int gcd(int a, int b) {
    a = Math.abs(a);
    b = Math.abs(b);
    while (a != 0 && b != 0) {
        if (a >= b) {
            a %= b;
        } else {
            b %= a;
        }
    }
    return a == 0 ? b: a;
}