Take a sheet of paper 0.1 mm thick and fold it in half. It is now 0.2 mm thick. Fold it again: 0.4 mm. How many folds would it take for the stack to reach the Moon, about 384,400 km away?

Most people guess thousands, or millions. The answer is 42.

Here is a second puzzle that is really the same one. A rumour starts with one person. Every hour, everyone who knows it tells one new person. After one day (24 hours), how many people know?

After a day and a half, more people than live on Earth would "know", which is obviously impossible. Something has to give. We come back to that in Section 12.7.

What these puzzles share is a quantity that gets multiplied by the same factor at every step. That is the defining feature of exponential behaviour, and human intuition is very bad at it.

Compare two savings plans, each starting at $100:

In the early years the two plans are almost the same. Over time the multiplying plan leaves the adding plan far behind. The rule of thumb:

You can recognise exponential data in a table by dividing each value by the one before. If the ratios are all (roughly) the same, the data is exponential.

If a quantity is multiplied by \(b\) each step and starts at \(a\), then

So "multiply by \(b\) every step" turns into "raise \(b\) to the number of steps". The exponent counts the multiplications.

Now look again at the folding puzzle. Thickness after \(n\) folds is \(0.1 \times 2^{n}\) mm. For \(n = 42\):

which is more than the 384,400 km to the Moon. (41 folds gives about 219,900 km, which is not enough.) Doubling 42 times multiplies by more than four trillion.

From Chapter 3 you know that \(b^x\) makes sense for any real \(x\), not only whole numbers: \(b^{1/2} = \sqrt{b}\), \(b^{-1} = 1/b\), and irrational exponents are filled in by continuity. So \(f(x) = a b^x\) is defined on the whole real line and gives a smooth curve.

Every graph of \(y = b^x\) with \(b > 0\), \(b \ne 1\) shares these features:

Carbon-14 has a half-life of about 5,730 years. A sample starts with 200 micrograms of carbon-14. How much is left after 20,000 years?

Sanity check: after 3 half-lives you would have \(200/8 = 25\), and after 4 you would have \(200/16 = 12.5\). 17.8 falls between them, as it should.

The reverse question, "how old is a sample with 30% of its carbon-14 left?", needs the exponent as the unknown. We can’t answer it with what we have yet. That is exactly what the logarithm is for, and we solve it in Section 12.5.

A bank offers 100% interest a year. (Not a real bank.) Put in $1 and after a year you have $2. A rival bank says: "We pay the same rate, but we compound twice a year: 50% after six months, then 50% on the new balance." Another compounds monthly. Another daily. Another every second.

Does compounding more often make you arbitrarily rich, or is there a ceiling?

Compounding more often helps, because interest starts earning interest sooner. But each split also makes the individual pieces smaller. These two effects pull against each other, and it isn’t obvious which wins.

Split the year into \(n\) periods. Each period pays \(1/n\) of the annual rate, so the balance is multiplied by \(1 + 1/n\) \(n\) times:

The balance grows, but more and more slowly, and it levels off just above 2.718. That ceiling is the number

The formal definition uses a limit, which is the subject of Chapter 16:

Read "lim as \(n \to \infty\)" as "the value this expression settles towards as \(n\) grows without bound".

Suppose the annual rate is \(r\) instead of 100%, you invest a principal \(P\) for \(t\) years, and you compound \(n\) times a year. The balance is

Let \(m = n/r\). Then \(r/n = 1/m\) and \(nt = m \cdot rt\), so

That gives the continuous compounding formula

$1,000 at 5% a year for 10 years:

Going from annual to monthly compounding earns $18. Going from monthly to continuous earns only $1.71 more. That matches the levelling off in the table.

The values close in on \(e\) up to \(n = 10^8\). Then they go wrong: \(10^{12}\) is worse, and at \(10^{16}\) the answer is exactly 1. The reason is floating point. 1 + 1/n is rounded to the nearest representable double, and when \(1/n\) is below about \(1.1 \times 10^{-16}\), 1 + 1/n rounds to exactly 1.0. We return to this kind of failure in Chapter 32. The general lesson is that a numerical approach to a limit has a sweet spot. Push too far and rounding error takes over.

Continuous compounding is how many financial models price bonds and options, but \(e\) turns up far beyond banking, wherever many small independent chances or a growth rate proportional to size are involved:

From Section 12.1 you can answer "\(2^{10}\) is what?" (1,024). Now turn the question round:

That is the question a logarithm answers. The answer is 10, and we write

Questions like this come up constantly. How many years until my investment doubles? How old is this fossil? How many times can I halve a list of a million items before one item is left? How many bits does it take to count to a billion? Each asks for an unknown exponent.

The word to hold onto: a logarithm is an exponent. Every fact about logarithms is a fact about exponents written the other way round.

Each of these is answered by asking "what power?":

One more, a bit harder: \(\log_8 32\). Both 8 and 32 are powers of 2: \(8 = 2^3\) and \(32 = 2^5\). We want \(y\) with

So \(\log_8 32 = 5/3\). Check: \(8^{5/3} = (\sqrt[3]{8})^5 = 2^5 = 32\). Correct.

Because \(y = b^x\) is one-to-one, it has an inverse function (Chapter 11), and that inverse is \(y = \log_b x\). Inverse functions undo each other:

The graph of an inverse function is the original graph reflected in the line \(y = x\). Every point \((p, q)\) on \(y = 2^x\) becomes the point \((q, p)\) on \(y = \log_2 x\).

Swapping the roles of \(x\) and \(y\) in the exponential’s properties gives the logarithm’s properties:

The last row matters a lot in computing. \(\log_2 x\) does keep increasing without limit, but extremely slowly. \(\log_2\) of a thousand is about 10, of a million about 20, of a billion about 30. Multiplying the input by 1,000 adds only about 10 to the output. That is why an algorithm that takes \(\log n\) steps scales so well.

Before calculators, multiplying two seven-digit numbers by hand was slow and easy to get wrong, while adding them was fast. Navigators, astronomers and engineers wanted a way to turn multiplication into addition. Logarithms did that, and the reason is a single exponent law.

The log laws aren’t new rules to memorise. Each is an exponent law from Chapter 3 read backwards. In everything below, \(b > 0\), \(b \ne 1\), and \(M, N > 0\).

Product law. Let \(m = \log_b M\) and \(n = \log_b N\). By definition, \(b^m = M\) and \(b^n = N\). Then

Quotient law. Same setup:

Power law. For any real \(k\):

Change of base. Suppose you need \(\log_2 50\) but your calculator only has \(\log_{10}\) and \(\ln\). Let \(y = \log_b x\), so \(b^y = x\). Take log base \(c\) (any convenient base) of both sides:

So

In words: every logarithm is a constant multiple of every other. \(\log_2 x = \log_{10} x / \log_{10} 2 \approx 3.3219 \log_{10} x\). Changing the base just rescales the vertical axis of the graph.

Three bases account for nearly every logarithm you will meet.

Some values worth recognising:

\(\log_{10} 2 \approx 0.301\) says \(2^{10} = 1024 \approx 10^3\): ten doublings add about three decimal digits. That is the familiar kilo/kibi relationship. Big-O notation doesn’t care about the base of a log, because by change of base \(\log_2 n\) and \(\log_{10} n\) differ only by a constant factor.

Expand \(\log_2\!\left(\dfrac{8x^3}{\sqrt{y}}\right)\):

Condense \(2\ln a + \ln b - 3\ln c\) to a single log:

Change of base: compute \(\log_3 20\) with a calculator that only has \(\ln\):

Check: \(3^{2.726833}\) should be 20. \(3^{2} = 9\) and \(3^{3} = 27\), so an exponent between 2 and 3 that lands closer to 3 is about right.

Now we can answer the questions we set aside earlier. When will $1,000 at 6% become $2,000? How old is a bone with 30% of its carbon-14 left? In each the unknown is in the exponent, and the way to get it down is to take a logarithm of both sides.

Taking logs is allowed because \(\log\) is a function: equal inputs give equal outputs, so if \(A = B\) (both positive) then \(\log A = \log B\). Then the power law moves the unknown exponent down to the main line, where ordinary algebra (Chapter 5) can reach it:

The arrow \(\Longrightarrow\) means "implies".

Solve \(2^{x} = 50\).

Check: \(2^5 = 32\) and \(2^6 = 64\), so the answer has to be between 5 and 6. \(x \approx 5.64\) passes. (Equivalently, \(x = \log_2 50\).)

Solve \(3 \cdot 5^{2x - 1} = 400\).

A bone has 30% of the carbon-14 that living tissue has. How old is it? (Half-life 5,730 years.)

The two negative logs cancel to give a positive age. Sanity check: 30% is between 50% (one half-life) and 25% (two half-lives), and 9,953 years is between 5,730 and 11,460.

How long does money take to double at 6% compounded annually?

Bankers use the rule of 72: doubling time \(\approx 72 / (\text{rate in percent})\), here \(72/6 = 12\). Why does it work? For small \(r\), \(\ln(1 + r) \approx r\) (you’ll see why in Chapter 17), so

69.3 would be the more accurate constant for small rates. 72 is used because it divides evenly by 2, 3, 4, 6, 8, 9 and 12, and because it partly corrects for \(\ln(1+r)\) being a little less than \(r\) at typical rates of 6–10%.

Solve \(\log_2 x + \log_2(x - 2) = 3\).

(Factoring quadratics is covered in Chapter 8.)

Check: \(x = 4\) gives \(\log_2 4 + \log_2 2 = 2 + 1 = 3\). Correct. \(x = -2\) gives \(\log_2(-2)\), which is undefined, so we reject it. It is an extraneous solution: condensing the logs widened the domain, because \(x(x - 2) > 0\) also allows \(x < 0\).

The decision rule: same base → match exponents; one exponential term → isolate and log; exponentials of related bases → substitute; exponential mixed with polynomial → numerical.

(The first line solves for the whole exponent \(2x - 1 = 3.0401\). The final digit in 400.0000000000001 is floating-point rounding.)

Every "how long until …?" question about an exponential process is solved this way:

The quietest sound a human can hear and the sound of a jet engine at 30 m differ in intensity by a factor of about \(10^{14}\). Earthquakes span a similar range of energies. Hydrogen-ion concentrations in everyday liquids run from about 1 down to \(10^{-14}\) moles per litre. Put any of these on an ordinary linear axis and everything except the biggest values gets squashed into an invisible sliver near zero.

A logarithmic scale places each value at a position proportional to its logarithm. Equal distances then represent equal ratios, not equal differences. On a base-10 log scale, 1 → 10 → 100 → 1,000 are evenly spaced, each one "decade" apart. Our senses work roughly like this: a sound ten times as intense doesn’t seem ten times as loud.

Decibels (sound, signals). The sound intensity level is Try it: Decibels and power ratios.

where \(I_0 = 10^{-12}\ \text{W/m}^2\) is the threshold of hearing. Multiplying intensity by 10 adds 10 dB, and doubling it adds \(10\log_{10}2 \approx 3.01\) dB. Engineers use dB for any power ratio: amplifier gain, Wi-Fi signal strength (dBm), the signal-to-noise ratio of an ADC.

Worked example. A sound is 85 dB. How many times more intense than a 60 dB sound is it? Try it: 25 dB as a ratio.

Earthquake magnitude. The Richter scale, and the moment-magnitude scale that replaced it, is logarithmic. Each whole number up means about 10 times the ground-motion amplitude and about \(10^{1.5} \approx 31.6\) times the energy released. A magnitude 7 quake releases about \(31.6^2 \approx 1000\) times the energy of a magnitude 5.

pH (chemistry).

where \(\lbrack\mathrm{H}^{+}\rbrack\) is the hydrogen-ion concentration in moles per litre. The minus sign makes everyday values positive. Pure water has a hydrogen-ion concentration of \(10^{-7}\), so pH 7. Lemon juice at pH 2 has \(10^{5} = 100{,}000\) times the hydrogen-ion concentration of water.

Graphs can use a log scale on one axis or both.

You have data, say case counts of a spreading infection, users of a new app, or the runtime of a brute-force solver as the input grows. It curves upward. Is it exponential? If so, what are \(a\) and \(b\), what is the doubling time, and what does the model predict?

You know how to fit a straight line (Chapter 5). Logarithms turn an exponential into a straight line, so take the log of the data, fit a line, and convert back.

If \(y = a e^{kt}\), then

This is a line in the variables \(t\) and \(\ln y\), with slope \(k\) and intercept \(\ln a\). The base-\(e\) form \(a e^{kt}\) is the one scientists prefer. It is the same family as \(a b^t\), with \(b = e^{k}\) (so \(k = \ln b\)). \(k\) is called the continuous growth rate.

A culture has 500 cells at hour 2 and 4,000 cells at hour 5. Find \(y = a e^{kt}\). Try it: Fit y = a·e^(kt).

So \(y = 125\, e^{0.6931\,t} = 125 \cdot 2^{t}\). The culture doubles every hour, and there were 125 cells at \(t = 0\).

With real, noisy data, use all the points. Fit a least-squares line to \((t, \ln y)\). (Least squares is covered properly in Chapter 31. For now, think of it as "the line that best goes through the cloud of points".) Try it: Fit the case counts.

Try it: Run this in your browser.

How can you tell whether to use a linear, exponential or power-law model? Transform the data and see which version comes out straight:

\(x^{10}\) is a huge polynomial. At \(x = 10\) it is ten billion, while \(2^{10}\) is only 1,024. Is \(x^{10}\) bigger for good? An algorithm that takes \(n^{10}\) steps would be useless in practice, but theory still calls it "efficient" (polynomial), while \(2^n\) is "intractable". Why does exponential rank as worse?

Compare how each function changes when \(x\) goes up by 1:

The exponential multiplies itself by 2 at every step for ever. The polynomial’s step-to-step growth factor shrinks towards 1. Eventually it is below 2 and stays there. Once the polynomial is growing by less than 2× per step and the exponential by exactly 2×, the exponential closes any gap and pulls ahead.

Take logs of both to compare them:

The left side is a straight line. The right side is a log curve, which grows more slowly than any line. A line with any positive slope eventually overtakes \(10\ln x\) and never falls back. For \(2^x\) vs \(x^{10}\), solving \(x \ln 2 = 10 \ln x\) numerically gives crossover points at \(x \approx 1.078\) and \(x \approx 58.77\). Beyond about 58.8, \(2^x\) wins for ever.

The general statements, which Chapter 16 makes rigorous:

That gives the growth hierarchy:

where \(\ll\) means "is eventually negligible compared with".

Searching a sorted array of \(n\) items, each comparison throws away half of what remains. After \(k\) comparisons, about \(n / 2^{k}\) items are left. We stop when one item is left: Try it: Binary search on a billion.

So binary search needs about \(\lceil \log_2 n \rceil\) comparisons. \(\lceil \cdot \rceil\) is the ceiling, which rounds up to the next integer. For a billion items that is

comparisons, where linear search needs up to a billion.

Try it: Estimate log₂ in your head.

A complete binary tree of height \(h\) (\(h\) levels of edges below the root) holds up to Try it: Tree height and B-trees.

nodes. (That sum is a geometric series, Chapter 14.) So a balanced tree holding \(n\) keys needs height only about \(\log_2 n\). That is why a balanced binary search tree, a heap or a red–black tree gives \(O(\log n)\) lookups and inserts. A B-tree with branching factor \(B\) has height about \(\log_B n\). With \(B = 500\), a billion keys fit in a tree of height \(\log_{500} 10^9 = 9/\log_{10}500 \approx 3.3\), so in practice four levels, four disk reads. Try it: Merge sort’s log₂ n levels.

Merge sort splits the list in half repeatedly, giving \(\log_2 n\) levels of splitting with \(n\) work per level, for a total of \(O(n \log n)\) (Chapter 24 counts this more carefully).

With \(k\) bits you can write \(2^{k}\) different values, 0 to \(2^{k} - 1\). To store the integers 0 to \(n\) you need the smallest \(k\) with \(2^{k} > n\):

where \(\lfloor \cdot \rfloor\) is the floor, which rounds down. For example, 1,000,000 needs \(\lfloor 19.93 \rfloor + 1 = 20\) bits. Likewise the number of decimal digits in \(n\) is \(\lfloor \log_{10} n \rfloor + 1\).

Here is how many basic steps algorithms of different complexity need, and how long they’d take at \(10^{9}\) steps per second:

\(2^{100}\) steps at a billion per second would take about \(4 \times 10^{13}\) years, thousands of times the age of the universe. That is why "exponential time" means "infeasible" for anything but small inputs.

How many yes/no questions does it take to identify one of 8 equally likely possibilities? Each well-chosen question halves the candidates: 8 → 4 → 2 → 1. That is 3 questions, and \(3 = \log_2 8\). In general, picking one of \(N\) equally likely options conveys

A fair coin flip is 1 bit. A roll of a fair die is \(\log_2 6 \approx 2.585\) bits. A random 12-character password from 94 printable characters has \(12 \log_2 94 \approx 78.7\) bits of entropy. The game Twenty Questions can distinguish \(2^{20} \approx 1{,}048{,}576\) objects.

Claude Shannon generalised this to unequal probabilities. An outcome of probability \(p\) carries \(-\log_2 p\) bits of surprise, and the average surprise of a source is its entropy. That is the foundation of compression (Huffman coding, arithmetic coding) and of the cross-entropy loss used to train classifiers (Chapter 29).

Multiply a thousand probabilities of 0.01 each, as a language model or a naive Bayes classifier might when scoring a long document:

The smallest positive double is about \(5 \times 10^{-324}\), so the product underflows to 0.0, and every candidate document scores the same zero. The fix is to work in logs: the product law turns the product into a sum,

which is a perfectly ordinary floating-point number. (\(\prod\) is the product symbol, the multiplicative cousin of \(\sum\). Read \(\prod_i p_i\) as "multiply all the \(p_i\) together". \(\sum_i \ln p_i\) means "add up all the \(\ln p_i\)".) Since \(\ln\) is increasing, comparing log-probabilities gives the same ranking as comparing probabilities. Log-likelihood, log-loss and log-odds all exist for this reason.

A classifier produces scores \(z_1, \ldots, z_K\) ("logits") and turns them into probabilities with the softmax function:

If any \(z_i\) is around 1,000, then \(e^{1000}\) overflows to infinity and the result is nan. The standard fix uses an exponent law. For any constant \(m\),

Choose \(m = \max_j z_j\). Every exponent \(z_j - m\) is then at most 0, so nothing overflows and at least one term equals 1. The same trick computes \(\log\sum_j e^{z_j} = m + \log\sum_j e^{z_j - m}\) safely. This is the log-sum-exp function, which appears throughout machine learning.