「竹内関数」の版間の差分

編集の要約なし
(→‎高速化: Scalaでも遅延評価関数で書けばネイティブには適いませんが同様に高速化できます)
'''竹内関数'''(たけうちかんすう)とは三つの[[整数]] ''x, y, z'' に対して、次のように再帰的に[[定義]]される[[関数 (数学)|関数]]である。
 
<math>{\rm TakTarai}(x, y, z) = \begin{cases}
y & \mbox{ if }x \le y\\
{\rm TakTarai}({\rm TakTarai}(x - 1, y, z), {\rm TakTarai}(y - 1, z, x), {\rm TakTarai}(z - 1, x, y)) & \mbox{ otherwise. }\\
\end{cases}</math>
 
定義からわかるように処理を次々にたらいまわしにしていくことから、'''[[たらい回し|たらいまわし]]関数、[[たらい]]関数'''(''Tarai function'')とも呼ばれる(後述のマッカーシー版との混同を避けるためこの名で呼ばれることのほうが多いが、こちらの定義のほうがオリジナルである。マッカーシー版を特にTak関数として区別する場合もある)。[[日本電信電話公社|電電公社]]研究員(当時)の[[竹内郁雄]]が[[1976年]]に考案した。与える数によって関数の再帰呼び出しの回数が非常に増え、計算量が大きくなるため、コンピュータの[[ベンチマーク|性能測定]]などに用いられる。
 
== マッカーシー版 ==
{\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>
 
計算量はずっと少ない。
 
== 本質 ==
竹内関数の出力は以下のものと同等である。
 
<math>{\rm Tak0T0}(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の評価時である)か、一度やった計算の結果を再利用するかして、計算量自体を削減する(当然非常に速いこれベンチマークとしては一種のチートと言えなくもない)手法とがあり、後者には次のような手法がある。
 
* [[メモ化]]