確率論における法則については「重複対数の法則(英語版) 」をご覧ください。
図1 自然対数 を反復する反復対数 log ∗ 4 {\displaystyle \log ^{*}4} の値が 2 {\displaystyle 2} であることを示す図。反復対数の値は、入力値 n {\displaystyle n} から区間 [ 0 , 1 ] {\displaystyle [0,1]} に到達するまでの間、曲線 y = log x {\displaystyle y=\log x} をジグザグに移動することで求められる。ジグザグは点 ( n , 0 ) {\displaystyle (n,0)} から始め、次に点 ( n , log n ) {\displaystyle (n,\log n)} 、点 ( 0 , log n ) {\displaystyle (0,\log n)} 、点 ( log n , 0 ) {\displaystyle (\log n,0)} といった順番に移動を繰り返していくことで描かれる。 計算機科学 において、反復対数 (英 : iterated logarithm )は、結果が 1 {\displaystyle 1} 以下となるまでに必要とする対数関数 の適用回数である[1] 。
概要 n {\displaystyle n} についての反復対数は log ∗ n {\displaystyle \log ^{*}n} (ログスター n {\displaystyle n} )と表記され、単純には次のように再帰的 に定義される。
log ∗ n := { 0 if n ≤ 1 ; 1 + log ∗ ( log n ) if n > 1 {\displaystyle \log ^{*}n:={\begin{cases}0&{\mbox{if }}n\leq 1;\\1+\log ^{*}(\log n)&{\mbox{if }}n>1\end{cases}}} 関数の反復 を用いれば、次のようにも定義できる。
log ∗ n := min { i ≥ 0 : log ( i ) n ≤ 1 } {\displaystyle \log ^{*}n:=\min \left\{i\geq 0:\log ^{(i)}n\leq 1\right\}} 正の実数 においては、連続性の超対数(英語版) に等しい。
log ∗ n = ⌈ s l o g n ⌉ {\displaystyle \log ^{*}n=\lceil \mathrm {slog} \,n\rceil } 言い換えれば、 b {\displaystyle b} を反復対数の底として、 n {\displaystyle n} が区間 ( y − 1 b , y b ] {\displaystyle (^{y-1}b,\,^{y}b]} にあるとき、その反復対数は log b ∗ n = y {\displaystyle \log _{b}^{*}n=y} で表される。ここで y b = b b ⋅ ⋅ b ⏟ y {\displaystyle {^{y}b}=\underbrace {b^{b^{\cdot ^{\cdot ^{b}}}}} _{y}} はテトレーション である。ただし、負の実数 x {\displaystyle x} について、反復対数の値は log ∗ x = 0 {\displaystyle \log ^{*}x=0} であるが、 ⌈ s l o g x ⌉ = − 1 {\displaystyle \lceil \mathrm {slog} \,x\rceil =-1} であるので、負の実数においては先に示した関係は成り立たないことになる。
反復対数は実数全体で定義され、非負整数を値域にとる。正の実数に対しては、 x y {\displaystyle xy} 平面の図1 において x {\displaystyle x} 軸上の区間 ( 0 , 1 ] {\displaystyle (0,1]} に到達するために必要なジグザグの数として図式的に理解できる。
計算機科学においては、自然対数の代わりに二進対数 を反復する反復対数 lg ∗ n := log 2 ∗ n {\displaystyle \lg ^{*}n:=\log _{2}^{*}n} も用いられている。数学的には、 e {\displaystyle e} や 2 {\displaystyle 2} だけでなく、 e 1 / e ≈ 1.444667 {\displaystyle e^{1/e}\approx 1.444667} より大きい任意の底に対してwell-defined である。
アルゴリズム解析 底が 2 {\displaystyle {\bf {2}}} の反復対数の値 n {\displaystyle n} lg ∗ n {\displaystyle \lg ^{*}n} ( − ∞ , 1 ] {\displaystyle (-\infty ,1]} 0 {\displaystyle 0} ( 1 , 2 ] {\displaystyle (1,2]} 1 {\displaystyle 1} ( 2 , 4 ] {\displaystyle (2,4]} 2 {\displaystyle 2} ( 4 , 16 ] {\displaystyle (4,16]} 3 {\displaystyle 3} ( 16 , 65536 ] {\displaystyle (16,65536]} 4 {\displaystyle 4} ( 65536 , 2 65536 ] {\displaystyle (65536,2^{65536}]} 5 {\displaystyle 5} ︙ ( y − 1 2 , y 2 ] {\displaystyle (^{y-1}2,\,^{y}2]} y {\displaystyle y}
反復対数はアルゴリズム解析 や計算複雑性理論 の分野でよく用いられている。以下に示すアルゴリズムでは、時間計算量 と空間計算量(英語版) の限界値が反復対数で表されている。
ユークリッド最小全域木(英語版) が分かっている点の集合に対してドロネー三角形分割 を行うアルゴリズム - O ( n log ∗ n ) {\displaystyle O(n\log ^{*}n)} [2] 。 整数乗算のフューラーのアルゴリズム(英語版) - O ( n log ∗ n ⋅ 2 O ( log ∗ n ) ) {\displaystyle O(n\log ^{*}n\cdot 2^{O(\log ^{*}n)})} 。 近似的な最大値を求めるアルゴリズム - lg ∗ ( n − 4 ) {\displaystyle \lg ^{*}(n-4)} から lg ∗ ( n + 2 ) {\displaystyle \lg ^{*}(n+2)} 回の演算[3] 。 Richard Cole とUzi Vishkin によるグラフの3彩色問題の分散アルゴリズム - O ( log ∗ n ) {\displaystyle O(\log ^{*}n)} 回の同期通信ステップ[4] 。 反復対数の成長は非常に遅く、対数関数よりもはるかに遅い。実装されている実際のアルゴリズムの実行時間を数えるのに十分な n {\displaystyle n} のすべての値(すなわち n ≤ 2 65536 ∼ 10 19660 {\displaystyle n\leq 2^{65536}\sim 10^{19660}} 、この最大値は観測可能な宇宙 内の原子数 10 80 {\displaystyle 10^{80}} を優に超える)に対して、底 2 {\displaystyle 2} の反復対数の値はたったの 5 {\displaystyle 5} 以下である。
より高い底の反復対数は、より小さい値を返す。計算の複雑さの分野で使われるものでいえば、逆アッカーマン関数 だけである。
他の応用例 反復対数は、symmetric level-index arithmetic(英語版) [訳語疑問点 ] で用いられる一般化された対数関数(英語版) と密接に関係している。加法についての持続係数(英語版) (ある数が数字根 に到達するまでに、数字をすべての桁の和で置き換える回数)は、 O ( log ∗ n ) {\displaystyle O(\log ^{*}n)} である。
計算複雑性理論において、Santhanam [5] によれば、計算資源 のDTIME (決定性チューリング機械 での計算時間)とNTIME (非決定性チューリング機械 での計算時間)とが区別できるのは n log ∗ n {\displaystyle n{\sqrt {\log ^{*}n}}} までである。
脚注
出典 ^ 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 ^ Devillers, Olivier (1992). “Randomization yields simple O ( n log ∗ n ) {\displaystyle O(n\log ^{\ast }n)} algorithms for difficult Ω ( n ) {\displaystyle \Omega (n)} problems”. International Journal of Computational Geometry & Applications 2 (1): 97–111. doi:10.1142/S021819599200007X. MR 1159844. ^ Alon, Noga; Azar, Yossi (1989). “Finding an approximate maximum”. SIAM Journal on Computing 18 (2): 258–267. doi:10.1137/0218017. MR 986665. ^ 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. MR 853994. ^ 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。 典拠管理データベース: 国立図書館