Ancient Puzzles – Multiplication System by Ethiopians
Excerpts from Ancient Puzzles by Dominic Olivastro
The story [of ancient puzzles in Ethiopia] is told of a colonel who wished to purchase seven bulls, each costing 22 Maria Theresa dollars. The owner of the stock called the local priest, who performed the necessary multiplication by digging a series of holes (called houses) arranged in two parallel col-umns. At the top of one column, he placed 7 pebbles (the number of bulls to be purchased) and at the top of the second column he placed 22 pebbles (the cost of each bull). The colonel reports:
It was explained to me that the first column is used for multiplying by two: that is, twice the number of pebbles in the first house are placed in the second, then twice the number in the third, and so on. The second column is for dividing by 2: half the number of pebbles in the first house are placed in the second, and so on down until there is one pebble in the last house. Fractions are discounted.
The division column is then examined for odd or even number of pebbles in the cups. All even houses are considered to be evil ones, all odd houses good. Whenever an evil house is discovered, the pebbles are thrown out (from both columns) and not counted. All pebbles left in the remaining cups of the multiplication col-umn are then counted, and the total of them is the answer.
The colonel’s problem looks like this:
In other words, 7 • 22 = 154. If you look carefully at the numbers that are not crossed out in the first column, you will see that we are actually multiplying by powers of two. The multiplication above amounts to saying
$$ 7 • 22 = 14 + 28 + 112 = 7 • (2^1 + 2^2 + 2^4) $$
This may seem strange, but it is actually a very logical way of proceeding for people who do not have a full number system. The method is still in common use in certain parts of the Soviet Union.
A computer, too, does not have a full number system, at least not one that counts to 10. It prefers, like the Ethiopians, to express numbers in powers of two (called a binary representation), and for much the same reason: It is easiest for a computer to duplicate a number. Modern textbooks in computer science often begin with a simple trick for changing numbers into a computer’s binary representation. A little eerily, these books are repeating the principle discovered by the Ethio-pians. First take the original number and successively divide by two, throwing out fractions when they arise. (In our story, the colonel said the priest also threw away the fractions.) If the number is even (an evil house) write a 0 next to it, effectively throwing it away, and if it is odd (a good house) write a 1 next to it, effectively keeping it. The numbers read from bottom up are the computer’s representation of the original number. For example, to find how a computer stores the number 22, do the following:
|Divided by 2||Remainder|
Does the Ethiopian’s trick seem a little mystifying? If so, then the computer’s trick of changing a number to its binary form may throw some light on it. By calling numbers “good” and “evil” houses, the Ethiopian, in modern terminology, is “reducing a number modulo 2.” That sounds like a mouthful, but it only means we are finding the remainder of a number after dividing by 2. Evil houses are even numbers that leave a remainder of 0, and good houses are odd numbers that leave a remainder of 1. Instead of throwing out and keeping various houses, the Ethiopian is merely multiplying by this remainder.
There is nothing magical about the modulus 2. We can go one up on the Ethiopian by using a different modulus, as in Figure 2, where we find the product of 7 • 58 using modulus 3. Again we use two columns, headed by 7 and 58; but because we are using modulus 3, the first column is tripled instead of doubled, and the second column is divided by 3 instead of 2. To help the procedure along, I have included a third column, which lists
|First Column||Second Column||Remainder|
the remainder when the corresponding number in the second column is divided by three.
Just multiply the first column by the third column and sum up the products. In effect this throws away the evil houses, which are numbers that leave a remainder of 0, and keeps the two types of good houses, which are numbers that leave a remainder of either 1 or 2. This rule works for any modulus whatsoever, including the Ethiopians’ choice of modulus 2. (The reader may like to try other examples using higher moduli.) By the way, can you find the number 58 in its ternary form in Figure 2? In general, using modulus n will produce a method that changes a number to its «-ary representation.