読者です 読者をやめる 読者になる 読者になる

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!
    } 
    ...

これで A(4, 1) はたった 34 回のループ、1ms で計算が終わります。同じロジックで long を BigInteger に修正すれば、A(4, 2) もほぼ一瞬で、19729 桁の巨大数が計算できます。


それでも A(4, 3) や A(5, 1) はこのロジックでは太刀打ちできず、Stack を確保するヒープが足りないのか計算パワーが足りないのかなどは些細な問題で、ただ単に計算不可能な巨大な数であるという圧倒的事実を前に我々は今のコンピューターの能力のちっぽけさを知ることができます。