Ten Little Algorithms, Part 1: Russian Peasant Multiplication

Jason SachsMarch 22, 20155 comments

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.



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.)

This article is available in PDF format for easy printing

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:

2713
546
1083
2161

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:

def rpmul(a,b):
    result = 0
    while b != 0:
        if b & 1:
            result += a
        b >>= 1
        a <<= 1
    return result
def rpmul_gf2(a,b):
    result = 0
    while b != 0:
        if b & 1:
            result ^= a
        b >>= 1
        a <<= 1
    return result
def rpexp(a,b):
    result = 1
    while b != 0:
        if b & 1:
            result *= a
        b >>= 1
        a *= a
    return result

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.


Previous post by Jason Sachs:
   Two Capacitors Are Better Than One
Next post by Jason Sachs:
   Ten Little Algorithms, Part 2: The Single-Pole Low-Pass Filter


Comments:

[ - ]
Comment by Mike S.March 24, 2015
That was really cool, thanks. I had never heard the term "Russian Peasant Multiplication" before, and I wasn't familiar with this algorithm. Neat.
[ - ]
Comment by Paddy3118July 25, 2015
Rosetta code has a task for the algorithm implemented in around 100 programming languages and correctly titled Ethiopian multiplication:

http://rosettacode.org/wiki/Ethiopian_Multiplication
[ - ]
Comment by Severin6March 25, 2015
> Somehow it has been attributed to the Russian peasant
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
[ - ]
Comment by dgrapovJuly 25, 2015
Thanks for the post. Inspired me to write R version of the multiplication.

http://rosettacode.org/wiki/Ethiopian_multiplication#R:_Without_tutor
[ - ]
Comment by wheels24July 27, 2015
I used this algorithm in the runtime for a Microchip PIC-based language to implement multiply for 16- and 32-bit integers, as well as 32-bit floats.

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.

Registering will allow you to participate to the forums on ALL the related sites and give you access to all pdf downloads.

Sign up
or Sign in