反復対数

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

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

概要

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

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

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

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

正の実数においては、連続性の超対数に等しい。

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

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

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

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

アルゴリズム解析

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

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

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

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

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

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

他の応用例

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

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

脚注