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

CodeIQ Blog

自分の実力を知りたいITエンジニア向けの、実務スキル評価サービス「CodeIQ(コードアイキュー)」の公式ブログです。

「アッカーマンの呪い」問題解説~進撃の巨人みたいに爆発的な大きな数字は案外簡単な式で実現できます #ackermann #python

問題解説

CodeIQ中の人、millionsmileです。

「昔、アッカーマンという人(残念ながらミカサという妙齢の女性ではありません)がいました。」

一瞬、ざわめきを感じる出だしで始まる今回の問題は、アッカーマン関数を使って、計算爆発を体験してみようというものでした。

出題者は空飛ぶデータサイエンティストである川頭信之さんです!

この問題、川頭さんの大学時代の経験がきっかけで思いついたそうですよ。

アッカーマンというと進撃の巨人か!?と思ったりするんですが、その辺についても解説記事に書かれているので、読んでみてください。

◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇

CodeIQに投稿した「アッカーマンの呪い」の解答を解説します。

f:id:codeiq:20130902123528p:plain

問題

昔、アッカーマンという人(残念ながらミカサという妙齢の女性ではありません)がいました。
その人の手帳には以下のような式が書かれていました。

A(m, n) =
m = 0 ならば n + 1
n = 0 ならば A(m - 1, 1)
他の場合は A(m - 1, A(m, n - 1))

この関数を計算してみましょう。
A(1,3)の場合は以下のようになります。

 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

問1A
A(2,1)を手で計算してみましょう。
(解答を提出する必要はありません)

問1B
気力のある人はA(2,2)を手で計算してみましょう。
(解答を提出する必要はありません)

問2A
再帰関数を使ってプログラムを書いてみましょう。
プログラミング言語は問いません。

A(3,4) の値はいくつになりますか。
答えと使った言語名のみを書いて提出してください。
プログラムの提出は必要ありません。

問2B
A(4,1) をプログラムで計算してみましょう。
ただし、スタックオバーフローのエラーが出る恐れがありますので、
パラメータ値の増加には十分注意してください。
ハングアップする恐れがあるので、他の重要なプログラムが走っているときは実行するの
はやめたほうが良いです。
(もし値が計算できたら、3行目に答を書いてください)

【解答方法】
テキストファイルに以下のように解答を書いてください。
完成しましたら、ファイルアップロードより提出してください。

???   # 1 行目 問2Aの答え
???   # 2 行目 プログラミング言語名
???   # 3 行目 問2Bの答え(計算出来なかったら空欄でも構いません)

【補足】
A(4,1) は何とか計算できるかもしれませんが、
A(4,2) はあまりにも値が大きいので普通の方法では計算できないでしょう。

LISP等を使った方がすんなり行くかもしれません。

コンピュータを壊さないように気をつけて頑張ってください。

解説

挑戦ありがとうございます。好評につき、99名の方々が挑戦してくれました。

今回の問題はWilhelm Friedrich Ackermannというドイツの数学者が考案したアッカーマン関数を問題としました。残念ながら、進撃の巨人とは何の関係もありません。(ただし、進撃の巨人の舞台がドイツらしいので関係なくはありませんが...)

言語不問とのことでしたが、使用言語ランキングはRuby(18名)がトップで、2位以降はC(14名)、Java(13名)、Haskell(13名)という順位となりました。Haskellの躍進はこの問題が再帰関数だったからでしょうか。

手計算の結果は以下の通りです。何度も再帰的に計算しているが視覚的に分かるように省略せずに全過程を書いてみました。僅かな数なのに再帰が深くなっているのが分かるでしょうか。

問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,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.2

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

アッカーマン関数は、自分自身を値として取る再帰関数ですが、簡単な定義にも関わらず、最初の部分でさえ爆発的に大きな値が現れてしまいます。

Wikipedia:アッカーマン関数より転載

私が大学の夏期特別講座でこのアッカーマン関数を知りました。当時は、コンピュータは一般的には存在せず、共有の大型コンピュータをかろうじて使うことが出来ましたが、一行書くのに一回リターンキーを押してしまうと二、三分待たなければ、レスポンスが帰ってこないと言う有様でした。年がバレてしまいますがwww。

ですから、自分でこの関数をコンピュータでプログラミングするなんてできませんから、手で計算したのです。ところが、小さな値で計算を始めたにも関わらず、なかなか答えが収束せず、大変な思いをしました。その時、友人が書きすぎて手が痛くなったので、「これはアッカーマンの呪いだ!」と叫んでいました。そこで、これを今回の問題のタイトルにしたというわけです。

Pythonでのプログラミングの例

def ack(m, n):

    if m == 0:
        return n + 1
    if n == 0:
        return ack(m - 1, 1)
    else:
        return ack(m - 1, ack(m, n - 1))

###
print ack(3,4)

問2A
A(3,4)の答えは125。

問2B
A(4,1)の答えは65533となります。

既にA(4,1)でコンピュータがエラーを吐き出し始めるかと思います。私のUbuntuの場合、パラメータをいじったのですが、A(4,1)はスタックオーバーフローで計算できませんでした。

A(4,2)は 2^65536 – 3 になり、19729桁という膨大な数になってします。プログラミング言語が19729桁まで表現できるかというのも、チェックする必要があります。

プログラムは再帰関数で解くのが答えとなっていますが、A(4,1), A(4,2)の計算あたりで、計算爆発が起こり、スタックオーバーフローのエラーが発生し、計算終了となってしまいます。
挑戦者からの解答も参考にしながら、対処法をいくつか、書いてみたいと思います。

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

この計算ですと、驚くほど早くA(4,2)が求まります。
A(4,3)については、私の環境では28GBのバーチャルメモリを食い、画面は固まったまま、三日後にエラーがでて終了しました。
A(4,2)は 2^65536 – 3 になり、19729桁の十進数です。そもそも全宇宙の水素原子の数が10^80個、つまり81桁だから、既に全宇宙の水素原子数を超えている。
A(4,3)=2^(2^65536) - 3 だから、途方もない数になります。なんか、くらくらしてきた。

とにかく、こんな簡単な式でこんな爆発的に大きな数が作れるなんて不思議ですね。しかも、コンピュータの普及していない時代にこんな関数を考えだすなんて数学者ってすごいなと思います。

◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇

CodeIQ中の人後記:
iPad miniを手に入れたんですが、ゲームと読書くらいしか使用用途を思いつかないです。

エンジニアのための新しい転職活動!CodeIQのウチに来ない?の特集ページを見る