Ancient Egyptian multiplication

Ancient Egyptian multiplication, also called Ethiopian, Russian or peasant multiplication, is a systematic way of multiplying two numbers that needs no multiplication table, only the ability to double, halve and add. One factor is decomposed into a sum of powers of two, a table of doublings of the other factor is built, and the doublings that correspond to the chosen powers of two are added to give the product. The method is known from the Moscow and Rhind Mathematical Papyri, copied in the seventeenth century BC by the scribe Ahmes. Although the Egyptians had no concept of base two, the procedure is in effect long multiplication carried out on binary numbers, which is why it survives today in binary multiplier circuits in processors. It can also be seen as a special case of the square and multiply algorithm for exponentiation, and the Russian peasant variant halves one column and doubles the other, striking out even rows.