Logarithms
Most of What We Studied
in School Stayed There
Logarithms didn’t. They followed us into every codebase, quietly running inside the algorithms we rely on the most.
There is a long list of things we studied in school mathematics and never encountered again. Trigonometric identities are near the top. Sin²θ + cos²θ = 1, the double angle formulae, pages of them, dutifully memorised and carefully reproduced in an exam, then quietly never thought about again. They had the decency to stay in school where we left them.
Logarithms sat in the same chapter. Same compact notation, same air of abstraction, same unspoken question: when will I ever use this? So they got filed under the same heading: learned it, passed it, moved on.
That turns out to be a significant mistake. Unlike most of what we memorised, logarithms never went away. They just went underground. There is one inside every binary search you have ever written. One governing the height of every balanced tree in your standard library. One quietly explaining why sorting a million items takes roughly twenty thousand times longer than sorting a thousand, not a million times longer. They did not disappear from our work after school. They became the invisible scaffolding behind the algorithms you reach for every day.
log₂(1,000,000,000) ≈ 30. A logarithm, doing its job silently inside your code.
This post is my attempt to make that scaffolding visible. Not through more definitions, but by drawing out what logarithms are actually doing, step by step, starting from something you can hold in your hands.
What Is a Logarithm, Really?
Take a piece of paper. Fold it in half. Fold it again. Keep going. After 10 folds, how thick is it? A piece of A4 paper is about 0.1mm thick. After 10 folds: 0.1 × 2¹⁰ = 102mm, which is over 10 centimetres. After 42 folds, it would reach the moon.
Exponentiation (repeated multiplication) grows insanely fast. Logarithm is the question you ask when you want to undo that:
"How many times must I double before I reach this number?" Answer: 30 times.
10? = 1,000,000,000 means log₁₀(1,000,000,000) = 9
"How many times must I multiply by 10 before I reach this number?" Answer: 9 times (it has 9 zeros).
Every logarithm is counting how many times you multiply before reaching a target. The base tells you what you're multiplying by. Change the base and you change the unit of folding, but the shape of the curve is always the same: steep at first, then flattening toward a crawl.
That flatness is not a quirk. It is the entire point. And it is why logarithms keep appearing in algorithm analysis wherever something is being halved, split, or divided at each step.
The Three Famous Bases
Most of what you'll encounter in programming and science comes from three bases. Each one arises naturally from a different kind of division happening in the real world.
log₁₀ in the Real World: When the Numbers Hide the Truth
log₁₀ is the base most people encountered in school, and also the one that causes the most surprise in everyday life. Because log₁₀ compresses enormous differences into small numbers, scales that use it can make things that are wildly different appear deceptively close together.
The Richter scale is the clearest example of this.
The Richter scale is logarithmic base 10. Each whole number step up represents ten times more ground motion, and roughly 31.6 times more energy released.
A magnitude 5 earthquake is felt by people, rattles windows, occasionally causes minor damage. They happen hundreds of times a year worldwide. They rarely make international news.
A magnitude 8 earthquake is catastrophic. It can level cities, trigger tsunamis, and reshape coastlines.
The difference in the number: 8 minus 5 = 3. The difference in energy: 10³ = 1,000 times more powerful. That is what three steps on a logarithmic scale actually means. The news reports them three points apart. The planet feels them a thousand times apart.
This compression is not a flaw in the scale. It is exactly why the scale was invented. Without logarithms, you would need to write "magnitude 1,000,000,000 vs magnitude 1" to capture the full range of earthquakes that occur on Earth. The log scale fits the entire range of seismic activity, from the vibration of a passing truck to the rupture of a tectonic plate, into a single human-readable number between 1 and 10.
The same principle explains several other scales you have seen without perhaps realising why they work the way they do.
In each case, the logarithm is doing the same job: translating a range of values so enormous it would be unwieldy to write out into a compact, human-friendly number. The cost of that convenience is that our intuition about the differences between numbers on the scale completely breaks down. Three points does not mean three times. It means one thousand times. That is the thing worth remembering every time you see a logarithmic scale in a news article.
But Why e, of All Numbers?
This is the question that deserves a proper answer. log₁₀ makes sense because of our ten fingers. log₂ makes sense because computers think in bits. But e ≈ 2.71828...? That specific irrational number, going on forever without pattern. Why does it keep appearing in serious mathematics?
The answer starts with a simple question about money.
The Bank Account That Compounds Every Instant
Suppose you deposit £1 in a bank that offers 100% interest per year. If they pay it once at the end of the year, you have £2. Simple enough.
Now suppose they compound it twice a year: 50% every six months. After six months you have £1.50, and that £1.50 then earns another 50%, giving £2.25 at year end. A little better.
What if they compound monthly? Weekly? Daily? Every second? You might expect that compounding more and more often would let you earn unlimited money. It does not. No matter how frequently you compound 100% annual interest, your £1 approaches a ceiling. That ceiling is e.
Try it: n=1 gives 2.0. n=10 gives 2.594. n=1000 gives 2.7169. n=1,000,000 gives 2.71828. The sequence crawls toward 2.71828... and never goes further. That limit is e. It emerges from compounding, without anyone choosing it.
The One Function That Is Its Own Derivative
Here is the deeper reason e keeps appearing. If you have a quantity that grows at a rate proportional to its own current size, which is a very common situation in nature, the mathematics forces you toward e.
Mathematically: the function eˣ is the only function where the rate of change equals the function itself. Written as a derivative: d/dx(eˣ) = eˣ. Population growth, compound interest, radioactive decay, the charging of a capacitor. All of these are described by equations of the form "the rate of change is proportional to the current value," and all of them produce e in their solutions.
Nobody put e there. The mathematics of continuous change discovered it.
What ln Actually Counts
So if eˣ describes continuous growth, then ln(x), the natural logarithm, answers the reverse question: how long does continuous growth take to reach x? If something doubles every ln(2) ≈ 0.693 units of time under continuous compounding, then ln(x) tells you how many of those doubling periods fit into reaching x.
A Petri Dish That Has Nothing to Do With Banks
Consider a single bacterium placed in a warm petri dish with plenty of nutrients. Under good conditions, E. coli divides roughly every 20 minutes. One cell becomes two. Two become four. Four become eight. No human invented this rate. No interest rate was set by a committee. This is just what bacteria do when conditions allow: each individual keeps dividing at the same constant rate, so the total population grows at a rate proportional to its current size.
That sentence is worth pausing on. "Grows at a rate proportional to its current size." That is the precise condition under which e appears naturally. Not approximately. Exactly.
Starting population: 1 cell. Doubling time: 20 minutes. After ten hours (30 doubling periods): 2³⁰ = 1,073,741,824 cells. Over one billion, from a single cell, in the time it takes to sleep.
Now the natural logarithm enters. Suppose you want to know not the final count, but the answer to the reverse question: given that the dish now contains N bacteria, how long has it been growing?
The answer is t = ln(N) / r, where r is the growth rate constant. ln is not a choice made by a biologist. It falls out of the mathematics of continuous proportional growth the same way e falls out of the compounding bank account. The universe uses the same equation in both places because both situations are the same situation: a quantity growing in proportion to itself.
This is also why epidemics feel slow, then suddenly catastrophic. In the early stages, when N is small, ln(N) is very small too, so the numbers look manageable. But the underlying exponential is already running. By the time the case count reaches a level that looks alarming, the ln of that count has only moved a little, while the actual count has multiplied many times over. The logarithm measures the calm. The exponent is what is actually happening.
For populations, for epidemics, for the decay of radioactive atoms, for the discharge of a capacitor, for any system where growth or decay feeds on itself, ln is the natural measuring stick. Not because someone decided it should be. Because the mathematics of continuous proportional change has no other option.
Feel the Flatness
Now that all three bases have a story behind them, drag the slider and watch each one in motion. Notice that ln(N) always sits between log₁₀(N) and log₂(N), because e sits between 10 and 2 on the number line of bases. All three barely move. That is the point.
Notice something? As you drag N from 1 million to 1 billion, a thousandfold increase, log₂ creeps from 20 to 30. Ten extra steps. The curve has essentially stopped caring about the growth in N. That's why algorithms that achieve O(log N) complexity feel almost magical at scale: doubling your dataset costs you just one extra operation.
Logarithms in Your Code
Each of the three bases has its natural home in programming. log₂ appears wherever a problem is halved at each step. log₁₀ appears in digit-counting, formatting, and human-readable scaling. ln appears in anything modelling continuous growth, probability, or information. The base tells you what kind of division is happening.
Here's what binary search looks like in C++, with the log explicitly visible in the loop structure:
// Binary search: each iteration cuts the search space in half
// Total iterations ≤ log₂(N) — the logarithm emerges from the halving
int binary_search(const std::vector<int>& arr, int target) {
int lo = 0, hi = (int)arr.size() - 1;
int steps = 0;
while (lo <= hi) {
++steps; // count: never exceeds log₂(N)
int mid = lo + (hi - lo) / 2; // ← this halving IS the logarithm
if (arr[mid] == target) return mid;
else if (arr[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
// For N = 1,000,000,000: steps ≤ 30. Always.
How Algorithms Scale
Select a value of N and see how many operations each complexity class requires. The log column will make you want to use binary search everywhere.
| Algorithm class | Complexity | Operations | At 1 GHz: time |
|---|
Three bases. Three different stories about what is being divided or measured. log₁₀ counts digits, belonging to the human world of powers of ten. log₂ counts halvings, belonging to the binary world of computers. And ln counts something subtler: the accumulation of continuous change, the passage of time in a system that grows because it has already grown.
What surprised me, working through this properly for the first time, is that all three are pointing at the same underlying idea. A logarithm is always an answer to the question: how many times does this process have to repeat before we get there? The process might be multiplying by 10, or by 2, or by e. Change the process and you change the base. The question stays the same.
That is why O(log N) in algorithm analysis does not bother to specify a base. The base only changes the constant factor (how many repetitions per unit), not the fundamental shape of the growth. And that shape, that slow beautiful curve that barely moves as N grows to billions, is the real insight. Once you have seen it, you start recognising logarithms everywhere: in the height of a tree, in the number of bits in a number, in the half-life of a radioactive element, in the way sound intensity is measured in decibels.
Comments
Post a Comment