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