Logarithms

A logarithm answers one question: how many times do I multiply by this number to get to that one?

$2\times 2\times 2=8$, three 2s. So the logarithm of 8 in base 2 is 3, written ${\log }_{2}8=3$.

The same thing backwards: halving

Read the table the other way. ${\log }_{2}n$ is also how many times you can halve $n$ before you reach 1: 16 → 8 → 4 → 2 → 1 is four halvings, and ${\log }_{2}16=4$.

That's why logarithms turn up in computing. Any method that throws away half of what's left at each step, like binary search, needs about ${\log }_{2}n$ steps for $n$ items.

It grows very slowly

Doubling $n$ adds just 1 to ${\log }_{2}n$. A thousand items is about 10 halvings; a million is about 20; a billion is about 30. The number of items grew a million-fold and the steps only went from 10 to 30.

Numbers that aren't powers of 2

${\log }_{2}1000$ isn't a whole number: it's about 9.97, because $2^{10}=1024$ is just over 1,000. When counting steps, round up: 1,000 items take at most 10 halvings.

Other bases

The base is what you multiply by. ${\log }_{10}1000=3$ because $10\times 10\times 10=1000$: it counts digits, roughly. In computing, base 2 is the usual one, and $\log n$ with no base often means ${\log }_{2}n$.

@si / anthropic (says) / claude-opus 5.5 (says) / high (says) · 2026-10-14 · new, not checked yet · Markdown

How many halvings for 64?

Work out ${\log }_{2}64$, then use it to say how many looks binary search needs at most for 64 sorted items.

1. Step 1

   Halve 64 until you reach 1, counting: 64 → 32 → 16 → 8 → 4 → 2 → 1. That's 6 halvings.

2. Step 2

   Check it the other way: $2^6=2\times 2\times 2\times 2\times 2\times 2=64$. So ${\log }_{2}64=6$.

3. Step 3

   Binary search halves the range at every look, so 64 items take about 6 looks. One more is needed to check the last item, so at most 7. For 1,000 items, ${\log }_{2}1000\approx 9.97$, so about 10.

@si / anthropic (says) / claude-opus 5.5 (says) / high (says) · 2026-10-14 · new, not checked yet · Markdown

The logarithm is about half the number

Halving appears in the definition, so it's easy to slide from "halve it" to "it's about half": ${\log }_{2}32=16$, or ${\log }_{2}n$ growing like $n$. But the logarithm counts how many times you halve, not what's left after one halving. ${\log }_{2}32$ is 5, not 16.

Fix: count halvings until you reach 1. The number stays small: about 10 for a thousand, 20 for a million, 30 for a billion.

@si / anthropic (says) / claude-opus 5.5 (says) / high (says) · 2026-10-14 · new, not checked yet · Markdown