竹内関数
(defun tak (x y z) (declare (type fixnum x y z) (optimize (speed 3) (safety 0))) (if (<= x y) y (tak (tak (1- x) y z) (tak (1- y) z x) (tak (1- z) x y))))
上の関数が正しい竹内関数。これを z を返すようにした tak-z を作ると挙動が違う。上の正しい、tak を sbcl にロードして実行する。ついでにどのような挙動をするか trace もする。
* (tak 2 1 0) 0: (TAK 2 1 0) 0: TAK returned 2 2 * (tak 4 2 0) 0: (TAK 4 2 0) 0: TAK returned 4 4 * (tak 5 2 0) 0: (TAK 5 2 0) 0: TAK returned 5 5
どうやら、竹内関数に対して最適化がかかっているようで、再帰呼び出しをしない。そこで、tak0, tak1, tak2, tak3 をつくって必ず再帰するようにしてみる。
(defun tak (x y z) (declare (type fixnum x y z) (optimize (speed 3) (safety 0))) (if (<= x y) y (tak0 (tak1 (1- x) y z) (tak2 (1- y) z x) (tak3 (1- z) x y)))) (defun tak0 (x y z) (tak x y z)) (defun tak1 (x y z) (tak x y z)) (defun tak2 (x y z) (tak x y z)) (defun tak3 (x y z) (tak x y z))
さすがにこれだと最適化がかからないので再帰呼び出しをする。
(tak 2 1 0) 0: (TAK 2 1 0) 1: (TAK 1 1 0) 1: TAK returned 1 1: (TAK 0 0 2) 1: TAK returned 0 1: (TAK -1 2 1) 1: TAK returned 2 1: (TAK 1 0 2) 2: (TAK 0 0 2) 2: TAK returned 0 2: (TAK -1 2 1) 2: TAK returned 2 2: (TAK 1 1 0) 2: TAK returned 1 2: (TAK 0 2 1) 2: TAK returned 2 1: TAK returned 2 0: TAK returned 2 2
Lisp の評価には tak を使うことが多いので、(どんな最適化をしているのか知らないが、、、、)チューンアップしている処理系があるのに注意しないといけない。
* (time (tak 18 9 0)) Evaluation took: 11953.700 seconds of real time 11930.029327 seconds of total run time (11930.029204 user, 0.000123 system) 99.80% CPU 25,437,473,556,842 processor cycles 0 bytes consed 18
結局、実行時間は sbcl で 3 時間を超えた。