美しい数式と美しいプログラム - プログラマyasuhoの隠れ家

先週末「博士の愛した数式」という映画を観た。

正確には観たというより「ちらっと覗いた」という感じなんだけどね。で、その映画の中で「友愛数」という言葉が出てくる。

公式サイトより：

みてごらん。この素晴らしい一続きの数字の連なりを。
284の約数の和は220.
220の約数の和は284.
友愛数だ。
神の計らいを受けた、絆で結ばれた数字なんだ。美しいと思わないかい？

「友愛数」なんて、すごくきれいな言葉ですね。名前をつけた人はセンスがいいと思う。学生時代、もしもこんな先生がいたら、数学が好きになってハードのエンジニアになれたかな。なんてね。：）

さて、この友愛数。わりと単純にプログラムで求めることができそうです。先日やったFizzBuzz問題よりちょっとコード量が多いくらいかな。というわけで、さっそくCで書いてみました。

/*
 *  Compute amicable numbers
 */

#define DEFAULT_MAX_AMICABLES   10000

/*
 *  GetDivisor
 */
static int GetDivisor(int no)
{
    int     n;
    int     sum;
    int     i;

    n = no / 2;     /* don't include myself */
    sum = 0;

    for (i = 1; i <= n; i++) {
        if (no / i * i == no)
            sum += i;
    }

    return sum;
}

/*
 *  main
 */
void main(int argc, char **argv)
{
    int     i, j;
    int     max_amicables = DEFAULT_MAX_AMICABLES;
    int     *aDivisors;

    if (argc > 1)
        max_amicables = atoi(argv[1]);

    if (!(aDivisors = (int *)calloc(max_amicables + 1, sizeof(aDivisors[0]))))
        perror("calloc"), exit(1);

    /*
     *  Compute all of divisors
     */

    for (i = 0; i < max_amicables; i++)
        aDivisors[i] = GetDivisor(i);

    /*
     *  Find out amicable numbers
     */

    for (i = 0; i < max_amicables; i++) {
        if (aDivisors[i] <= 1)
            continue;
        for (j = i + 1; j < max_amicables; j++) {
            if (aDivisors[j] <= 1)
                continue;
            if (aDivisors[i] == j && aDivisors[j] == i)
                printf("%d and %d are amicable.\n", i, j);
        }
    }
}

今回もひねりも何もないですね。いや、かなりしょぼいプログラムと言わざるを得ない。Pentium 4 - 3GhzのHyper threadなPCで100,000までの友愛数を求めるのに、1分11秒ぐらいかかってしまった。興味のある方はもっと効率がよく美しいコードを書いてもらえるとyasuhoが喜びます（笑）

シンプルなだけじゃ美しいとは言えない

さて、上記プログラム。突っ込みどころが満載です。：）

最初に約数の和を求めるところは友愛数を判定するループに入れられそう。内側のループは最大数まで回してるんだけど、ループの範囲はもっと絞り込めそうです。そもそも最初から素数は除外した方がいいんじゃない！？ちょっと考えると改善すべき点がいっぱい出てきます。

ここで前述の映画からの言葉を再び引用:

神の計らいを受けた、絆で結ばれた数字なんだ。美しいと思わないかい？

数学的に美しい数字や数式というのは大多数の人の共感を得られるものだと思います。ところで、あなたはどんなプログラムを美しいと思いますか？これはとても主観的なことで、人によってまちまちなのですけど、一般にシンプルで分かりやすく、ムダがないコードがよいとされています。しかし前述のコードはシンプルではあるものの、性能的には実用に耐えるものではないでしょう。

多くのプログラムは最初とても素直に作られていて「美しい」ものが多いです。しかし度重なる機能拡張や性能改善などにより、より巨大に複雑になっていきます。プログラマが嫌う「汚いコード」になっていくのです。

しかしプログラムは使われてこそ意味があるもの。最初に作った時ほどエレガントさを保つことは難しいし、そこに固執することは必ずしもいいことではないと私は考えます。一番大事なのはやはりバランスで、うまく妥協点を見つけることができるのが優秀なプログラマであり、「美しいコード」が書ける人なのだと思います。

過去の関連記事：
yasuhoの隠れ家 - FizzBuzz問題の回答を書いてみた