Emacs Lisp で最大公約数など

最大公約数（greatest common divisor）を求めるアルゴリズムをEmacs Lisp で作成してみただけ。

前提として、引数 a と b は自然数で a > b を満たす。

1. 除数を減じながら公約数かどうか調べる方法

まずは、工夫も法則もない素朴な方法。小さい数 b を初期値として a と b を割り切れるか試す。割り切れなければ 1減らしてリトライする流れ。

(defun my-gcd (a b &optional div)    ; やむを得ず optional引数を使う
  (if (null div) (setq div b))
  (cond
   ((zerop div) 1)
   ((every (lambda (n) (zerop (% n div))) (list a b)) div)
   (t (my-gcd a b (1- div))) ))
=> my-gcd

;;; テスト
(my-gcd 156 65)
=> 13        ;正解。

性能というか、関数の呼出し回数も調べてみる。

(my-call-count my-gcd 156 65)
=> 53

156 と 65 の場合は53回だった。なお、呼び出し回数の計測には以前書いたマクロを使っている。

2. ユークリッドの互除法

「昔はアルゴリズムといえば互除法そのものを意味した」というくらい、歴史的に特別なアルゴリズム（吉田武「オイラーの贈り物」より）。

(defun my-gcd (a b)
  (if (zerop (% a b))
      b
    (my-gcd b (% a b)) ))
=> my-gcd

;;; テスト
(my-gcd 156 65)
=> 13        ;正解。

;;; 呼び出し回数を調べる
(my-call-count my-gcd 156 65)
=> 3        ;たった3回で済んでいる。

発展その1：最小公倍数

最大公約数と最小公倍数（least common multiple）のあいだには、「与えられた二数の積 = 最大公約数 × 最小公倍数」の関係が成り立つ。この関係から、最大公約数が求まればただちに最小公倍数も得られる。

(defun my-lcm (a b)
  "最小公倍数を求める"
  (/ (* a b) (my-gcd a b)))
=> my-lcm

;;; テスト
(my-lcm 156 65)
=> 780

発展その2：ディオファントス方程式

整数係数の方程式「ax + by = d」のことをディオファントス方程式（Diophantine equation）と呼び、d が a と b の最大公約数の倍数になっている場合、すなわち 「d = k × gcd(a, b)」である場合に解をもつ。

したがって、最大公約数を求める関数を応用して、ある数 a, b, d から成るディオファントス方程式の解の有無を調べることができる。

(defun my-solvablep (a b d)
  "a, b, d  から成る方程式 ax + by = d が解をもつ場合に t を返す"
  (zerop (% d (my-gcd a b))))
=> my-lcm

;;; テスト
(my-solvablep 156 65 13)
=> t
(my-solvablep 156 65 14)
=> nil

参考

• Amazon.co.jp： オイラーの贈物―人類の至宝eiπ=-1を学ぶ (ちくま学芸文庫): 吉田 武: 本
• 『最大公約数の求め方』