竹内関数のソースを表示

'''竹内関数'''（たけうちかんすう）は、[[プログラミング言語]][[実装|処理系]]の[[ベンチマーク]]などに使われる、[[再帰的定義|再帰的に定義]]された[[関数 (数学)|関数]]である。

== 概要 ==
[[再帰]]的に[[定義]]される、3個の引数 ''x'', ''y'', ''z'' をとる次のような関数である。

<math>{\rm Tarai}(x, y, z) = \begin{cases}
  y & \mbox{ if }x \le y\\
  {\rm Tarai}({\rm Tarai}(x - 1, y, z), {\rm Tarai}(y - 1, z, x), {\rm Tarai}(z - 1, x, y)) & \mbox{ otherwise. }\\
\end{cases}</math>

特に変わる所は無いが[[LISP|Lisp]]版<ref>https://www.nue.org/nue/index.html#tak-function 2023年9月1日閲覧。</ref>も参照のこと。定義からわかるように処理を次々に[[たらい回し]]にしていくことから、'''たらいまわし関数'''<ref>{{Cite book |和書 |author=奥村晴彦 |authorlink=奥村晴彦 |title=C言語による最新アルゴリズム事典 |year=1991 |publisher=[[技術評論社]] |isbn=4-87408-414-1 |page=185}}</ref>、'''たらい関数''' (''Tarai function'') とも呼ばれる（後述のマッカーシー版との混同を避けるためこの名で呼ばれることのほうが多いが、こちらの定義のほうがオリジナルである。マッカーシー版を特にTak関数として区別する場合もある）。[[日本電信電話公社|電電公社]]研究員（当時）の[[竹内郁雄]]が、1974年の夏前の頃、後述するような特性のある関数をあれこれ考えていた、ある日の午前に思いついたものである<ref>{{Cite web|和書|url=http://cybozushiki.cybozu.co.jp/articles/m000434.html |title=ハッカーの遺言状──竹内郁雄の徒然苔第18回：問題児も悪くない |accessdate=2016-3-7 |author=竹内 郁雄 |authorlink=竹内郁雄 |website=サイボウズ式 |language=ja}}</ref>。竹内関数と命名したのは[[野崎昭弘]]である<ref>{{Cite book |author=野崎昭弘 |authorlink=野崎昭弘 |title=計算機数学 |year=1984 |publisher=[[共立出版]]}}</ref>。

特性として、よくベンチマークに使われる関数である[[フィボナッチ数]]を何の工夫もなく計算するいわゆるダム（dumb）フィボナッチと比較して、大きな数の計算が必要ない（ワード長の整数演算さえ実装していれば十分）、再帰が深くならない（大きな量のスタックを使えなくても十分）といったものがある。このためベンチマークとしてはその処理系の関数呼び出し（と戻り）の[[オーバーヘッド (コンピュータ)|オーバーヘッド]]の寄与度が大きい結果が計算でき、メモリの少ないハードウェアや多倍長計算が無い処理系などのような制限の大きい環境でも実装し測定できるといった特徴がある。

== マッカーシー版 ==
[[ジョン・マッカーシー]]は竹内関数を記憶違いで<ref>{{Cite web|和書|url=http://jp.franz.com/base/seminar/2005-11-18/SeminarNov2005-Takeuchi.htm |title=どう転んでもLisp |accessdate=2007-10-04 |author=竹内郁雄 |authorlink=竹内郁雄 |page=12 |archiveurl=https://web.archive.org/web/20061211233610/http://jp.franz.com/base/seminar/2005-11-18/SeminarNov2005-Takeuchi.files/v3_document.htm |archivedate=2006-12-11 |url-status=dead|url-status-date=2021-11-19}}</ref> ''z'' を返すように変更し、これが'''Tak関数'''として広まった。以下がその定義である。

<math>{\rm Tak}(x, y, z) = \begin{cases}
  z & \mbox{ if }x \le y\\
  {\rm Tak}({\rm Tak}(x - 1, y, z), {\rm Tak}(y - 1, z, x), {\rm Tak}(z - 1, x, y)) & \mbox{ otherwise. }\\
\end{cases}</math>

計算量はずっと少ない（たとえば tarai(12, 6, 0) では 12,604,860 回 tarai が呼ばれるのに対し、 tak(12, 6, 0) では tak は 63,608 回しか呼ばれない）。

== 本質 ==
竹内関数の出力は以下のものと同等である。

<math>{\rm T0}(x, y, z) = \begin{cases}
  y & \mbox{ if }x \le y\\
  z & \mbox{ if }x > y \mbox { and } y \le z\\
  x & \mbox{ otherwise. }\\
\end{cases}</math>

[[ドナルド・クヌース]]による研究が、Textbook Examples of Recursion(1990)にある。

== 高速化 ==
竹内関数を高速化するには、関数呼び出しのコストを小さくする、というまっとうな手法と、計算を必要になるまでやらない（引数のx, y, zの値が実際に必要なのは、関数の呼び出し時でなくifの評価時で、しかも常に全部は必要としない）か、一度やった計算の結果を再利用するかして、計算量自体を削減する（当然非常に速い。ベンチマークとしては一種のチートと言えなくもない）手法とがあり、後者には次のような手法がある。

; [[メモ化]]
: 一度計算した値を覚えておき、次の呼び出しではその値を使う。
; [[遅延評価]]
: [[クロージャ]]などを利用して、関数呼び出しの計算より前に引数を計算すること（[[先行評価]]）をしない（ただし、クロージャ生成のコストがかかる）。原則として遅延評価する言語である[[Haskell]]では定義そのままで非常に速い。他にも[[Scala]]など遅延評価に対応した言語においては、簡単に、非常に高速に評価が終わるコードを作成できる。

マッカーシー版は、メモ化では同様に速い。しかし、マッカーシー版をHaskellなどでそのままの定義で遅延評価した場合は、高速にならない（遅延評価では計算量が減らない）、という違いがある。これは少し動作を追いかけて考えてみるとわかるが、本物では z の値をたらいまわしした挙句に結局使っていない（捨ててしまっている）ため、遅延評価ではその計算がごっそり行われなくなるからである。マッカーシー版では z を返しているため結局その値が必要になっている、という違いになっている。先行評価による tarai(n, 0, n+1) の計算全体において「さもなくば」の側が評価される回数をTakeuchi Numberと言う<ref>{{Cite web |url=https://mathworld.wolfram.com/TakeuchiNumber.html |title=Takeuchi Number |accessdate=2015年6月22日 |last=Weisstein |first=Eric W. |website=mathworld.wolfram.com |language=en}}</ref>。

== 感覚化 ==
数値データ等を視覚や聴覚でとらえられるようにすることがあるが（視覚の場合[[可視化]]という）、竹内関数の引数の値に音階を割り振り、3個の引数で和音のような音にした試みがある<ref>{{Cite web|和書|url=https://aike.hatenablog.com/entry/20111112 |title=竹内関数で音楽生成 |accessdate=2011-11-15 |author=aike |website=aike’s blog |language=ja}}</ref>。

== 参照 ==
<references />

== 関連項目 ==
* [[アッカーマン関数]]

== 外部リンク ==
* [http://mathworld.wolfram.com/TAKFunction.html Wolfram MathWorld]

{{DEFAULTSORT:たけうちかんすう}}
[[Category:特殊関数]]
[[Category:計算理論]]
[[Category:数学に関する記事]]