「竹内関数」の版間の差分
削除された内容 追加された内容
語の定義と概要を分離、概要に特徴を追加 |
|||
1行目:
'''竹内関数
== 概要 ==
三つの[[整数]] ''x, y, z'' に対して、次のように再帰的に[[定義]]される。
<math>{\rm Tarai}(x, y, z) = \begin{cases}
7 ⟶ 10行目:
定義からわかるように処理を次々にたらいまわしにしていくことから、'''[[たらい回し|たらいまわし]]関数、[[たらい]]関数'''(''Tarai function'')とも呼ばれる（後述のマッカーシー版との混同を避けるためこの名で呼ばれることのほうが多いが、こちらの定義のほうがオリジナルである。マッカーシー版を特にTak関数として区別する場合もある）。[[日本電信電話公社|電電公社]]研究員（当時）の[[竹内郁雄]]が[[1976年]]に考案した。与える数によって関数の再帰呼び出しの回数が非常に増え、計算量が大きくなるため、コンピュータの[[ベンチマーク|性能測定]]などに用いられる。
他のよくベンチマークに使われる関数と比較して、たとえば[[フィボナッチ数]]を何の工夫もなく計算するいわゆるダム（dumb）フィボナッチと比較して、計算量を増やしても、たいして大きな数の計算が必要ない（ワード長の整数演算さえ実装していれば十分）、再帰がたいして深くならない（たいした量のスタックを使えなくても十分）、といった特性があり、関数呼び出し（と戻り）の[[オーバーヘッド]]がものをいう、というベンチマークである。
== マッカーシー版 ==
| |||