Russian Multiplication

Also called "Ethiopian multiplication." To multiply two numbers  and , write  and  in two columns. Under , write , where  is the floor function, and under , write . Continue until . Then cross out any entries in the  column which are opposite an even number in the  column and add the  column. The result is the desired product. For example, for 

Russian multiplication works because it implements binary multiplication:

1. If , accumulate .

2. Right-shift  one bit.

3. If , exit.

4. Left-shift  one bit.

5. Loop.

REFERENCES:

Wells, D. The Penguin Dictionary of Curious and Interesting Numbers. Middlesex, England: Penguin Books, p. 44, 1986.