Logarithms

The logarithm of base \(b\) for value \(y\) is the power to which \(b\) is raised to get \(y\). Normally, this is written as \(\log_b y = x\). Thus, if \(\log_b y = x\) then \(b^x = y\), and \(b^{log_b y} = y\).

Logarithms have the following properties, for any positive values of \(m\), \(n\), and \(r\), and any positive integers \(a\) and \(b\).

1. \(\log (nm) = \log n + \log m\).

2. \(\log (n/m) = \log n - \log m\).

3. \(\log (n^r) = r \log n\).

4. \(\log_a n = \log_b n / \log_b a\).

The first two properties state that the logarithm of two numbers multiplied (or divided) can be found by adding (or subtracting) the logarithms of the two numbers. [1] Property (3) is simply an extension of property (1). Property (4) tells us that, for variable \(n\) and any two integer constants \(a\) and \(b\), \(\log_a n\) and \(\log_b n\) differ by the constant factor \(\log_b a\), regardless of the value of \(n\). Most runtime analyses we use are of a type that ignores constant factors in costs. Property (4) says that such analyses need not be concerned with the base of the logarithm, because this can change the total cost only by a constant factor.

C and C++ have always included functions to compute \(\log_e\) and \(\log_{10}\). New in C++11 is a function specifically for base 2. As we will see, base 2 logarithms are used frequently and it is convenient to not have to perform change in base calculations when \(\log_2\) is needed.

double x = std::log(1000);  // natural log of 1000

double x = std::log10(1000);  // base 10 log of 1000

double x = std::log2(1000);  // base 2 log of 1000

In this course, nearly all logarithms used have a base of two. This is because data structures and algorithms most often divide things in half, or store codes with binary bits. Whenever you see the notation \(\log n\) in this text, either \(\log_2 n\) is meant or else the term is being used asymptotically and so the actual base does not matter. For logarithms using any base other than two, we will show the base explicitly.

#include <iostream> #include <cmath> int main() { std::cout << "log(1) = " << std::log(1) << '\n' << "base-5 logarithm of 125 = " << std::log(125)/std::log(5) << '\n'; std::cout << "log2(65536) = " << std::log2(65536) << '\n' << "log2(0.125) = " << std::log2(0.125) << '\n' << "log2(0x020f) = " << std::log2(0x020f) << " (highest set bit is in position 9)\n" << "base-5 logarithm of 125 = " << std::log2(125)/std::log2(5) << '\n'; // special values std::cout << "log2(1) = " << std::log2(1) << '\n' << "log2(+Inf) = " << std::log2(INFINITY) << '\n'; }

Example

Many programs require an encoding for a collection of objects. What is the minimum number of bits needed to represent \(n\) distinct code values? The answer is \(\lceil \log_2 n \rceil\) bits. For example, if you have 1000 codes to store, you will require at least \(\lceil \log_2 1000 \rceil = 10\) bits to have 1000 different codes (10 bits provide 1024 distinct code values).

Example

Consider the binary search algorithm for finding a given value within an array sorted by value from lowest to highest.

Binary search first looks at the middle element and determines if the value being searched for is in the upper half or the lower half of the array. The algorithm then continues splitting the appropriate subarray in half until the desired value is found. How many times can an array of size (n) be split in half until only one element remains in the final subarray? The answer is \(\lceil \log_2 n \rceil\) times.

A useful identity to know is:

\[2^{\log n} = n\]

To give some intuition for why this is true: What does it mean to take the log (base 2) of \(n\)? If \(\log_2 n = x\), then \(x\) is the power to which you need to raise 2 to get back to \(n\). So of course, \(2^{\log n} = n\) when the base of the log is 2.

When discussing logarithms, exponents often lead to confusion. Property (3) tells us that \(\log n^2 = 2 \log n\). How do we indicate the square of the logarithm (as opposed to the logarithm of \(n^2\))? This could be written as \((\log n)^2\), but it is traditional to use \(\log^2 n\). On the other hand, we might want to take the logarithm of the logarithm of \(n\). This is written \(\log \log n\).

A special notation is used in the rare case when we need to know how many times we must take the log of a number before we reach a value \(\leq 1\). This quantity is written \(\log^* n\). For example, \(\log^* 1024 = 4\) because \(\log 1024 = 10\), \(\log 10 \approx 3.33\), \(\log 3.33 \approx 1.74\), and \(\log 1.74 < 1\), which is a total of 4 log operations.

Self Check

sc-1-2: Simplify the following expression into the form \(log(c)\): \(\log(15) - \log(3)\)

sc-1-3: Simplify the following expression into the form \(log(c)\): \(\log(3) + \log(4)\)

sc-1-4: Solve the following expression: \(\log_{729}(9)\)

More to Explore

• From cppreference.com

  • log, log, and log2

Footnotes

[1]

These properties are the idea behind the slide rule. Adding two numbers can be viewed as joining two lengths together and measuring their combined length. Multiplication is not so easily done. However, if the numbers are first converted to the lengths of their logarithms, then those lengths can be added and the inverse logarithm of the resulting length gives the answer for the multiplication (this is simply logarithm property (1)). A slide rule measures the length of the logarithm for the numbers, lets you slide bars representing these lengths to add up the total length, and finally converts this total length to the correct numeric answer by taking the inverse of the logarithm for the result.

Acknowledgements

This section is adapted from Open Data Structures (OpenDSA) by Ville Karavirta and Cliff Shaffer which is distributed under the MIT License.

You have attempted of activities on this page