ユークリッドの互除法

gawk


ユークリッドの互除法 - Wikipedia にも書かれているようなアルゴリズムであり、密かに (知らず知らずのうちに) 多用されるアルゴリズムでもあります。多分、Wikipedia よりもコードを見た方が分かりやすいと思います。個人的には、小飼さんのところに「小学校でも必ず習うこのアルゴリズム」とありますが、全て直感で解いていたので、アルゴリズムとして私の頭には定着していません。

#! /usr/bin/gawk -f
# gcd.awk - print GCD (Greatest Common Divisor) between n numbers
# usage: gawk -f gcd.awk ARGV[1] ARGV[2] ...
#   input:  ARGV
#   output: gcd(x, y)
BEGIN {
    print ngcd(ARGV);
}

# gcd - get GCD (Greatest Common Divisor) between 2 numbers
#   input:  x and y (2 numbers)
#   output: return gcd(x, y)
function gcd(x, y) {
    if (y == 0) {
        return x;
    } else {
        return gcd(y, x % y);
    }
}

# ngcd - get GCD (Greatest Common Divisor) between n numbers
#   input:  array[n]
#   output: return gcd(x, y)
function ngcd(arr,    n, d) {
    n = ARGC - 1;
    d = arr[1];
    for (i = 2; i <= n && d != 1; i++) {
        d = gcd(arr[i], d);
    }
    return d;
}

出力は以下のようになります。

$ gawk -f gcd.awk 10 50
10
$ gawk -f gcd.awk 10 50 55
5

参考にさせていただいたのは、例によって「C言語による最新アルゴリズム事典」です。

C言語による最新アルゴリズム事典 (ソフトウェアテクノロジー)

C言語による最新アルゴリズム事典 (ソフトウェアテクノロジー)