「アッカーマンの呪い」のスタックオーバーフローの対処方法
数多くの方々の「アッカーマンの呪い」への挑戦ありがとうございます。
プログラムは再帰関数で解くのが答えとなっていますが、A(4,1), A(4,2)の計算あたりで、計算爆発が起こり、スタックオーバーフローのエラーが発生し、計算終了となってしまいます。
挑戦者からの解答も参考にしながら、対処法をいくつか、書いてみたいと思います。
A(4,1)は65533となります。
A(4,2)は 2^65536 – 3 になり、19729桁という膨大な数になってします。プログラミング言語が19729桁まで表現できるかというのも、チェックする必要があります。
1. スタックオーバーフローの対処
アッカーマン関数の計算は再帰が深くなるので、スタックサイズをできるだけ増やす必要があります。
Rubyでは、2.0で環境変数RUBY_THREAD_VM_STACK_SIZEが導入されたので、4MB等に設定してみてはどうでしょうか。
Pythonでは下記のようにsys.setrecursionlimit()でスタックサイズを増やせます。
import sys sys.setrecursionlimit(10**9)
私の環境では、これでもA(4,1)は計算できませんでした。
2. 計算結果を保持する方法
m✕nの格納場所を確保しておき、一度計算したA(m,n)の結果をメモリに保存しておくと、スタックも深くならず、計算速度も向上します。
3. m=3以下のものを公式で置き換える
この方法は挑戦者のだいじゅさんから頂いた解答です。下記のようにアッカーマン関数の公式があるので、m=3以下の場合について公式で置き換えます。
If m=0 or m=1 then A(m,n) = n + 1 + m
If m=2 then A(2,n) = 2 * n + 3
If m=3 then A(3,n) = 2^(n+3) – 3
import sys sys.setrecursionlimit(5000) def A(m, n): if m < 2: return n + 1 + m elif m == 2: return 2*n + 3 elif m == 3: return (2 ** (n+3)) - 3 elif n == 0: return A(m-1, 1) else: return A(m-1, A(m, n-1)) def do(m, n): try: return A(m, n) except RuntimeError: raise RuntimeError, "maximum recursion depth exceeded" except: print "Error" ####################### print A(4, 2)
このプログラムですと、驚くほど早くA(4,2)が求まります。
A(4,3)については、私の環境では28GBのバーチャルメモリを食い、画面は固まったまま、三日後にエラーがでて終了しました。
A(4,2)は 2^65536 – 3 になり、19729桁の十進数です。そもそも全宇宙の水素原子の数が10^80個、つまり81桁だから、既に全宇宙の水素原子数を超えている。
A(4,3)=2^(2^65536) - 3 だから、途方もない数になります。なんか、くらくらしてきた。