brainwagon

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.