Exponentials and logarithms

Two operations that undo each other: one multiplies over and over, the other counts how many times you multiplied, or halved.

Exponentials and logarithms are inverse twins. An exponential like $2^{10}$ says "multiply by 2, ten times" and lands on $1024$. A logarithm runs the film backwards: ${\log }_{2}1024$ asks "how many times did I multiply, or, going down, how many times can I halve?" and answers $10$. Hold onto that second reading of a log as a count of halvings: it is the entire reason binary search and balanced trees are so astonishingly fast.

Multiply up, count back down

An exponential function $f(x)=b^x$ multiplies the base $b$ by itself $x$ times. When $b>1$ you get growth, $3^1,3^2,3^3=3,9,27$, each step multiplies so the curve rockets upward. When $0<b<1$ you get decay, $\frac{1}{2},\frac{1}{4},\frac{1}{8}$, halving toward zero. This is the same shape behind compound interest, radioactive half-lives, and a search space that halves every step.

One base shows up so often it gets its own letter: $e\approx 2.71828$, the natural base. It is the growth rate at which a curve's steepness always equals its current height, and it falls out of continuous compounding as ${\left(1+\frac{1}{n}\right)}^n\to e$ when $n\to \infty$. The logarithm is the inverse function: give it a result, it hands back the exponent. Because it is an inverse, every fact about exponents flips into a fact about logs.

A logarithm counts halvings

Here is the aha you can feel with your hands. Pick a pile of $N$ items. Cut it in half, then halve what remains, and keep going until a single item is left. The number of cuts you make is exactly ${\log }_{2}N$. Set $N$ with the slider, then step the halving and watch the tally close in on the computed logarithm.

The same idea in code: a log is a loop that halves.

# how many times can we halve n before hitting 1?
def halvings(n):
    count = 0
    while n > 1:
        n = n // 2      # cut the pile in half
        count += 1
    return count        # == floor(log2 of the original n)

halvings(1024)          # -> 10, because 2**10 == 1024

The log rules, and change of base

Because logs undo exponents, the exponent laws become the log laws. These three turn multiplication into addition, the trick that made slide rules and, later, fast numeric code possible.

A quiet but huge consequence: ${\log }_{2}x$, ${\log }_{10}x$, and $\ln x$ differ only by a constant factor. That is precisely why Big-O writes $O(\log n)$ with no base at all: the base only changes a constant, and Big-O throws constants away.

Inverses mirror across the diagonal

Because $b^x$ and ${\log }_{b}x$ are inverse functions, their graphs are reflections of each other across the line $y=x$. Whatever the exponential sends $x\mapsto b^x$, the logarithm sends straight back. Drag the base $b$ and watch the two curves swing as perfect mirror images.

Check yourself