Counting: from notches to bits

A shepherd with thirty sheep needs only a stick and a knife. In the morning a sheep leaves the pen, and a notch appears on the stick. In the evening the flock comes back, and the shepherd runs a finger along the notches: one sheep, one notch. If sheep and notches run out together, everyone is home; if notches are left over, it's time to go looking. No counting is needed at all, only matching.

The method is reliable, but it has a limit. A temple that receives grain from farmers counts sacks in thousands, a royal treasury in tens of thousands, and your bank has millions of accounts. Nobody wants a stick with a million notches: it can't be read, and it can't be added to another one like it. What's needed is a notation in which a large number takes up little room and is convenient to calculate with. People searched for it for several thousand years. Let's walk through the halls of an imaginary museum: each one displays a single solution, what it did well and where it stumbled.

The display case by the entrance

Before you enter the halls, stop at the display case. It shows one number written seven ways: as a hunter with a bone would write it, an Egyptian scribe, a Babylonian astronomer, a Roman tax collector, a Maya priest, an Indian mathematician and your phone. On the right is the number of signs each of them needed.

A digit and a number are different things, like a letter and a word. Our system has ten digits, 0 to 9, but infinitely many numbers: 7 is a one-digit number written with one digit, 365 a three-digit number written with three. Later we'll meet systems with two, twenty and sixty digits.

Hall one: notches

The oldest exhibit is a fragment of a baboon's fibula with 29 notches. It was found in Border Cave in the Lebombo Mountains, on the border of South Africa and Eswatini; radiocarbon dates put it at about 43,000 years old. A lunar month lasts about 29.5 days, so the bone is often called the oldest calendar. That's a guess: the bone is broken, so nobody knows how many notches it had originally, or what they recorded.

The Ishango bone, from the east of what is now the Democratic Republic of the Congo, is younger, about 20,000 years old. Its notches are arranged in three columns. One column has groups of 11, 13, 17 and 19 notches, all the prime numbers between 10 and 20. Another has 11, 21, 19 and 9, that is $10 + 1$, $20 + 1$, $20 - 1$ and $10 - 1$. It's tempting to see Stone Age number theory here, and some researchers do. Others think the notches simply kept the handle from slipping in the palm. The debate is unresolved, and the honest thing is to treat both bones as puzzles.

What is beyond doubt is this. A notch is the simplest numeral system of all: one mark per object. It has exactly one rule, which is why it is still in use. When you count votes by drawing strokes and crossing every fifth one, you are working in the first hall of our museum.

The weakness of notches is obvious at once: the length of the notation equals the number itself. A thousand is a thousand strokes. They take a long time to make, it's easy to be off by one, and nobody can tell 1000 notches from 1001 by eye. The first idea that comes to mind is a special sign for a whole bundle. That is what the Egyptians did.

Hall two: Egypt

In Egyptian hieroglyphic notation every power of ten has its own sign. One is a vertical stroke, ten a cattle hobble shaped like a horseshoe, a hundred a coil of rope, a thousand a lotus flower, ten thousand a raised finger, a hundred thousand a tadpole, and a million the god of infinity, Heh, with his arms raised. A number is written by repeating the signs as many times as needed: 365 is three coils of rope, six hobbles and five strokes.

Such a system is called additive: the value of the number is the sum of the values of its signs. Scribes put the large signs first and lined up identical ones in neat rows, but shuffle them and the number stays the same. There's no need for zero: if there are no tens, you simply don't draw any hobbles.

The ceremonial macehead of the pharaoh Narmer, carved around 3100 BC, records a victory: 120,000 prisoners, 400,000 oxen and 1,422,000 goats. The figures are probably exaggerated, but the notation is short: the goats take one Heh, four tadpoles, two fingers and two lotuses, nine signs in all. For round numbers Egyptian notation is very economical. A million is one sign for the Egyptians and seven digits for us.

Now write 999,999 the Egyptian way. Nine tadpoles, nine fingers, nine lotuses, nine ropes, nine hobbles and nine strokes: 54 signs. The length of the notation equals the sum of the number's digits, and in the worst case every power of ten costs nine signs. Column arithmetic is out of the question too. Adding two such numbers means pouring the signs into one heap and trading every ten identical ones for one of the next kind. It works, but slowly.

Hall three: Babylon

In Mesopotamia people wrote with a pointed stylus on wet clay, and drawing lotuses there was awkward. Babylonian scribes made do with two impressions: an upright wedge (one) and a corner wedge (ten). From these, as the Egyptians did from strokes and hobbles, they built the numbers from 1 to 59: 23 is two corner wedges and three upright ones.

Then comes something the Egyptians never had. A Babylonian wrote the number 60 with the same sign as 1, a single upright wedge, only further to the left. The value of a sign depends on its place: the rightmost group is units, the next is sixties, then $60 \cdot 60 = 3600$, and so on. This is the first place-value system we know of, and it was in use about four thousand years ago. Its base is 60. The number 365 on a Babylonian tablet is six wedges, a gap and five more wedges: $6 \cdot 60 + 5$. Look at the display case by the entrance: that's exactly how it is shown there.

The Babylonians paid for place value with ambiguity. For a long time they had no zero: if a place was empty, the scribe left a gap, and a gap in clay is easy to miss. Later a special placeholder sign appeared, but it was usually put only between digits, not at the end of a number. So a single wedge could mean 1, 60, 3600 or even $\frac{1}{60}$: there was no sign separating the whole part from the fractional part either. The reader guessed what the author meant from the sense of the problem.

Nobody knows for certain why sixty. But it's clear what makes this base convenient: 60 has twelve divisors, 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30 and 60. A half, a third, a quarter, a fifth and a sixth of sixty are all whole numbers, and fractions are easy to write in such a system. Counting in sixties outlived Babylon by millennia: through Greek astronomers it reached us as 60 minutes in an hour, 60 seconds in a minute and 360 degrees in a circle.

The clock on your screen is a living Babylonian tablet. The reading 2:05:30 means two hours, five minutes and thirty seconds, that is $2 \cdot 3600 + 5 \cdot 60 + 30 = 7530$ seconds. Three places, base 60, and even the zero in the empty place that the Babylonians missed so badly.

How many seconds long is the interval 1:01:01?

Three places in base 60: $1 \cdot 3600 + 1 \cdot 60 + 1 = 3661$.

Hall four: Rome

Everyone knows Roman numerals from clock faces and the names of kings: I is 1, V is 5, X is 10, L is 50, C is 100, D is 500, M is 1000. This is additive again, but with a twist: a smaller sign in front of a larger one is subtracted. IV is $5 - 1$, IX is $10 - 1$, XC is $100 - 10$. This makes the notation shorter: 1999 is MCMXCIX, seven signs instead of twenty-eight Egyptian ones. The largest number that can be written by the usual rules is MMMCMXCIX, that is 3999.

The Romans themselves were not strict about the subtraction rule. The gates of the Colosseum are numbered with IIII rather than IV, so gate 44 is labelled XLIIII. The habit survives today: on many clocks with Roman numerals four o'clock is marked IIII, although nine is IX.

Try adding XLVIII and LXXIV in columns. It can't be done: the signs don't line up by place, and the same letter is added in one spot and subtracted in another. The Romans didn't even try to calculate this way. They counted on an abacus, a board with lines along which pebbles were moved. The Latin for pebble is calculus, which gives us "calculation" and "calculator". Each line of the abacus stands for its own place: units, tens, hundreds. When ten pebbles gather on one line, they are removed and one is placed on the next.

So the Romans did have a place-value system, only on the board rather than in writing. They counted with pebbles and wrote the finished answer in numerals: $48 + 74 = 122$, CXXII. To move the board onto paper they lacked just one thing, a sign for an empty line. Without it, "three hundreds, nothing, five" and "thirty-five" look the same in writing.

The first edition of Leonardo of Pisa's Book of Calculation, which we'll meet two halls from now, is dated 1202. Write this number in Roman numerals.

$1202 = 1000 + 100 + 100 + 1 + 1$, that is M, C, C, I, I: MCCII.

Hall five: the Maya

On the other side of the ocean, with no connection to Babylon or India, the Maya arrived at place-value notation. They counted in twenties, probably after the number of fingers and toes. The digits from 0 to 19 were made of dots and bars: a dot is one, a bar is five, so 13 is two bars with three dots above them. Places were written in a column from the bottom up: units at the bottom, twenties above them, four-hundreds higher still.

The star exhibit of this hall is a shell. That was the Maya sign for an empty place, and it appears in their inscriptions no later than the fourth century AD. A sign for an empty place turned up in different corners of the world, among the late Babylonians, in India and among the Maya, and the Maya certainly reached it on their own. The reason was the same every time: in place-value notation an empty place has to be visible.

The Maya calendar had a correction: the third place was worth not $20 \cdot 20 = 400$ but $18 \cdot 20 = 360$, close to the length of a year. So in dates of the so-called Long Count the places are 1, 20, 360, 7200 and 144,000 days. Traces of counting in twenties survive in Europe too: in French 80 is quatre-vingts, "four twenties", and English once counted in scores.

Hall six: India and zero

The notation we use today took shape in India in the first millennium AD: base 10, nine digits for the values 1 to 9, and a separate sign for an empty place. In a temple in Gwalior there is an inscription from the year 876 that gives the size of a garden, 270 by 187 hastas (a hasta is a cubit), and says that the garden supplies the temple with 50 garlands a day. The zero in 270 and 50 is carved as a small circle. It is the oldest zero carved in stone in India itself. But Cambodia has a stone almost two hundred years older, from 683, on which the zero in the date 605 is shown as a dot. The stone went missing during the Khmer Rouge years, and in 2013 the mathematician Amir Aczel tracked it down again in a store of antiquities.

Scholars of the Arab world adopted the Indian digits. Around 825 Muhammad ibn Musa al-Khwarizmi wrote a book on Indian reckoning. The Arabic original is lost, but a Latin translation survives, beginning with the words "Dixit Algorizmi", "Al-Khwarizmi said". The garbled name of the author gave us the word "algorithm".

The new digits were brought to Europe by Leonardo of Pisa, later nicknamed Fibonacci. He opens his Book of Calculation (1202) with the main point:

These are the nine figures of the Indians: 9 8 7 6 5 4 3 2 1. With these nine figures, and with the sign 0, which in Arabic is called zephirum, any number can be written.

The Arabic sifr, "empty", gave both "zephirum", which became "zero", and "cipher". The new digits didn't catch on at once: merchants clung to Roman numerals and the abacus for several more centuries. Paper won in the end: you can calculate in columns anywhere, and the whole calculation stays on the page, where it can be checked.

So what is so special about this notation? Take 2026. The two on the left means two thousand, the zero means no hundreds, the next two is two tens, and the six is six units:

$$2026 = 2 \cdot 1000 + 0 \cdot 100 + 2 \cdot 10 + 6 = 2 \cdot 10^3 + 0 \cdot 10^2 + 2 \cdot 10^1 + 6.$$

Each digit is multiplied by a power of ten, and which power is decided only by the digit's place. The zero holds the place of the empty position: without it, 2026 would turn into 226. And ten itself is nothing special: any whole number greater than one can take its place.

The digits of the number, from the leading one $a_n$ to the last one $a_0$. Each is a whole number from $0$ to $b - 1$, and the leading digit isn't zero, otherwise it could simply be erased. The base, a whole number no smaller than two. The bar on top and the subscript say: this is a numeral in base $b$, not a product of digits. The weight of a place: one, $b$, $b^2$ and so on. Places are numbered from right to left starting at zero, and place zero has weight $b^0 = 1$. Example: $\overline{365}_{10} = 3 \cdot 10^2 + 6 \cdot 10 + 5 = 365$, while $\overline{365}_{8} = 3 \cdot 64 + 6 \cdot 8 + 5 = 245$. Same digits, different bases, and different numbers.

Why must there be exactly $b$ digits? If we allowed a digit equal to the base or larger, a number would have several notations. Give the decimal system a separate digit for twelve, and 22 could be written two ways: "2 2" (two tens and two units) and "1 12" (a ten and twelve units). With fewer than $b$ digits, some numbers couldn't be written at all. Exactly $b$ digits from $0$ to $b - 1$ give every natural number exactly one notation. That's a theorem, and we'll prove it in the next hall.

Place value delivered what the whole enterprise was for: column arithmetic. When you add 58 and 67, the units column gives 15: write five, carry one into the tens. That is exactly what the Roman did on the abacus when he traded ten pebbles for one. In any base $b$ the rule is the same: $b$ units of one place make one unit of the next.

Notice that "10" in base $b$ always means the number $b$ itself: one unit of the second place and no units of the first. If people had four fingers on each hand, we would write "10" meaning eight, and consider that system the only natural one.

Now about length. Three decimal digits are enough for all numbers up to 999, six for everything up to 999,999. Each new digit multiplies the supply of numbers by ten, while a new notch adds just one number. The same holds in any base.

For the decimal system this gives the familiar $999 = 10^3 - 1$ and $999{,}999 = 10^6 - 1$. A million notches versus seven digits: that is the whole difference between the first hall and the sixth.

The workshop: any base

In this hall you can touch the exhibits. Let's learn to convert numbers from one base to another: we'll need it in the last hall.

From base $b$ to decimal

The formula itself shows the way: multiply each digit by the weight of its place and add up. For example, $\overline{1011}_2 = 1 \cdot 8 + 0 \cdot 4 + 1 \cdot 2 + 1 = 11$. For long numbers it's easier to go from left to right: take the leading digit, multiply by the base, add the next digit, multiply again, and so on to the end. For $\overline{1011}_2$: $1$, then $1 \cdot 2 + 0 = 2$, then $2 \cdot 2 + 1 = 5$, then $5 \cdot 2 + 1 = 11$. This method is called Horner's scheme, and we'll meet it again in the chapter on polynomials.

From decimal to base $b$

The way back is division with remainder. Divide 37 by 2: that gives 18 with remainder 1. This remainder is the last digit of the binary notation. Why? Because $37 = 2 \cdot 18 + 1$, and all the places except the lowest together give a multiple of two; the remainder can only come from the lowest place. The remaining digits are the binary notation of 18. Keep dividing until the quotient is zero, and read the remainders from the bottom up:

$$37 \xrightarrow{:2} 18 \;(1) \xrightarrow{:2} 9 \;(0) \xrightarrow{:2} 4 \;(1) \xrightarrow{:2} 2 \;(0) \xrightarrow{:2} 1 \;(0) \xrightarrow{:2} 0 \;(1), \qquad 37 = \overline{100101}_2.$$

Check: $32 + 4 + 1 = 37$. The first remainder gives the last digit, the last remainder the first. If you read the remainders from the top down, you get $\overline{101001}_2 = 41$; that is the most common slip.

Why the ladder never fails

The ladder looks like a conjuring trick: divide, divide, copy the remainders out backwards, and there's the notation. Let's prove that it never fails, and along the way prove what we promised in the last hall: every natural number has exactly one notation in every base. Everything rests on division with remainder.

The idea: cut the number line into pieces of length $b$ and see which one $n$ falls into.

Mark the multiples of $b$ on the line: $0$, $b$, $2b$, $3b$ and so on. They grow without end and cut the line to the right of zero into pieces of length $b$ that follow one another with no gaps and no overlaps. Let's agree that a piece includes its left end, while its right end belongs to the next piece. The point $n$ falls into exactly one such piece: from $qb$ inclusive up to $(q+1)b$ exclusive. Exactly one, because the pieces neither overlap nor leave holes. The number $q$ of this piece is the quotient: from zero to $qb$ there are exactly $q$ steps of length $b$. The remainder $r = n - qb$ is the distance from the start of the piece to the point $n$. It is at least zero because $n \ge qb$, and less than the length of the piece because $n < (q+1)b$. So $0 \le r \le b - 1$ and $n = bq + r$. There's no other pair. If $n = bq' + r'$ and $0 \le r' \le b - 1$, then $n$ lies in the piece from $q'b$ to $(q'+1)b$, and there is only one such piece. So $q' = q$, and then $r' = n - bq = r$.

The idea: tie pebbles into bundles of $b$, bundles into packs of $b$ bundles, and so on. Each time fewer than $b$ items are left untied, and that is the next digit.

Lay out $n$ pebbles and tie them into bundles of $b$. Tie as many bundles as you can. Between $0$ and $b - 1$ pebbles will be left over: with $b$ or more you could tie one more bundle. By the lemma on division with remainder there are exactly $q_0$ bundles and exactly $a_0$ loose pebbles, where $n = b q_0 + a_0$. That is the last digit. Now do the same with the bundles: tie them into packs of $b$ bundles, each pack holding $b \cdot b = b^2$ pebbles. Again between $0$ and $b - 1$ bundles are left untied; that is the digit $a_1$, and $q_0 = b q_1 + a_1$. Carry on until some level has fewer than $b$ items: then there's nothing more to tie, and the number of items at that level is the leading digit. It isn't zero: we move up a level only if the previous one had at least $b$ items, and they made at least one pack. (If $n < b$ from the start, there's nothing to tie at all, and the notation is the single digit $n$.) Each level has at least $b$ times fewer items than the one before, so we stop after finitely many steps. Adding up the pebbles level by level gives $n = \dots + a_2 b^2 + a_1 b + a_0$: the notation exists. The notation is unique. Take any notation of $n$ with digits from $0$ to $b - 1$. All its places except the last are whole bundles, so together they make a multiple of $b$, while the last digit is less than $b$. So $n = b \cdot (\text{number of bundles}) + a_0$ with $0 \le a_0 \le b - 1$, and by the lemma $a_0$ has to be the remainder of $n$ divided by $b$, and the number written by the remaining digits has to be the quotient $q_0$. Apply the same argument to $q_0$, and so on digit by digit: each one is determined uniquely.

The idea: substitute each line of the ladder into the one before, and the positional notation appears by itself.

The lines of the ladder are the equations $n = b q_0 + r_0$, $q_0 = b q_1 + r_1$, $q_1 = b q_2 + r_2$, …, $q_{k-1} = b \cdot 0 + r_k$, and by the lemma each remainder is between $0$ and $b - 1$. The ladder is finite: as long as a number isn't zero, its quotient on division by $b \ge 2$ is strictly smaller than the number itself, and natural numbers can't decrease forever. Substitute the second equation into the first and expand: $n = b(b q_1 + r_1) + r_0 = q_1 b^2 + r_1 b + r_0$. Substitute the third: $n = q_2 b^3 + r_2 b^2 + r_1 b + r_0$. Reaching the last line, where the quotient is zero, we get $n = r_k b^k + \dots + r_1 b + r_0$. This is the notation of $n$ in base $b$: every $r_i$ is between $0$ and $b - 1$, and the leading digit $r_k = q_{k-1}$ isn't zero, since at zero we would already have stopped. By the theorem the notation is unique, so the ladder produces exactly it. The first remainder goes with $b^0$, so it's the last digit; the last remainder goes with $b^k$, so it's the first. Hence the rule "read from the bottom up".

Which octal number comes right after $\overline{17}_8$?

$\overline{20}_8$ $\overline{18}_8$ $\overline{110}_8$ $\overline{1A}_8$

Octal has the digits 0 to 7; there is no digit 8. After seven units the place overflows, just as ours does after nine: $\overline{17}_8 + 1 = \overline{20}_8$. In decimal that's $15 + 1 = 16$.

Write the number 100 in octal.

$100 = 8 \cdot 12 + 4$, $12 = 8 \cdot 1 + 4$, $1 = 8 \cdot 0 + 1$. The remainders from the bottom up: $\overline{144}_8$. Check: $1 \cdot 64 + 4 \cdot 8 + 4 = 100$.

The last hall: two signs

The shortest positional system is binary: base 2, digits 0 and 1. Gottfried Wilhelm Leibniz worked it out in detail in a manuscript of 1679 and in 1703 published the article "Explanation of Binary Arithmetic". Shortly before that the Jesuit Joachim Bouvet had sent him from China the 64 hexagrams of the Book of Changes, figures made of six solid and broken lines, and Leibniz saw in them the binary numbers from 0 to 63. The idea itself was known before him: Thomas Harriot tried binary notation in the early seventeenth century, but in manuscripts that nobody read for a long time.

Binary is awkward for people: 2026 looks like 11111101010, eleven digits. But for a machine it's ideal. A digit 0 or 1 can be stored by anything with two states: current or no current, a patch magnetised one way or the other, a pit or a flat spot on a disc. Two states are easy to tell apart even through noise, whereas ten voltage levels would get mixed up far more often.

Eight bits hold $2^8 = 256$ different values, from $\overline{00000000}_2 = 0$ to $\overline{11111111}_2 = 255$. Long strings of zeros and ones are hard to read, so programmers split them into fours and write each four as one hexadecimal digit: 0–9 and the letters A–F for the values 10 to 15. A byte is exactly two such digits. The colour #FF8800 on a web page is three bytes: the red channel $\overline{FF}_{16} = 255$ is fully on, green $\overline{88}_{16} = 136$ is about half on, and there's no blue. The result is orange.

An old joke: why do programmers confuse Halloween (Oct 31) with Christmas (Dec 25)?

Because $\overline{31}_8 = 25$ Because $\overline{31}_{16} = 25$ Because $\overline{31}_2 = 25$

Oct is short not only for October but also for octal, and Dec for decimal as well as December. Check: $\overline{31}_8 = 3 \cdot 8 + 1 = 25$. In hexadecimal $\overline{31}_{16} = 49$, and there's no such numeral as $\overline{31}_2$: binary has no digit 3.

Binary has a trick that conjurers love to show: a secret number from 1 to 63 can be guessed from six yes-or-no answers. Try it on yourself.

Six cards are six places. The card that starts with an eight collects every number that has a one in the eights place. When you say "yes", you are reporting the value of that bit. Six bits determine a number from 0 to 63 uniquely, like the six lines of a hexagram for Leibniz. Zero didn't make it onto the cards: all six of its bits are zero.

What is the largest number that can be written with ten bits?

Ten ones: $\overline{1111111111}_2$. Add one and every place overflows, giving $\overline{10000000000}_2 = 2^{10} = 1024$. So ten ones make $1024 - 1 = 1023$. In the same way the largest three-digit decimal number is $10^3 - 1 = 999$.

Back in the Egyptian hall

Let's return to the Rhind papyrus with fresh eyes. The Egyptians multiplied by doubling. To multiply 13 by 21, the scribe made two columns: on the left he doubled one, on the right the number 21, and he stopped when the left number grew past 13.

Then he ticked the rows whose left numbers add up to 13: $13 = 8 + 4 + 1$. The sum of the ticked right-hand numbers is the answer: $168 + 84 + 21 = 273$. The whole calculation is doublings and one addition; no times table is needed.

Why does the method work for any numbers, and what does binary have to do with it?

The idea: a product is the area of a rectangle, and the scribe's doublings are the areas of the strips it can be cut into.

The product $a \cdot b$ is the area of a rectangle with sides $a$ and $b$: it is made of $a \cdot b$ unit squares. Cut the width $a$ into pieces whose lengths are powers of two, each time taking the largest piece that fits into the remaining width, just as the scribe picks rows from the bottom up. A piece of length $1$ always fits while any width is left, so the whole width gets cut. Each power is used at most once: if after a piece $2^k$ at least $2^k$ were left, then before it at least $2^{k+1}$ would have been left, and we would have taken the piece $2^{k+1}$. So $a$ is a sum of distinct powers of two. That is its binary notation, and by the uniqueness theorem there is no other. Each piece is a strip of width $2^k$ and height $b$, with area $2^k \cdot b$. That is exactly the number in the scribe's right column: doubling $b$ exactly $k$ times means multiplying it by $2 \cdot 2 \cdot \ldots \cdot 2 = 2^k$. Cutting doesn't change area, so $a \cdot b$ equals the sum of the strips' areas, that is, the sum of the ticked right numbers. For $13 \cdot 21$: $13 = 8 + 4 + 1 = \overline{1101}_2$ and $13 \cdot 21 = 168 + 84 + 21 = 273$. The ticked rows are the ones of the binary notation, the skipped rows its zeros.

The Egyptian scribe wrote the multiplier in binary three thousand years before Leibniz, without suspecting it.

Check how comfortable you've become with conversions. If you'd like to take your own number apart with an explanation of every step, there is a solver for that.

Where next

Place-value notation with zero has dealt with the wall we started from: any natural number fits into a few digits, and addition, subtraction and multiplication can be done in columns by the same rules in any base. So far, though, zero only serves as a placeholder: it holds the place of an empty position but doesn't count as a number in its own right.

Now try to work out $3 - 5$. Columns don't help: you can't take five units from three, and there's nowhere to borrow from. A shepherd promised a neighbour five sheep, but he has only three. How many sheep does he have now? The natural numbers have no answer. We need zero as a full-fledged number, and numbers below zero, and for more than a thousand years mathematicians argued about whether such numbers had any right to exist. That argument is chapter 2.