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

履歴の双方向閲覧

← 古い編集新しい編集 →

削除された内容追加された内容

ビジュアルウィキテキスト

インライン

2020年10月25日 (日) 14:07時点における版

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

概要

再帰的に定義される、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}}$

定義からわかるように処理を次々にたらい回しにしていくことから、たらいまわし関数^[1]、たらい関数 (Tarai function) とも呼ばれる（後述のマッカーシー版との混同を避けるためこの名で呼ばれることのほうが多いが、こちらの定義のほうがオリジナルである。マッカーシー版を特にTak関数として区別する場合もある）。電電公社研究員（当時）の竹内郁雄が、1974年の夏前の頃、後述するような特性のある関数をあれこれ考えていた、ある日の午前に思いついたものである^[2]。竹内関数と命名したのは野崎昭弘である^[3]。

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

マッカーシー版

ジョン・マッカーシーは竹内関数を記憶違いで^[4] 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と言う^[5]。

感覚化

数値データ等を視覚や聴覚でとらえられるようにすることがあるが（視覚の場合可視化という）、竹内関数の引数の値に音階を割り振り、3個の引数で和音のような音にした試みがある^[6]。

参照

^ 奥村晴彦『C言語による最新アルゴリズム事典』技術評論社、1991年、185頁。ISBN 4-87408-414-1。
^ ハッカーの遺言状──竹内郁雄の徒然苔第18回：問題児も悪くない | サイボウズ式
^ 野崎昭弘『計算機数学』（共立出版、1984年）
^ どう転んでもLisp - スライド12
^ Weisstein, Eric W. "Takeuchi Number." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/TakeuchiNumber.html
^ http://d.hatena.ne.jp/aike/20111112

外部リンク

Wolfram MathWorld

[1] 奥村晴彦『C言語による最新アルゴリズム事典』技術評論社、1991年、185頁。ISBN 4-87408-414-1。

[2] ハッカーの遺言状──竹内郁雄の徒然苔第18回：問題児も悪くない | サイボウズ式

[3] 野崎昭弘『計算機数学』（共立出版、1984年）

[4] どう転んでもLisp - スライド12

[5] Weisstein, Eric W. "Takeuchi Number." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/TakeuchiNumber.html

[6] ttp://d.hatena.ne.jp/aike/20111112

[1]

[2]

[3]

[4]

[5]

[6]

@@ 9行目: / 9行目: @@
 \end{cases}</math>
-定義からわかるように処理を次々に[[たらい回し]]にしていくことから、'''たらいまわし関数'''<ref>{{cite book | 1=和書 | title=C言語による最新アルゴリズム事典 | publisher=[[技術評論社]] | author=奥村晴彦 | authorlink=奥村晴彦 | year=1991 | page=185 | isbn=4-87408-414-1}}</ref>、'''たらい関数''' (''Tarai function'') とも呼ばれる（後述のマッカーシー版との混同を避けるためこの名で呼ばれることのほうが多いが、こちらの定義のほうがオリジナルである。マッカーシー版を特にTak関数として区別する場合もある）。[[日本電信電話公社|電電公社]]研究員（当時）の[[竹内郁雄]]が、1974年の夏前の頃、このような特性のある関数をあれこれ考えていた、ある日の午前に思いついたものである<ref>[http://cybozushiki.cybozu.co.jp/articles/m000434.html ハッカーの遺言状──竹内郁雄の徒然苔第18回：問題児も悪くない | サイボウズ式]</ref>。竹内関数と命名したのは[[野崎昭弘]]である<ref>[[野崎昭弘]]『計算機数学』（[[共立出版]]、1984年）</ref>。与える数によって関数の再帰呼び出しの回数が非常に増え、計算量が大きくなるため、コンピュータの性能測定などに用いられる。
+定義からわかるように処理を次々に[[たらい回し]]にしていくことから、'''たらいまわし関数'''<ref>{{cite book | 1=和書 | title=C言語による最新アルゴリズム事典 | publisher=[[技術評論社]] | author=奥村晴彦 | authorlink=奥村晴彦 | year=1991 | page=185 | isbn=4-87408-414-1}}</ref>、'''たらい関数''' (''Tarai function'') とも呼ばれる（後述のマッカーシー版との混同を避けるためこの名で呼ばれることのほうが多いが、こちらの定義のほうがオリジナルである。マッカーシー版を特にTak関数として区別する場合もある）。[[日本電信電話公社|電電公社]]研究員（当時）の[[竹内郁雄]]が、1974年の夏前の頃、後述するような特性のある関数をあれこれ考えていた、ある日の午前に思いついたものである<ref>[http://cybozushiki.cybozu.co.jp/articles/m000434.html ハッカーの遺言状──竹内郁雄の徒然苔第18回：問題児も悪くない | サイボウズ式]</ref>。竹内関数と命名したのは[[野崎昭弘]]である<ref>[[野崎昭弘]]『計算機数学』（[[共立出版]]、1984年）</ref>。
-他のよくベンチマークに使われる関数と比較して、たとえば[[フィボナッチ数]]を何の工夫もなく計算するいわゆるダム（dumb）フィボナッチと比較して、計算量を増やしても、たいして大きな数の計算が必要ない（ワード長の整数演算さえ実装していれば十分）、再帰がたいして深くならない（たいした量のスタックを使えなくても十分）、といった特性があり、関数呼び出し（と戻り）の[[オーバーヘッド]]がものをいう、というベンチマークである。
+特性として、他のよくベンチマークに使われる関数と比較して、たとえば[[フィボナッチ数]]を何の工夫もなく計算するいわゆるダム（dumb）フィボナッチと比較して、計算量を増やしても、たいして大きな数の計算が必要ない（ワード長の整数演算さえ実装していれば十分）、再帰がたいして深くならない（たいした量のスタックを使えなくても十分）、といったものがある。このためベンチマークとしては、その処理系の関数呼び出し（と戻り）の[[オーバーヘッド]]に集中して結果が出ること、メモリの少ないハードウェアや多倍長計算がまだ無い処理系などのような実験的な環境でも実装し測定できること、といった特徴がある。
 == マッカーシー版 ==

2020年10月25日 (日) 14:07時点における版

概要

マッカーシー版

本質

高速化

感覚化

参照

関連項目

外部リンク