迭代对数

迭代对数（英语：Iterated logarithm）也称为重复对数，是一个增加非常慢的数学函数，可以视为近似常数。一般会用log*  n来表示。一实数的迭代对数是指须对实数连续进行几次对数运算后，其结果才会小于等于1。最简单的定义以是以下递回函数的结果：

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

说明为何log* 4 = 2

在计算机科学中，lg* 常用来表示实数可以进行几次以2为底的对数运算，lg*及log*都可以针对所有实数取值，值的结果一定是一个整数。

右图中以log* 4为例，说明迭代对数的计算方式，图中的曲线为y=log x，一开始由（4,0）开始画一垂直线，和y=log x相交于（4,1.386），再由交点画一水平线到y轴，交点在（0,1.386），再画一条往右下，和x轴夹角45度的斜线，和x轴交点在（1.386,0），再依以上方式画垂直线、水平线及斜线，和x轴交点在（0.326,0），再画垂直线时，和y=log x交点已不在第一象限，因此结束，中间进行了二次log x的计算，因此log* 4=2。

迭代对数的增加速度非常慢，比对数要慢很多。对于实际算法可能的执行次数而言（n ≤ 2⁶⁵⁵³⁶，此数字比宇宙中已知的原子数目还要多），lg*的结果都小于等于5。