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

出典: フリー百科事典『ウィキペディア(Wikipedia)』
削除された内容 追加された内容
DoWhile (会話 | 投稿記録)
初稿。ベンチマークに用いられる関数。
 
DoWhile (会話 | 投稿記録)
m →‎本質: miss
21行目: 21行目:
<math>{\rm Tak0}(x, y, z) = \begin{cases}
<math>{\rm Tak0}(x, y, z) = \begin{cases}
y & \mbox{ if }x \le y\\
y & \mbox{ if }x \le y\\
z & \mbox{ if }x \le y \mbox { and } y \le z\\
z & \mbox{ if }x > y \mbox { and } y \le z\\
x & \mbox{ otherwise. }\\
x & \mbox{ otherwise. }\\
\end{cases}</math>
\end{cases}</math>

2007年10月3日 (水) 15:20時点における版

竹内関数(たけうちかんすう)とは三つの整数 x, y, z に対して、次のように再帰的に定義される関数である。

定義からわかるように処理を次々にたらいまわしにしていくことから、たらいまわし関数(Tarai function)とも呼ばれる(後述のマッカーシー版との混同を避けるためこの名で呼ばれることのほうが多いが、こちらの定義のほうがオリジナルである)。電電公社研究員(当時)の竹内郁雄1976年に考案した。与える数によって関数の再帰呼び出しの回数が非常に増え、計算量が大きくなるため、コンピュータの性能測定などに用いられる。

マッカーシー版

ジョン・マッカーシーは竹内関数を記憶違いで[1] z を返すように変更し、これがTak関数として広まった。以下がその定義である。

本質

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

高速化

竹内関数を高速化するには関数の再帰呼び出しのコストを小さくする必要がある。これには次のような手法がある。

一度計算した値を覚えておき、次の呼び出しではその値を使う。

クロージャなどを利用してその場では関数を計算しない(ただし、クロージャ生成のコストがかかる)。原則として遅延評価する言語であるHaskellでは定義そのままで非常に速い。

参照

  1. ^ どう転んでもLisp - スライド12

関連項目

外部リンク