Calculus How To

Iterated Logarithm Function

Share on

Types of Functions >


The iterated logarithm functionlog * n (“log star of n”) is defined as the smallest natural number k for which
log(i) ≤ 1.
The function is not defined for n < 1.

Formally, it is defined as [1]:

  • log * n = 0 if n ≤ 1
  • log * n = 1 + log * (log n) if n > 1.

This slow growing function measures how many times you have to take the logarithm of n before it drops to one [2] or how many times you can take the log n base of a number [3].

A few examples:

  • log * 1 = 0
  • log * 2 = 1
  • log * 4 = 2
  • log * 16 = 3
  • log * 65,536 = 4.
  • log * (265536) = 5

This function is very slow-growing. Since the number of atoms in the universe if about 1080, which is a lot less than 265536, it’s very rare to see any use the iterated logarithm function for numbers that high: lg * 1020 exceeds the number of bytes in all of the computers on the planet [2].

Uses include algorithm analysis and building search trees (the Union-Find algorithm) in computer science, probability theory [4], mathematical systems and control theory [5], as well as various mathematical areas like the study of sets in bounded systems.

Iterated Logarithm Function & Tower-of-2

The iterated logarithm function is the inverse of the tower-of-2 function (similar to how log2x is the inverse of 2x). The first few towers-of-2:

  • tower-of-2(1) = 2
  • tower-of-2(2) = 22 = 4
  • tower-of-2(3) = 16
  • tower-of-2(4) = 65,536
  • tower-of-2(5) ≈ 10006,553

As this is the inverse of the iterated logarithm function, it grows very slowly. If you’re trying to calculate log * n by hand, it’s often much easier to calculate tower-of-2 first, then compare the number in question to see which “bucket” it falls into [6].

References

[1] 600.363 Introduction to Algorithms / 600.463 Algorithms I
[2] Problem Set 1: RMQ.
[3] Disjoint Set Data Structure.
[4] Eichelsbacher, P. & Lowe, M. Workshop on Probability Theory and Its Applications. Retrieved July 31, 2021 from: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.30.7719&rep=rep1&type=pdf
[5] Blondel, V. & Megretski, A. [Eds.]. Unsolved Problems in Mathematical Systems and Control Theory. Retrieved July 31, 2021 from: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.134.1462&rep=rep1&type=pdf
[6] Elkins, D. (2017). Computing the Iterated Logarithm (log-star) by hand. Retrieved July 31, 2021 from: https://math.stackexchange.com/questions/2553258/computing-the-iterated-logarithm-log-star-by-hand


CITE THIS AS:
Stephanie Glen. "Iterated Logarithm Function" From CalculusHowTo.com: Calculus for the rest of us! https://www.calculushowto.com/iterated-logarithm-function/
------------------------------------------------------------------------------

Need help with a homework or test question? With Chegg Study, you can get step-by-step solutions to your questions from an expert in the field. Your first 30 minutes with a Chegg tutor is free!


Leave a Reply

Your email address will not be published. Required fields are marked *