反復対数

確率論における法則については「(重複対数の法則)（英語版）」をご覧ください。

計算機科学において、反復対数（英: iterated logarithm）は、結果が ${\displaystyle 1}$ 以下となるまでに必要とする対数関数の適用回数である^[1]。

図1 自然対数を反復する反復対数 ${\displaystyle \log ^{*}4}$ の値が ${\displaystyle 2}$ であることを示す図。反復対数の値は、入力値 ${\displaystyle n}$ から区間 ${\displaystyle [0,1]}$ に到達するまでの間、曲線 ${\displaystyle y=\log x}$ をジグザグに移動することで求められる。ジグザグは点 ${\displaystyle (n,0)}$ から始め、次に点 ${\displaystyle (n,\log n)}$、点 ${\displaystyle (0,\log n)}$、点 ${\displaystyle (\log n,0)}$ といった順番に移動を繰り返していくことで描かれる。

概要

${\displaystyle n}$  についての反復対数は ${\displaystyle \log ^{*}n}$ （ログスター ${\displaystyle n}$ ）と表記され、単純には次のように再帰的に定義される。

${\displaystyle \log ^{*}n:={\begin{cases}0&{\mbox{if }}n\leq 1;\\1+\log ^{*}(\log n)&{\mbox{if }}n>1\end{cases}}}$ 

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

${\displaystyle \log ^{*}n:=\min \left\{i\geq 0:\log ^{(i)}n\leq 1\right\}}$ 

正の実数においては、連続性の(超対数)（英語版）に等しい。

${\displaystyle \log ^{*}n=\lceil \mathrm {slog} \,n\rceil }$ 

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

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

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

アルゴリズム解析

底が ${\displaystyle {\bf {2}}}$  の反復対数の値

${\displaystyle n}$	${\displaystyle \lg ^{*}n}$
${\displaystyle (-\infty ,1]}$	${\displaystyle 0}$
${\displaystyle (1,2]}$	${\displaystyle 1}$
${\displaystyle (2,4]}$	${\displaystyle 2}$
${\displaystyle (4,16]}$	${\displaystyle 3}$
${\displaystyle (16,65536]}$	${\displaystyle 4}$
${\displaystyle (65536,2^{65536}]}$	${\displaystyle 5}$
︙
${\displaystyle (^{y-1}2,\,^{y}2]}$	${\displaystyle y}$

反復対数はアルゴリズム解析や計算複雑性理論の分野でよく用いられている。以下に示すアルゴリズムでは、時間計算量と(空間計算量)（英語版）の限界値が反復対数で表されている。

• (ユークリッド最小全域木)（英語版）が分かっている点の集合に対してドロネー三角形分割を行うアルゴリズム - ${\displaystyle O(n\log ^{*}n)}$ ^[2]。
• 整数乗算の(フューラーのアルゴリズム)（英語版） - ${\displaystyle O(n\log ^{*}n\cdot 2^{O(\log ^{*}n)})}$ 。
• 近似的な最大値を求めるアルゴリズム - ${\displaystyle \lg ^{*}(n-4)}$  から ${\displaystyle \lg ^{*}(n+2)}$  回の演算^[3]。
• Richard ColeとUzi Vishkinによる(グラフの3彩色問題の分散アルゴリズム) - ${\displaystyle O(\log ^{*}n)}$  回の同期通信ステップ^[4]。

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

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

他の応用例

反復対数は、(symmetric level-index arithmetic)（英語版）^{[訳語疑問点]}で用いられる(一般化された対数関数)（英語版）と密接に関係している。加法についての(持続係数)（英語版）（ある数が数字根に到達するまでに、数字をすべての桁の和で置き換える回数）は、${\displaystyle O(\log ^{*}n)}$  である。

計算複雑性理論において、Santhanam^[5]によれば、計算資源のDTIME（決定性チューリング機械での計算時間）とNTIME（非決定性チューリング機械での計算時間）とが区別できるのは ${\displaystyle n{\sqrt {\log ^{*}n}}}$  までである。

脚注

出典

1. ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990], “The iterated logarithm function, in Section 3.2: Standard notations and common functions”, Introduction to Algorithms (3rd ed.), MIT Press and McGraw-Hill, pp. 58–59, ISBN (0-262-03384-4) 
2. ^ Devillers, Olivier (1992). “Randomization yields simple ${\displaystyle O(n\log ^{\ast }n)}$  algorithms for difficult ${\displaystyle \Omega (n)}$  problems”. (International Journal of Computational Geometry & Applications) 2 (1): 97–111. doi:10.1142/S021819599200007X. MR1159844. 
3. ^ (Alon, Noga); Azar, Yossi (1989). “Finding an approximate maximum”. (SIAM Journal on Computing) 18 (2): 258–267. doi:10.1137/0218017. MR986665. 
4. ^ (Cole, Richard); (Vishkin, Uzi) (1986). “Deterministic coin tossing with applications to optimal parallel list ranking”. (Information and Control) 70 (1): 32–53. doi:10.1016/S0019-9958(86)80023-7. MR853994. 
5. ^ Santhanam, Rahul (2001). "On separators, segregators and time versus space" (PDF). (Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001). IEEE Computer Society. pp. 286–294. doi:10.1109/CCC.2001.933895。