Java でアッカーマン関数を実装しよう

アッカーマン関数という関数がある。
この関数はとても巨大な値を返し、またその計算に多大な計算量が必要なことが知られている。

定義自体は単純で、下記の通り。

f:id:shawshank99:20150630160633p:plain

これを Java で実装してみましょう。

コードの読みやすさのために整数型に long を用いてますが、アッカーマン関数様の前では 64bit で表せる範囲なんてものは素粒子以下の存在でしかないので、もう少しまともな計算をしたい場合は
BigInteger を使う必要があります。

ではシンプルな実装。

public long ack(long m, long n) {
    if (m == 0) {
        return n + 1;
    } else if (n == 0) {
        return ack(m - 1, 1);
    } else {
        return ack(m - 1, ack(m, n - 1));
    }
}

極めてシンプル、定義の直訳。

テストしてみるとちゃんと動いていることがわかります。

System.out.println(ack(3, 1)); // 13
System.out.println(ack(3, 2)); // 29
System.out.println(ack(4, 0)); // 13

ただ、残念ながら ack(4, 1) は動きません。
あまりにスタックが深くなる故にスタックオーバーフローを起こしてしまうのです。

では再帰を使わずにアッカーマン関数を実装し、ack(4,1) を実行できるようチャレンジしてみましょう。
考え方としては、アッカーマン関数を展開していく時の処理を数列として捉えること。
アッカーマン関数を A として、A(2, 1) を例に取って考えると、

A(2, 1)
= A(1, A(2, 0))
= A(1, A(1, 1))
= A(1, A(0, A(1, 0)))
= A(1, A(0, A(0, 1)))
= A(1, A(0, A(2)))
= A(1, 3)
= A(0, A(1, 2))
= A(0, A(0, A(1, 1)))
= A(0, A(0, A(0, A(1, 0))))
= A(0, A(0, A(0, A(0, 1))))
= A(0, A(0, A(0, 2)))
= A(0, A(0, 3))
= A(0, 4)
= 5

と展開されるわけです。この時、関数呼び出しについては一旦忘れて、数値だけを書き出すとこうなります。

[2, 1]
[1, 2, 0]
[1, 1, 1]
[1, 0, 1, 0]
[1, 0, 0, 1]
[1, 0, 2]
[1, 3]
[0, 1, 2]
[0, 0, 1, 1]
[0, 0, 0, 1, 0]
[0, 0, 0, 0, 1]
[0, 0, 0, 2]
[0, 0, 3]
[0, 4]
[5]

見えてきましたね。スタック構造を用いて、先頭(右側)2つの値を pop して、これを m, n とみなし、次の値を push すれば良いのです。

では早速実装。

public long ack(long m, long n) {
    Stack<Long> stack = new Stack<>();
    stack.push(m);
    stack.push(n);
    return extract(stack);
}

private long extract(Stack<Long> stack) {
    while (stack.size() > 1) {
        long n = stack.pop();
        long m = stack.pop();
        if (m == 0) {
            stack.push(n + 1);
        } else if (n == 0) {
            stack.push(m - 1);
            stack.push(1L);
        } else {
            stack.push(m - 1);
            stack.push(m);
            stack.push(n - 1);
        }
    }

    return stack.pop();
}

はい。再帰が無くなりました。もちろんうまく動いて、A(4, 1) も計算できます。

System.out.println(ack(3, 1)); // 13
System.out.println(ack(3, 2)); // 29
System.out.println(ack(4, 0)); // 13
System.out.println(ack(4, 1)); // 65533

計算できるとはいえ膨大な計算量を誇るアッカーマン関数、ack(4, 1) では実に 2862984010 回のループ、計算時間は Core i7 3770 を用いても約 400 秒かかりました。ベンチマークにはそれで良いのですが、我々プログラマは一般人と違って、急ぎでアッカーマン関数の値を知りたいことがしばしばあります。計算量の短縮を目的にちょっとコードに手を入れてみましょう。

先ほどの A(2, 1) の展開時の数列の、右から二番目、つまり m の値に注目してください。

[2, 1]
[1, 2, 0]
[1, 1, 1]
[1, 0, 1, 0]
[1, 0, 0, 1]
[1, 0, 2]
[1, 3]
[0, 1, 2]
[0, 0, 1, 1]
[0, 0, 0, 1, 0]
[0, 0, 0, 0, 1]
[0, 0, 0, 2]
[0, 0, 3]
[0, 4]
[5]

n != 0 かつ m が 1 の時、その後スタックが成長して元に戻ると m の部分には n + 2 が格納されています。例えば [1, 1, 1] は [1, 3] に、[0, 1, 2] は [0, 4] へと変化しています。
このショートカットを先ほどのコードに織り込んでしまいましょう。

public long extract(Stack<Long> stack) {
    while (stack.size() > 1) {
        long n = stack.pop();
        long m = stack.pop();
        if (m == 0) {
            stack.push(n + 1);
        } else if (n == 0) {
            stack.push(m - 1);
            stack.push(1L);
        } else if (m == 1) {
            stack.push(n + 2); // customize!
        } else {
            stack.push(m - 1);
            stack.push(m);
            stack.push(n - 1);
        }
    }

    return stack.pop();
}

たったこれだけで、A(4, 1) は 131042 回のループ、計算時間は 41ms で終わるようになりました。
さらに改良し、m == 2 の時、計算後は n*2 + 3 が格納されることを利用してコードを修正します。

    ...
    else if (m == 1) {
        stack.push(n + 2); // customize!
    } else if (m == 2) {
        stack.push(n * 2 + 3); // customize!
    } 
    ...