ユークリッドの互除法

L99-32問目

OCamlのL99問題の32問目は2つの正の整数の最大公約数(the greatest commom divisor)を求めよ、という問題。これは私自身、過去にやったことがあるので、できる気がします(記憶が確かなら)

ユークリッドの互除法は例えば a = 10 b = 8 とした時、以下のような流れで計算していきます。

a(10) / b(8) = 1 余り(r) 2
b(8) / r(2) = 4 余り(r) 0
余り(r)が0になった時の除数、つまり2が最大公約数

といった流れで求めることができます。

OCamlで書くと以下のようになります。


let rec gcd a b =
  if b = 0 then a else gcd b (a mod b)
;;

非常に簡単。じゃあCommon Lispでやってみよう！ (defun gcd (a b) ...……

エラー！！！

実はCommon Lispにはgcdという関数がすでに用意されている。


* (gcd 10 8)
2

なんということでしょう。ということで一応別名で書いてみる。


(defun gcd2 (a b)
  (if (zerop b)
    a
    (gcd2 b (mod a b))))

せっかくなので(文章量も少なすぎるので)、他の言語でも書いてみる。

Rustの場合


fn gcd(a: u32, b: u32) -> u32 {
    if b == 0 { a }
    else { gcd(b, a % b) }
}

Nimの場合


proc gcd(a, b: uint): uint =
  if b == 0:
    a
  else:
    gcd(b, (a mod b))

Pythonの場合


def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, (a % b))

Haskellの場合、これまたCommon Lispと同様にgcdという関数がすでにあるようですので、別名で。


gcd' :: Integral a => a -> a -> a
gcd' a 0 = a
gcd' a b = gcd' b (mod a b)

Clojureの場合


(defn gcd
  [a b]
  (if (zero? b)
    a
    (recur b (mod a b))))

2つ以上の数の最大公約数を求める場合

上記で示したものは2つの数の最大公約数を求めるものでした。ではそれ以上の数の最大公約数を求めたい場合はどうすればよいのか？

単純にまず2つの数の最大公約数を求め、その最大公約数とあとに来る数の最大公約数を求める、という処理を続ける。

OCamlで書くと以下のような感じになるだろうか？


exception Can_not_determine_gcd

let ggcd list =
  let rec gcd a b = if b = 0 then a else gcd b (a mod b) in
  match list with
  | [] | [_] -> raise Can_not_determine_gcd
  | h :: t -> List.fold_left gcd h t;;

ではCommon Lispではどうだろうか？もともと備わっているgcd関数は2つ以上も処理できますが、自分で書いてみました。


(defun ggcd (a b &rest r)
  (labels ((aux (a b)
             (if (zerop b)
                 a
                 (aux b (mod a b)))))
    (cond
      ((endp r) (aux a b))
      (t
       (reduce #'aux (cons a (cons b r)))))))

&restは可変個の引数を扱う時に使うもので、3つ以上与えられた場合、3つ目からの数をまとめてリストにしてくれます。reduceは関数とシークエンスを受け取って、先頭の2要素に関数を適用した後、その結果と残りの要素に関数を適用していくといったもので、つまるところOCamlのflod_leftと同じ感じです。

まとめ

ユークリッドの互除法は私のように数学の知識がない場合でも、算数の知識とどのようなものなのかということを知っているというだけで簡単にできます。再帰も使われているので、私のように再帰が苦手な方の勉強になるものかもしれません。

2020/06/18