[Haskell] ユークリッドの互除法で最大公約数を求める

Haskellのお勉強

ハノイの塔の記事のときと同じように、今回もHaskellのお勉強のためにユークリッドの互除法による最大公約数の取得処理をHaskellで実装してみました。

まずは実装したコードを載せます。

main = print $ getGcd 1071 1029 -- 21

-- 最大公約数を求める関数
getGcd :: Int -> Int -> Int
getGcd a 0 = a
getGcd a b
    | a `mod` b == 0 = b
    | otherwise = getGcd b $ a `mod` b

ユークリッドの互除法とは

ユークリッドの互除法とはそもそもどのようなものか、例によって詳しくはWikipediaを参照してください。2つの数の最大公約数を効率よく求めるための手法のことです。以下Wikipediaの引用です。

2 つの自然数（または整式） a, b (a ≧ b) について、a の b による剰余を r とすると、 a と b との最大公約数は b と r との最大公約数に等しいという性質が成り立つ。この性質を利用して、 b を r で割った剰余、 除数 r をその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が 0 になった時の除数が a と b との最大公約数となる。

…

(問題) 1071 と 1029 の最大公約数を求める。

• 1071 を 1029 で割った余りは 42
• 1029 を 42 で割った余りは 21
• 42 を 21 で割った余りは 0

よって、最大公約数は21である。

ユークリッドの互除法のアルゴリズム

見ての通り、余りが0となるまで割り算を続け、その時の商が最大公約数となります。なのでこのアルゴリズム実現するには再帰関数を使ってやりましょう。

再帰関数のゴール地点は割り算のあまりが0になる時です。その時の割り算の商が再帰関数の戻り値となります。

プログラムの実装

gcdという名前の関数はすでにHaskell側で定義されているので、getGcdという関数を定義し、引数に最大公約数を求めるための整数値２つ(a, b)を取るようにします。

引数のいずれか片方でも0の場合はもう片方の数が最大公約数となります。

a/bの余りが0の場合、この時の商、つまり b が最大公約数となります。プログラム上では余りが0の時ではなく、その次に呼び出される a, 0 の引数の時の関数で再帰のループから抜け出します。

a/bの余りが0以外の場合、今度は b と その余りの最大公約数が a と b の最大公約数と等しいので再帰的にgetGcdを呼び出します。

確認

引数の a < b でも影響はありません。なぜならその時、a/b は 0 あまり a となり 引数を入れ替えた形で関数が呼ばれるからです。

上でも引用したWikipediaの例(1071と1029)を確認してみると、最大公約数は21となりました。

C#でも書いてみる

ユークリッドの互除法は手続き的な書き方でも、比較的シンプルに書くことができますが、再帰関数として実装すると1行で済みます。
それぞれの書き方でユークリッドの互除法をプログラムで書いてみました。

// 再帰関数でユークリッドの互除法
public static int GetGcd(int a, int b)
{
    return b != 0 ? GetGcd(b, a % 2) : a;
}

// ループでユークリッドの互除法
public static int GetGcd2(int a, int b)
{
    while (b != 0)
    {
        var r = a % b;
        a = b;
        b = r;
    }
    return a;
}