「アッカーマンの呪い」のスタックオーバーフローの対処方法

数多くの方々の「アッカーマンの呪い」への挑戦ありがとうございます。

プログラムは再帰関数で解くのが答えとなっていますが、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 だから、途方もない数になります。なんか、くらくらしてきた。

広告

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中