反復対数のソースを表示

{{For|確率論における法則|{{仮リンク|重複対数の法則|en|Law of the iterated logarithm}}}}
[[File:Iterated_logarithm.png|thumb|right|300x300px|'''図1''' [[自然対数]]を反復する反復対数 <math>\log^* 4</math> の値が <math>2</math> であることを示す図。反復対数の値は、入力値 <math>n</math> から区間 <math>[0, 1]</math> に到達するまでの間、曲線 <math>y = \log x</math> をジグザグに移動することで求められる。ジグザグは点 <math>(n, 0)</math> から始め、次に点 <math>(n, \log n)</math>、点 <math>(0, \log n)</math>、点 <math>(\log n, 0)</math> といった順番に移動を繰り返していくことで描かれる。]]
[[計算機科学]]において、'''反復対数'''（{{Lang-en-short|iterated logarithm}}）は、結果が <math>1</math> 以下となるまでに必要とする[[対数関数]]の適用回数である<ref>{{Introduction to Algorithms|3|chapter=The iterated logarithm function, in Section 3.2: Standard notations and common functions|pages=58–59}}</ref>。

== 概要 ==
<math>n</math> についての反復対数は <math>\log^* n</math>（ログスター <math>n</math>）と表記され、単純には次のように[[再帰的定義|再帰的]]に定義される。

: <math>
\log^* n :=
\begin{cases}
0                  & \mbox{if } n \le 1; \\
1 + \log^*(\log n) & \mbox{if } n > 1
\end{cases}
</math>

関数の[[写像の反復|反復]]を用いれば、次のようにも定義できる。

: <math>\log^* n := \min\left\{i \geq 0 : \log^{(i)}n \leq 1 \right\}</math>

正の[[実数]]においては、連続性の{{仮リンク|超対数|en|super-logarithm}}に等しい。

: <math>\log^* n = \lceil \mathrm{slog}\,n \rceil</math>

言い換えれば、<math>b</math> を反復対数の底として、<math>n</math> が区間 <math>(^{y-1}b,\,^{y}b]</math> にあるとき、その反復対数は <math>\log^*_b n = y</math> で表される。ここで <math>{^{y}b} = \underbrace{b^{b^{\cdot^{\cdot^{b}}}}}_y</math> は[[テトレーション]]である。ただし、負の実数 <math>x</math> について、反復対数の値は <math>\log^* x = 0</math> であるが、<math>\lceil \mathrm{slog}\,x \rceil = -1</math> であるので、負の実数においては先に示した関係は成り立たないことになる。

反復対数は実数全体で定義され、非負整数を値域にとる。正の実数に対しては、<math>xy</math> 平面の'''図1'''において <math>x</math> 軸上の区間 <math>(0, 1]</math> に到達するために必要なジグザグの数として図式的に理解できる。

計算機科学においては、自然対数の代わりに[[二進対数]]を反復する反復対数 <math>\lg^*n := \log^*_2n</math> も用いられている。数学的には、<math>e</math> や <math>2</math> だけでなく、<math>e^{1/e} \approx 1.444667</math> より大きい任意の底に対して[[well-defined]]である。

== アルゴリズム解析 ==
{| class="wikitable floatright"
|+底が <math>\bf{2}</math> の反復対数の値
!<math>n</math>
!<math>\lg^* n</math>
|-
|<math>(-\infty, 1]</math>
|<math>0</math>
|-
|<math>(1, 2]</math>
|<math>1</math>
|-
|<math>(2, 4]</math>
|<math>2</math>
|-
|<math>(4, 16]</math>
|<math>3</math>
|-
|<math>(16, 65536]</math>
|<math>4</math>
|-
|<math>(65536, 2^{65536}]</math>
|<math>5</math>
|- style="text-align:center;"
| colspan="2" |︙
|-
|<math>(^{y-1}2,\,^{y}2]</math>
|<math>y</math>
|}
反復対数は[[アルゴリズム解析]]や[[計算複雑性理論]]の分野でよく用いられている。以下に示すアルゴリズムでは、[[時間計算量]]と{{仮リンク|空間計算量|en|Space complexity}}の限界値が反復対数で表されている。

* {{仮リンク|ユークリッド最小全域木|en|Euclidean minimum spanning tree}}が分かっている点の集合に対して[[ドロネー図|ドロネー三角形分割]]を行うアルゴリズム - <math>O(n\log^*n)</math><ref>{{cite journal
 | last = Devillers | first = Olivier
 | doi = 10.1142/S021819599200007X
 | issue = 1
 | journal = [[International Journal of Computational Geometry & Applications]]
 | mr = 1159844
 | pages = 97–111
 | title = Randomization yields simple <math>O(n\log^\ast n)</math> algorithms for difficult <math>\Omega(n)</math> problems
 | volume = 2
 | year = 1992| s2cid = 60203
 }}</ref>。
* 整数乗算の{{仮リンク|フューラーのアルゴリズム|en|Fürer's algorithm}} - <math>O(n\log^*n \cdot 2^{O(\log^* n)})</math>。
* 近似的な最大値を求めるアルゴリズム - <math>\lg^*(n - 4)</math> から <math>\lg^*(n + 2)</math> 回の演算<ref>{{cite journal
 | last1 = Alon | first1 = Noga | author1-link = Noga Alon
 | last2 = Azar | first2 = Yossi
 | doi = 10.1137/0218017
 | issue = 2
 | journal = [[SIAM Journal on Computing]]
 | mr = 986665
 | pages = 258–267
 | title = Finding an approximate maximum
 | volume = 18
 | year = 1989}}</ref>。
* {{Lang|en|Richard Cole}}と{{Lang|en|Uzi Vishkin}}による[[グラフ彩色#並列アルゴリズムと分散アルゴリズム|グラフの3彩色問題の分散アルゴリズム]] - <math>O(\log^*n)</math> 回の同期通信ステップ<ref>{{cite journal
 | last1 = Cole | first1 = Richard | author1-link = Richard J. Cole
 | last2 = Vishkin | first2 = Uzi | author2-link = Uzi Vishkin
 | doi = 10.1016/S0019-9958(86)80023-7
 | issue = 1
 | journal = [[Information and Control]]
 | mr = 853994
 | pages = 32–53
 | title = Deterministic coin tossing with applications to optimal parallel list ranking
 | volume = 70
 | year = 1986}}</ref>。

反復対数の成長は非常に遅く、対数関数よりもはるかに遅い。実装されている実際のアルゴリズムの実行時間を数えるのに十分な <math>n</math> のすべての値（すなわち <math>n \le 2^{65536} \sim 10^{19660}</math>、この最大値は[[観測可能な宇宙]]内の原子数 <math>10^{80}</math> を優に超える）に対して、底 <math>2</math> の反復対数の値はたったの <math>5</math> 以下である。

より高い底の反復対数は、より小さい値を返す。計算の複雑さの分野で使われるものでいえば、[[アッカーマン関数#逆アッカーマン関数|逆アッカーマン関数]]だけである。

== 他の応用例 ==
反復対数は、{{仮リンク|symmetric level-index arithmetic|en|symmetric level-index arithmetic}}{{訳語疑問点|date=2023年1月}}で用いられる{{仮リンク|一般化された対数関数|en|generalized logarithm function}}と密接に関係している。加法についての{{仮リンク|持続係数|en|persistence of a number}}（ある数が[[数字根]]に到達するまでに、数字をすべての桁の和で置き換える回数）は、<math>O(\log^* n)</math> である。

計算複雑性理論において、{{Lang|en|Santhanam}}<ref>{{cite conference
 | last = Santhanam | first = Rahul
 | contribution = On separators, segregators and time versus space
 | contribution-url = https://scholar.archive.org/work/jsi2cizbpbcsrkq3annbprthsm/access/wayback/http://homepages.inf.ed.ac.uk/rsanthan/Papers/segsepfinal.pdf
 | doi = 10.1109/CCC.2001.933895
 | pages = 286–294
 | publisher = [[IEEE Computer Society]]
 | title = Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001
 | title-link = Computational Complexity Conference
 | year = 2001}}</ref>によれば、[[計算資源]]の[[DTIME]]（[[チューリングマシン|決定性チューリング機械]]での計算時間）と[[NTIME]]（[[非決定性チューリング機械]]での計算時間）とが区別できるのは <math>n\sqrt{\log^*n}</math> までである。

== 脚注 ==

=== 出典 ===
{{Reflist}}

{{Normdaten}}

{{DEFAULTSORT:はんふくたいすう}}
[[Category:漸近解析]]
[[Category:対数]]
[[Category:数学に関する記事]]