5
$\begingroup$

I've had a book for many years called Puzzles, Mazes, and Numbers which describes a method for performing multiplication as follows called "Russian peasant multiplication":

There are two columns, on the left hand side the number is halved, rounding down and on the right hand side, each successive number is doubled. In the algorithm described in the book, rows corresponding to even numbers in the left column are struck out. In this example, rows with even numbers in the left column simply have a blank entry in the right.

    45  x   89    89
    22     178
    11     356   356
     5     712   712
     2    1424
     1    2848  2848
 -----------------------
                4005

My understanding is that this is similar to the Ancient Egyptian method of multiplication, but that the Ancient Egyptians decomposed the left argument into powers of two by repeatedly subtracting the largest power of two possible, rather than by repeatedly dividing by two and checking the parity.

I'm curious whether a doubling and mediation algorithm with the parity check as described here was ever the/an ordinary of doing multiplication anywhere in the world.

One source cited by the Wikipedia article claims that the supposed Russian origin of the algorithm is a bit murky and hard to definitively show.

$\endgroup$
2
$\begingroup$

That may be considered a cheating answer but indeed there was an era when this algorithm was used intensely. I'm talking about early decades of electronic computers.

This algorithm is very easy to implement in binary because multiplication and division by 2 becomes simply a 1 bit shift of the number in the left or the right direction correspondingly. The lowest bit gives you the parity. Thus all you need from you processor is to have a shifter and adder. Before appearance of new algorithms in 60s and possibility to perform several additions simultaneously at a hardware level this was how multiplication was done on computers.

The positional system provides you with several techniques relying on the knowledge of the multiplication table for all numbers up to the base. The Ancient Egyptian method is attractive if you don't have any of that (or restricted to the base 2 like computers). I couldn't find (not that I searched very long...) much info on the multiplication methods from Ancient Greek sources. However I find it likely that by the time such sources could exist this Ancient Egyptian multiplication method was not the main one for the people educated in arithmetics (who, again would write such sources). The Babylonians had a positional numerical system and multiplication tables by 2000 bc. While true positional numerical systems were not that popular in the ancient world, the abacus was.

$\endgroup$
2
$\begingroup$

The analogue for exponentiation, usually referred to as "square-and-multiply" is in common use in applied cryptography, e.g. in the RSA system for public key encryption. See for example Section 14.6 of Menezes et al's Handbook of Applied Cryptography.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.