Logs Count Doublings

Lesson 7 of 11 · 7 min · Free, no account needed

What you will learn

A logarithm counts doublings: log₂ 1024 = 10 because 2¹⁰ = 1024.
log₁₀ counts times ×10: log₁₀ 1,000,000 = 6. Between powers, the log is between whole numbers: log₂ 100 ≈ 6.6.
Halving a search each time needs only about log₂ n questions: 20 for a million.

Guess my number from 1 to a million with yes/no questions. How many do you need?
Drag the lever to your bet.
Cut the ribbon down to one cell.
The ribbon has 1024 cells. Each tap keeps one half. Count the cuts.
Game: find my number from 1 to 1000.
Tap the strip to guess. I answer higher or lower. Par is 10 questions.
Counting doublings has a name.
The logarithm log₂ x answers: how many times do I double 1 to get x? log₂ 1024 = 10, because 2¹⁰ = 1024.
It is the same count as halving x back down to 1.
log₁₀ x counts times ×10: log₁₀ 1000 = 3. A log turns an exponent question around.
Build log₁₀ with ×10 blocks.
Stack ×10 blocks on the 1 until you reach 1000, then a million.
Place the numbers on the doubling ruler.
Each tick is one more doubling. Drag 8, 100 and 1000 to where they belong.
This program should halve 1024 all the way down to 1.
It stops at 32. Change one number so it reaches 1.
Halving 1024 to 1 takes log₂ 1024 = 10 steps. range(1, 11) gives step = 1 to 10: ten steps.
So how many questions for a million?
Turn the dial to the fewest doublings that pass 1,000,000, then Check.
Each yes/no answer halves what is possible. 2²⁰ = 1,048,576 is the first power of 2 above a million, so 20 answers always narrow it to one number.
Speed round: five logs in 40 seconds.
Use the ladder of doublings.

Lessons are interactive and need JavaScript. Turn it on to play them.