新千葉 ガーベージ・コレクション

FPGA マガジンやインターフェースで書けなかったこと等をちょぼちょぼ書いてます。@ryos36

竹内関数

(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 時間を超えた。