Question:
I was recently introduced to a fun mathematical trick called
Russian multiplication. First take two numbers that you
want to multiply and place them at the top of two adjacent
columns. Divide the number in the left-hand column by two.
Ignore any remainder and write the new number beneath the
first. Repeat this step until you are left with 1. Now
double the number in the right-hand column and write the
answer below it. Keep doubling all the way down until there
are an equal number of figures in both of the columns.
Delete the numbers in the right-hand column that are next
to even numbers in the left-hand column. Now add up the
remaining numbers in the right-hand column and you will
find that the total equals the result of multiplying the
two original numbers at the head of the lists. Why?
For example:
9x 8 [=72]
4 16 (delete)
2 32 (delete)
1 64
Total for right-hand column: 72
Answer:
The trick of "Russian Multiplication" is actually just long
multiplication, but done base 2 instead of base 10. The
first stage, of repeated division by zero is converting the
number into base 2. An even number corresponds to a 0 bit
and an odd number to a 1 bit.
In normal long multiplication we do a single digit
multiplication from one number and put extra zeros at the
end of the other number. In Russian Multiplication the
single digit multiplication is either multiplying by 0
(corresponds to deleting) or 1. At the end of both we add
up the results to produce the final answer.
Russian Multiplication uses roughly log base 2 of m addition
operations to work out n * m, instead of m additions. It
is sometimes used to do multiplication on a computer which
doesn't have a multiply instruction.
It can also be modified to work out n to the power of m,
in around log base 2 of m multiply operations. This is used
in the implementation of some cryptographic schemes. In
this case, instead of doubling, you square the numbers in
the second column and at the end you multiply instead of
adding.
To work out 8 to the power of 9 using 5 multiplications
instead of 9:
9 8
4 64 (delete)
2 4096 (delete)
1 16777216
Product for right-hand column: 134217728