「竹内関数」の版間の差分
削除された内容 追加された内容
初稿。ベンチマークに用いられる関数。 |
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 |
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では定義そのままで非常に速い。
参照
関連項目
外部リンク
- TAK Function
- Wolfram MathWorld
- どう転んでもLisp - スライド10〜13に作者自身の解説がある