illuminating science

So I was reading this old book of mathematical (and other) curiosities recently and I came across a method that Russians used to use to multiply two numbers. A little Googling reveals the technique to be Russian Peasant Multiplication. It allows to you multiply any two numbers with without knowing your times tables - all you need is to be able to do addition plus doubling and halving numbers.

Here’s how it works. Take your two numbers, e.g., 42 times 24. Double the first number and halve the second, at each step ignoring any remainder:

   42 x 24
   84 x 12
  168 x 6
  336 x 3
  672 x 1

Then, cross out the lines with an even number in the righthand (halving) column:

   42 x 24
   84 x 12
  168 x 6
  336 x 3
  672 x 1

Then, simply add up all the numbers remaining in the left-hand (doubling) column:

336 + 672 = 1008

A quick check on Google shows that’s the right answer!

The proof, which I worked out through a little scribbling on the fogged up glass of my shower before I went to bed last night, is a really elegant piece of mathematics involving binary numbers. I won’t post it here, in case anyone fancies having a go themselves - it’s not that hard, but it’s quite clever. That’s one thing I’ve always loved about mathematics - there are these incredibly beautiful results which just drop out, and the proofs are definite and precise and often, well, beautiful!

Now, I wonder how fast this procedure is compared to “conventional” multiplication? There’s probably some small gain for smaller numbers (someone suggested that peasants might have used stones to keep count of their smaller numbers) but I suspect once you’re into 3 or 4 digit numbers, you’d be better off with your timetables. I wonder if there’s some analysis of the number of steps in each case?