nekoTheShadow’s diary

IT業界の片隅でひっそり生きるシステムエンジニアです(´・ω・`)

rubyでユークリッドの互除法を短く実装しよう。

 最近いろいろなアルゴリズムを短く短くすることにはまっています。今日はその一環でユークリッドの互除法を扱いました。

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

 ユークリッドの互除法は最大公約数を探す定番アルゴリズムです。シンプルながら非常に強力で、しかも世界最古のアルゴリズムというすごいやつです。

 具体的な手順は次のようになります。*1

  1. R1≧R2を満たすふたつの自然数R1R2について、R1÷R2のあまりR3を求める。
  2. R2R3のあまりR4を求める。
  3. step.1とstep.2をRn = 0になるまで繰り返す。
  4. Rn-1R1R2の最大公約数となる。

 ちょっとわかりづらいので、具体例を見てみましょう。ユークリッドの互除法を利用して69と18の最大公約数を求めてみましょう。

  1. 69 ÷ 18 = 3 ... 15
  2. 18 ÷ 15 = 1 ... 3
  3. 15 ÷ 3 = 5 ... 0

 よって69と18の最大公約数は3と求まるわけです。

具体的な実装

 具体的な手順が理解できたところで、実際にコードのレベルにアルゴリズムを落とし込んでいきます。

 ではa = 69, b = 18として、先ほどの具体例を表に表してみます。

a b あまり
69 18 3 15
18 15 1 3
15 3 5 0
3 0 ? ?

 上の表からいえるのは

  • aは1段階前のbの値である。
  • bは1段階前のあまりの値である。
  • bが0になったら処理終了。
    • 逆に言えばbが0より大きい間は処理を続けるということである。
  • 求める最大公約数はaにあらわれる。

 以上をプログラミングに当てはめていくと、次のようになるはずです。

def gcd(a,b)
    while b > 0
        a,b = b,a%b
    end
    return a
end

 これをrubyらしくリファクタリングしましょう。

def gcd(a,b)
    a,b = b,a%b while b > 0
    a
end

 随分とすっきりしましたね。具体的には次のようなことを行っています。

  • 後置whileを利用する。
  • メソッドの戻り値にreturnを必ずしも用いない

 このふたつはrubyらしさを演出する(?)要素なので積極的に使っていきたいところです。

おまけ

その1

 なおabの値を逆、すなわちa = 18, b = 69としても、最大公約数は求めることができます。

a b あまり
18 69 0 18
69 18 3 15
18 15 1 3
15 3 5 0
3 0 ? ?

 仮にa ≦ bだとしても1回目の処理で必然的にabスワップされるので、a ≦ bと同じ結果が得られるというわけです。

その2

 ちなみに同じことをC言語で実装すると以下のようになります――というかなるはずです(実はあまりCは詳しくない)。もっと簡潔にかけるかも……?

int gcd(int num1, int num2){
    int temp1, temp2;
    while (num2 > 0){
        temp1 = num2;
        temp2 = num1 % num2;
        
        num1 = temp1;
        num2 = temp2;
    }
    return num1;
}

その3

 最大公約数がわかると、最小公倍数は簡単に求められます。説明するまでもないレベルなので、rubyのコードだけ書いておきますね。

def lcm(a,b)
    a * b / gcd(a,b)
end