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.
