Russian Peasant Multiplication
Ogilvy and Andersen, in their excellent book Excursions in Number Theory , recount the true story of an Austrian colonel who wanted to buy seven bulls in a remote part of Ethiopia some sixty or so years ago. Although the price of a single bull was set at 22 Maria Theresa dollars, no one present could work out the total cost of the seven bulls — and the peasants, being peasants, didn’t trust the would-be buyer to do the calculation himself. Eventually the priest of a neighbouring village and his helper were called in.
“The priest and his boy helper began to dig a series of holes in the ground, each about the size of a teacup. These holes were ranged in two parallel columns; my interpreter said they were called houses. The priest’s boy had a bag full of little pebbles. Into the first cup of the first column he put seven stones (one for each bull), and twenty-two pebbles into the first cup of the second column. It was explained to me that the first column was used for doubling; that is, twice the number of pebbles in the first house are placed in the second, then twice that number in the third, and so on. The second column is for halving: half the number of pebbles in the first cup are placed in the second, and so on down until there is just one pebble in the last cup. If there is a pebble remaining when doing the halving it is thrown away.
The division column (the right one) is then examined for odd or even numbers of pebbles in the cups. All even houses are considered to be evil ones, all odd houses good. Whenever an evil house is discovered (marked in bold), the pebbles in it are thrown out and not counted, and the pebbles in the corresponding ‘doubling’ column are also thrown out. All pebbles left in the cups of the left, ‘doubling’ column are then counted, and the total is the answer.”
from Ogilvy & Andersen, Excursions in Number Theory
The working on paper would be as follows :
Doubling Column Halving Column
7 22
14 11
28 5
56 2
112 1
154
The priest worked out the result using holes and pebbles in the way I have demonstrated though instead of using different coloured beans the helper simply removed the stones from right-hand holes opposite ones with an even number in them. The colonel duly paid up, astounded to note that the crazy system ‘gave the right answer’.
Let us go further back in time. We suppose that a ‘primitive’ society had grasped the principle of numerical symbolism at the most rudimentary level, namely that a chosen single object such as a shell or bean could be used to represent a single different object, such as a tree or a man and that clusters of men or trees could be represented by appropriate clusters of shells — the ‘appropriateness’ to be checked by the time-honoured method of ‘pairing off’. This society has not, however, necessarily attained the stage of realizing that a single ‘one-symbol’ will do for every singleton, let alone reaching the stage of evolving a base such as our base ten. Now suppose the chief wants each of the villages in a certain area to provide ‘nyaal’ or
□ □ □ □ □ □ □ young men for some public works or warlike purpose. We have nyata’ or □ □ □ □ □ □ villages from which to draw the task force. The chief relies on two shamans to carry out numerical calculations, both of whom are adept in the practice of ‘pairing off’ but one has specialized in ‘doubling’ imaginary or actual quantities, the other in ‘halving’ imaginary or actual quantities. Although both shamans know that every quantity can be doubled, the ‘halving’ shaman knows that this procedure does not always work in reverse. He gets round this by simply throwing away the extra bean or shell — the equivalent of our ‘rounding off’ a quantity to a certain number of decimal places.
The ‘halving shaman’ works with a column of holes on the left hand side of a ‘numbering area’ (a flat piece of ground with holes in it) and he has a store of short sticks, shells or some other common object, which he places in the holes, or simply in a cluster on the ground. The doubling shaman works with a similar column of holes on the right but he has a store of beans or shells which are in two colours, light and dark. (The use of colour to distinguish two different types of quantities, or to distinguish between males and females, was the invention of a revered shaman who taught the two current shamans.)
The halving shaman sets out the sticks or shells representing the villages and tries, if possible, to have two matching rows. The doubling shaman watches carefully and, if the amount on the left can be arranged in two rows exactly, as in this case, he starts off with a set of dark coloured beans to represent the young men to be co-opted for the task at hand from each village. We thus have
Villages Young males
□ □ □ ■ ■ ■ ■
□ □ □ ■ ■ ■
Now the Halving Shaman selects half the quantity in the first hole, i.e. a single row of □ □ □, and arranges it as evenly as possible in two rows. In this case, there is a bean left over, and the Doubling Shaman, noticing this, doubles the original amount on the right but also changes the colour of the beans. We have
□ □ □ □ □ □ □ □ □
□ □ □ □ □ □ □ □
The Halving Shaman discards the extra unit on the second line of my diagram and once again halves what is left. This leaves just a single bean □ and, since we are not allowed to split a bean or shell, this signals the end of the procedure as far as he is concerned. The Doubling Shaman doubles his quantity and since the quantity on the left is ‘odd’ — it cannot be arranged in two matching rows — he once again chooses light coloured beans.
□ □ □ □ □ □ □
□ □ □ □ □ □ □
□ □ □ □ □ □ □
□ □ □ □ □ □ □
The two shamans collaborate to combine all the light coloured beans (but not the dark coloured ones) on the right hand side, giving a total of
□ □ □ □ □ □ □
□ □ □ □ □ □ □
□ □ □ □ □ □ □
□ □ □ □ □ □ □
□ □ □ □ □ □ □
□ □ □ □ □ □ □
The chief is given this amount of beans and thus knows how many young men he can expect to get for the task at hand. From experience, the chief will have a pretty good idea of what this collection of beans represents in terms of men and, if it seems inadequate for the task, may decide to increase the quota of young men impressed from each village. When preparing for battle, the chief might use human beings as counters, pair them off against the beans, then have them form square formations to judge whether he has a large enough army or raiding force.
If asked by a time traveller why the dark-coloured beans — which are always opposite an even number — are rejected, the Doubling Shaman would probably say that even amounts are female (because of breasts) and the chief doesn’t want effeminate men or boys who are still living with their mothers.
The multiplicative system just demonstrated is very ancient indeed : it is probably the very earliest mathematical system worthy of the name and was doubtless invented, reinvented and forgotten innumerable times throughout human history. Since it does not require any form of writing and involves only three operations, pairing off, halving and doubling, which are both easy to carry out and are not troublesome conceptually, the system remained extremely popular with peasants the world over and became known as Russian Multiplication because, until recently, Russia was the European country with by far the largest proportion of innumerate and illiterate peasants. It is actually such a good method that I have seriously considered using it myself , at any rate as a visual aid in doing mental arithmetic — it is one of the tools employed by traditional ‘lightning calculators’ and mathematical idiots savants.
Actually, one could say that the three mathematical procedures predate not only the earliest tribal societies but even the existence of animals ! Viruses, the lowest form of ‘life’ — if indeed they are to be considered alive at all which is still a matter of debate — are incapable of doubling, i.e. cannot reproduce, let alone halving and have to get the DNA of another cell to do the work for them. They may be considered capable of ‘pairing off’ however, since a virus seeks out the nucleus of a cell on the basis of one virus, one nucleus. Bacteria, a much more advanced life form, reproduce by mitosis, essentially duplicating everything within the cell and splitting in two, the ‘daughter’ cell being an exact replica (clone) of the ‘mother’ cell. Each prokaryotic cell is diploid, i.e. has a double complement of chromosomes, and this (even) number cannot be changed — it is 2(23) = 46 in humans. Eukaryotes, however, though still capable of pairing off and reproducing by mitosis (doubling) are also able to halve this diploid number by producing special so-called haploid cells (gametes) which, in our human case, come in two kinds, spermatozoid and ovum. Fusion of the ‘egg’ and ‘sperm’ cells restores the diploid number and incidentally introduces a further mathematical operation, combination, which may be considered the distant ancestor of Set Theory. It is thus maybe not at all surprising that peasants the world over have felt at home with ‘Russian’ Multiplication, living much closer than we do to the generative processes of Nature, even if they did not know what was going on.
A good written notation is not at all essential for Russian Multiplication, but it does speed things up. Using our Hindu/Arabic notation, suppose you want to multiply 147 by 19. This is a somewhat tedious enterprise if you are not allowed a calculator and these days two students out of three would probably come up with the wrong answer. So here goes
19 147
9 294
4 588 147
2 1176 294
1 2352 2352
2793
Now do it with a calculator. The result: 2793.
Why does the system work? You might like to think about this for a moment before reading on. (It personally took me a long time to cotton on though someone I mentioned it to saw it at once.)
Russian Peasant Multiplication works because any number can be represented as a sum of powers of two (counting the unit as the 0th power of any number). Algebraically we have
N = An xn + An-1 xn-1 + …….+ A1 x1 + A0
with x = 2. In practice there are only two choices of coefficient for the An , An-1 …….A0 namely 0 and 1 because once we get to a remainder of 2 we move to the next column. When 0 is the coefficient this term is not reckoned in the final count — is discounted just like the pebbles in the hole opposite an even cluster. Since 1 × xn = xn, we can simply dispense with coefficients altogether — which is not true for any other base.
If we look back at the pattern of black and grey in the right hand column and write 0 for black and 1 for grey, we have the representation of the number on the left in binary notation (though it is in reverse order compared to our system). Take the multiplication of 19 and 147 a couple of pages back.
19 147
9 294
4 588 147
2 1176 294
1 2352 2352
2793
The pattern in the right hand column is, from the bottom upwards,
Grey
Black
Black
Grey
Grey = 10011 = 24 23 22 2 unit
1 0 0 1 1
= 1910
A hole in the ground functions as a ‘House of Numbers’ and can only be in two states: either it is empty or it has something in it (i.e. is non-empty). The Abyssinian priest’s assistant who removed the stones from a house opposite one with an even number of stones in it was placing the House in the zero state. The right hand column Houses were in fact functioning in two different though related roles: on the one hand they were in binary (empty or non-empty) while on the other hand they gave the quantities to be added in base-one.
Did people using the system know what they were doing? In most cases probably not although, judging by their confidence in handling arithmetical operations, the Egyptian scribes, using a very similar method I shall perhaps write about in a subsequent article, almost certainly did : the peasants using the system just knew it worked. There is nothing surprising or shocking about this — how many people today who use decimal fractions without a moment’s thought realise that the system only works because we are dealing with an indefinitely extendable geometric series which converges to a limit because the common multiple is less than unity?
One might wonder whether it would be possible to extend the principle of Russian Multiplication to tripling, quadrupling and so on?
Take 19 × 23 using 3 as divisor and multiplier
19 23
6 69
2 207
?
We have already run into difficulties since we cannot get back to the unit. On the analogy with modulus 2 Russian Multiplication, we might decide we have to take into account the final entry on the right nonetheless, plus all entries which are not opposite an exact multiple of 3. This means the answer is 207 + 23 = 230 which is way off since 10 × 23 = 230. What has gone wrong?
A little thought reveals that, whereas in the case of modulus 2 we only had to neglect at most a unit on the left hand side, in the case of modulus 3 there are two possible remainders, namely 1 and 2. If we are opposite a number on the left which is 1 (mod 3) we include the number on the right in the final addition. However, if we are opposite a number which is 2 (mod 3) we must double the entry on the right since it is this much that has been neglected. In the above 19 = (6 × 3) + 1 and so it is 1 (mod 3) but 2 at the bottom is (0 × 3) +2 and so is 2 (mod 3). Applying the above we obtain 23 + (2 × 207) = 23 + 414 = 437 which is correct.
To make the system work properly we would thus need not one but two ways of marking entries in the right hand column to show whether they just have to be added on or have to be doubled first. This is an annoying complication, and even apart from this it is not that easy to divide into three and to treble integers. And if we move onto higher moduli there are much greater complications still. The Russian way of doing things ceases to be simple and user-friendly. Russian Peasant Multiplication is a good example of an invention excellent in itself but which does not lead on to further inventions and discoveries: it remains all on its own like an island in the middle of the Pacific Ocean. Once the crucial improvement of distinguishing the entries to be added from the others was made, there was nothing much that could be done in the way of improvements except possibly the introduction of colour coding, my distinction between dark and light coloured beans. To actually find a better multiplication system you have to make a giant leap in time to the ciphered Greek system of numerals or the full place value Indian system — and even so the advantages would not have been apparent to peasants. If you are only dealing with relatively small quantities, Russian Multiplication is quite adequate, is easier to comprehend and there are less opportunities for making mistakes. In such a case we see that there is indeed a ‘simplicity cut off point’ beyond which it is not worth extending existing techniques, since the disadvantages outweigh the advantages. However, there may also be a ‘second time round point’ when technology has become so sophisticated that it has become ‘simple’ (= ‘user-friendly’) once more. Computers, being as yet relatively unintelligent creatures, have reverted to base 2 arithmetic though I believe 16 is also used. Wolfram’s Cellular Automata based on simple rules which specify whether a given ‘cell’ repeats or doesn’t can perform complicated operations like taking square roots of large numbers.
This cycle of invention, stasis, disappearance and re-invention happens all the time : it is more often than not impossible to improve on an early invention without making a giant leap, a leap requiring not only new ideas but large-scale social and economic changes which are usually felt to be undesirable because disruptive, or are quite simply out of the question given the available technology. Short of hiring expensive modern haulage equipment the best way to move large heavy objects across uneven ground is the time-honoured Egyptian system of wooden rollers which are repeatedly brought round to the front. (I have often had occasion to use this system myself in inaccessible places and it is surprising how well it works.) The long bow made of yew and animal gut more than held its own against the far more advanced crossbow : English bowmen won Agincourt against axe-wielding French knights and Genoese cross-bowmen largely because the crossbow is slow to reload and its effectiveness is much reduced in wet weather (the English kept their cat-gut dry until the battle began). In point of fact the longbow, an extremely rudimentary weapon, was only superseded in speed, range and accuracy by the repeating rifle ¾ one of Wellington’s military advisors seriously suggested re-introducing the longbow against Napoleon’s Grande Armée. And the horse as a means of transport was only superseded by the railway : messages were not transmitted much faster across Europe (if at all) under Napoleon than under Augustus Caesar. S.H. 26/1/12
Acknowledgment : This article appeared in M500 Issue 243 , “M500” being the magazine of the mathematical department of the Open University, editor Tony Forbes, for whom many thanks. .
Origins of Mathematics 