Types of Functions > Iterated Logarithm Function

**Contents:**

## What is a Logarithm Function?

A **logarithm function** is a function of the form:

f(x) = log

_{b}x.

It is the inverse function of the exponential function. In notation, that’s: If y = log_{b}x, then b^{y} = x.

The logarithmic function log_{b}x is read “log base b of x”.

Sometimes a logarithm function is just written as *log x*. In those cases the writer thought which base to use was obvious, and we use our knowledge of the situation to determine what the expression means exactly. In the vast majority of cases, if you see “log x”, then assume it’s base 10.

## Logarithm Function Properties

A knowledge of the basic properties of logarithmic functions may help you in your evaluations.

- log
_{b}1 = 0 . Since b^{0}= 1, the exponent any base needs to make 1 is always zero. - log
_{b}b = 0 . Since b^{1}= b, the exponent any base needs to make itself is always just one. - log
_{b}b^{x}= x . Remember log bas b of x and b to the x power are inverse functions. When inverse functions are applied to each other, the inverse out (essentially cancel each other out). - If we know that log
_{b}x = log_{b}y, then we know that x = y. - If we know that log
_{b}x = log_{a}x, then we know that a = b.

## Special Bases

The logarithm with base 2 is called the **binary logarithm**, and it is foundational in much of computer science.

The logarithm with base *e* (≈ 2.718) is called the **natural logarithm** and is important in math and physics.

The logarithm with base 10 is the **common logarithm**, and is used in science, engineering and many other fields.

## Iterated Logarithm Function

The **iterated logarithm function**log * *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 * (2
^{65536}) = 5

This function is very slow-growing. Since the number of atoms in the universe if about 10^{80}, which is a lot less than 2^{65536}, it’s very rare to see any use the iterated logarithm function for numbers that high: lg * 10^{20} 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 log^{2}x is the inverse of 2^{x}). The first few towers-of-2:

- tower-of-2(1) = 2
- tower-of-2(2) = 2
^{2}= 4 - tower-of-2(3) = 16
- tower-of-2(4) = 65,536
- tower-of-2(5) ≈ 1000
^{6,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].

## Iterated Logarithm Function: 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