竹内たけうち関数かんすう

竹内たけうち関数かんすう（たけうちかんすう）は、プログラミング言語げんご処理しょり系けいのベンチマークなどに使つかわれる、再帰さいき的てきに定義ていぎされた関数かんすうである。

概要がいよう

再帰さいき的てきに定義ていぎされる、3個この引数ひきすう x, y, z をとる次つぎのような関数かんすうである。

${\rm {Tarai}}(x,y,z)={\begin{cases}y&{\mbox{ if }}x\leq 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}}$

特とくに変かわる所ところは無ないがLisp版はんも参照さんしょうのこと。定義ていぎからわかるように処理しょりを次々つぎつぎにたらい回まわしにしていくことから、たらいまわし関数かんすう、たらい関数かんすう (Tarai function) とも呼よばれる（後述こうじゅつのマッカーシー版ばんとの混同こんどうを避さけるためこの名なで呼よばれることのほうが多おおいが、こちらの定義ていぎのほうがオリジナルである。マッカーシー版ばんを特とくにTak関数かんすうとして区別くべつする場合ばあいもある）。電電でんでん公社こうしゃ研究けんきゅう員いん（当時とうじ）の竹内たけうち郁雄いくおが、1974年ねんの夏なつ前まえの頃ころ、後述こうじゅつするような特性とくせいのある関数かんすうをあれこれ考かんがえていた、ある日ひの午前ごぜんに思おもいついたものである。竹内たけうち関数かんすうと命名めいめいしたのは野崎のさき昭弘あきひろである。

特性とくせいとして、他たのよくベンチマークに使つかわれる関数かんすうと比較ひかくして、たとえばフィボナッチ数すうを何なんの工夫くふうもなく計算けいさんするいわゆるダム（dumb）フィボナッチと比較ひかくして、計算けいさん量りょうを増ふやしても、たいして大おおきな数かずの計算けいさんが必要ひつようない（ワード長ちょうの整数せいすう演算えんざんさえ実装じっそうしていれば十分じゅうぶん）、再帰さいきがたいして深ふかくならない（たいした量りょうのスタックを使つかえなくても十分じゅうぶん）、といったものがある。このためベンチマークとしては、その処理しょり系けいの関数かんすう呼よび出だし（と戻もどり）のオーバーヘッドに集中しゅうちゅうして結果けっかが出でること、メモリの少すくないハードウェアや多倍たばい長ちょう計算けいさんがまだ無ない処理しょり系けいなどのような実験じっけん的てきな環境かんきょうでも実装じっそうし測定そくていできること、といった特徴とくちょうがある。

マッカーシー版ばん

ジョン・マッカーシーは竹内たけうち関数かんすうを記憶きおく違ちがいで z を返かえすように変更へんこうし、これがTak関数かんすうとして広ひろまった。以下いかがその定義ていぎである。

${\rm {Tak}}(x,y,z)={\begin{cases}z&{\mbox{ if }}x\leq 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}}$

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

本質ほんしつ

竹内たけうち関数かんすうの出力しゅつりょくは以下いかのものと同等どうとうである。

${\rm {T0}}(x,y,z)={\begin{cases}y&{\mbox{ if }}x\leq y\\z&{\mbox{ if }}x>y{\mbox{ and }}y\leq z\\x&{\mbox{ otherwise. }}\\\end{cases}}$

ドナルド・クヌースによる研究けんきゅうが、Textbook Examples of Recursion(1990)にある。

高速こうそく化か

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

メモ化か

一度いちど計算けいさんした値ねを覚おぼえておき、次つぎの呼よび出だしではその値ねを使つかう。

遅延ちえん評価ひょうか

クロージャなどを利用りようして、関数かんすう呼よび出だしの計算けいさんより前まえに引数ひきすうを計算けいさんすること（先行せんこう評価ひょうか）をしない（ただし、クロージャ生成せいせいのコストがかかる）。原則げんそくとして遅延ちえん評価ひょうかする言語げんごであるHaskellでは定義ていぎそのままで非常ひじょうに速はやい。他ほかにもScalaなど遅延ちえん評価ひょうかに対応たいおうした言語げんごにおいては、簡単かんたんに、非常ひじょうに高速こうそくに評価ひょうかが終おわるコードを作成さくせいできる。

マッカーシー版ばんは、メモ化かでは同様どうように速はやい。しかし、マッカーシー版ばんをHaskellなどでそのままの定義ていぎで遅延ちえん評価ひょうかした場合ばあいは、高速こうそくにならない（遅延ちえん評価ひょうかでは計算けいさん量りょうが減へらない）、という違ちがいがある。これは少すこし動作どうさを追おいかけて考かんがえてみるとわかるが、本物ほんものでは z の値ねをたらいまわしした挙句あげくに結局けっきょく使つかっていない（捨すててしまっている）ため、遅延ちえん評価ひょうかではその計算けいさんがごっそり行おこなわれなくなるからである。マッカーシー版ばんでは z を返かえしているため結局けっきょくその値ねが必要ひつようになっている、という違ちがいになっている。先行せんこう評価ひょうかによる tarai(n, 0, n+1) の計算けいさん全体ぜんたいにおいて「さもなくば」の側がわが評価ひょうかされる回数かいすうをTakeuchi Numberと言いう。

感覚かんかく化か

数値すうちデータ等とうを視覚しかくや聴覚ちょうかくでとらえられるようにすることがあるが（視覚しかくの場合ばあい可視かし化かという）、竹内たけうち関数かんすうの引数ひきすうの値ねに音階おんかいを割わり振ふり、3個この引数ひきすうで和音わおんのような音おとにした試こころみがある。

関連かんれん項目こうもく

• アッカーマン関数かんすう

外部がいぶリンク

• Wolfram MathWorld