確率論における法則については「重複対数の法則（英語版）」をご覧ください。
図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}