Ten Little Algorithms, Part 1: Russian Peasant Multiplication
This blog needs some short posts to balance out the long ones, so I thought I’d cover some of the algorithms I’ve used over the years. Like the Euclidean algorithm and Extended Euclidean algorithm and Newton’s method — except those you should know already, and if not, you should be locked in a room until you do. Someday one of them may save your life. Well, you never know.
Other articles in this series:
- Part 1: Russian Peasant Multiplication
- Part 2: The Single-Pole Low-Pass Filter
- Part 3: Welford's Method (And Friends)
- Part 4: Topological Sort
- Part 5: Quadratic Extremum Interpolation and Chandrupatla's Method
- Part 6: Green’s Theorem and Swept-Area Detection
Russian Peasant Multiplication is one of those inaccurate and stupid-sounding names — who really wants to be a Russian peasant, anyway? It’s a technique for multiplication — well, that part’s accurate — that was apparently known almost four thousand years ago in Egypt, and is, apparently, one of the first two recorded algorithms, found on the Rhind Papyrus. (Somehow it has been attributed to the Russian peasant, although when I tried to search of how this name came to be, nothing significant showed up: everyone seems to just assert that Russian peasants used this method, without citing any reputable source. You’d think someone that had visited Russia in the 1800s and noted the fact would have written it down for posterity.)
Anyway, here’s how it works. Suppose you want to multiply 13 and 27. You write these numbers down on paper at the head of two columns. On each line below it, in one column you take half of the preceding number, rounding down, and in the other column you double the preceding number. Here’s an example:
27 | 13 |
---|---|
54 | 6 |
108 | 3 |
216 | 1 |
Now you add up all the numbers in the doubling column that correspond to odd numbers in the halving column. Here we’d add 27, 108, and 216 to get 351, which is the correct answer. In Python you could implement it like this:
def rpmul(a,b): result = 0 while b != 0: if b & 1: result += a b >>= 1 a <<= 1 return result rpmul(13,27)
Great, it works. So what?
(Cue that Miles Davis again!)
Algorithms for arithmetic may not seem very important at first. I mean, when have you ever used long division outside of school? That’s what calculators are for. But we are forgetting that prior to about 1970, electronic calculators were essentially unaffordable. The first electronic calculators costing less than \$1000 debuted in 1970 and 1971 from Japanese manufacturers, starting with the Canon Pocketronic. Canon beat a few of its competitors to market, including Busicom, which, for its entry into the handheld calculator business, contracted Intel to design the first microprocessor, the four-bit Intel 4004. (Busicom gave up exclusive rights to use the chip in order to get better pricing. Otherwise we might be working on computers with a sticker labeled Busicom inside™ and that just doesn’t have the same ring to it.)
So if you were an engineer or accountant or businessman prior to the introduction of the handheld calculator, and didn’t have the luxury of accessing expensive computers or desktop calculators, you would use other methods, like a mechanical calculator, or a slide rule, or an abacus, or pencil-and-paper. So fifty years ago, algorithms for arithmetic were important. Now we rarely even have to write software to multiply numbers; today’s processors have hardware logic in their ALU to multiply floating-point numbers and “small” (64-bit and under) numbers. Multiplication of arbitrary-precision numbers (aka “bignums”) is a whole art in itself and uses a variety of arcane techniques depending on the number size, but is available in libraries. Now that software like Python is readily available, I don’t have to know how to multiply, I can just do it:
123456789001002003004 * 987654321002003004
The important point of knowing the Russian Peasant method these days isn’t really to perform multiplication itself. It’s because the same method can be used for other types of calculations that are isomorphic to multiplication. Mathematicians love isomorphisms, and there are plenty of them in abstract algebra, which have odd names like fields and rings and groups and monoids. I can never keep these things straight, and whenever I need to know which is which, I have to look them up. In any case, ordinary arithmetic is only one type of computation, and there are others in discrete mathematics which share the same behavior as the ordinary operations like multiplication, division, addition, subtraction, and exponentiation. These include things like:
- Polynomial arithmetic
- Modular arithmetic
- Galois field arithmetic
If I want to multiply two elements of the quotient ring \( GF(2)/p(x) \), I can use the Russian Peasant method as well. This is a form of polynomial arithmetic in which all the coefficients are either 0 or 1, and coefficients are operated on modulo 2, and the polynomials themselves are operated on modulo some characteristic polynomial \( p(x) \). It sounds crazy, but is more common than you’d think, and is a fundamental part of CRCs and linear feedback shift registers, which I may write about more in detail in a future article. The halving and doubling operations in Russian Peasant Multiplication are isomorphic to division and multiplication by \( x \), addition is isomorphic to addition modulo 2, and determination of odd/even becomes a check whether the coefficients are 1 or 0.
Integer exponentiation is also, in a way, isomorphic to multiplication, in that we can use repeated squaring and multiplication instead of repeated doubling and addition:
def rpexp(a,b): result = 1 while b != 0: if b & 1: result *= a b >>= 1 a *= a return result print rpexp(3,13) print 3 ** 13
1594323 1594323
Multiplication in \( GF(2) \) works like this:
def rpmul_gf2(a,b): result = 0 while b != 0: if b & 1: result ^= a b >>= 1 a <<= 1 return result
Let’s look at those algorithms side-by-side:
|
|
|
They’re really the same method, just with slightly different operations.
So the next time you need to multiply (or exponentiate!) integers, you can take out your computer or calculator and punch the numbers in… or you can party like it’s 1899 and do it like the Russian peasants (and ancient Egyptians) apparently did.
© 2015 Jason M. Sachs, all rights reserved.
- Comments
- Write a Comment Select to add a comment
http://rosettacode.org/wiki/Ethiopian_Multiplication
It is mentioned as Russian peasant multiplication without any refs to Egypt in quite popular Russian science ed book by very popular author Yakov Perelman. Book is called "Math for fun", some links to Amazon http://www.amazon.com/s/ref=dp_byline_sr_book_1?ie=UTF8&field-author=Yakov+Perelman&search-alias=books&text=Yakov+Perelman&sort=relevancerank
http://rosettacode.org/wiki/Ethiopian_multiplication#R:_Without_tutor
Thanks!
To post reply to a comment, click on the 'reply' button attached to each comment. To post a new comment (not a reply to a comment) check out the 'Write a Comment' tab at the top of the comments.
Please login (on the right) if you already have an account on this platform.
Otherwise, please use this form to register (free) an join one of the largest online community for Electrical/Embedded/DSP/FPGA/ML engineers: