As I was “StumbleUpon”-ing tonight, I was reminded of something that I was thinking about a couple of days ago, and though I’d write it down here. Let’s say we want to multiply, oh… 47 by 69. We begin by writing the two numbers:

47 69

and then proceed by halving the first number and doubling the second number repeatedly.

47 69

23 138

11 276

5 552

2 1104

1 2208

Now, we cross out all the rows where the first column is even, and add all the remaining entries in column two:

47 69

23 138

11 276

5 552

~~2 1104~~

1 2208

If we add up 69+138+176+552+2208, we get 3243, which is indeed 47 * 69. This is so-called *Russian peasant multiplication*. I’ve probably known about this since I was eleven or twelve, but never really gave it much thought. Later, it seemed like the obvious way to implement multiplication on computers which had shift instructions. It’s not hard to see why this works if you are familiar with binary arithmetic, but I must admit that if you *weren’t* familiar with binary arithmetic, it seems to me unobvious how you would figure this stuff out. Yet, the ancient Egyptians actually knew about a closely allied technique that allowed them to do multiplication and division, so it would appear that the principles of binary arithmetic are actually exceedingly old. Wikipedia has some nice information.

Didn’t work for me at first, until I figured that you need to truncate successive divisions by 2 in the first column (only an issue if the first number is odd). Then it works. Pretty cool!