The Russian Peasant's Algorithm is a recursive algorithm for multiplication that uses doubling, halving, and addition. The basic idea is that to multiply n by m, we can compute instead (n/2)*(2m) if n is even and ((n-1)/2)*(2m) + m if n is odd. In either case the multiplier drops by a factor of two or more, at the cost of one halving, one doubling, and possibly one addition. If we assume that halving, doubling, and addition are all constant-time operations, this gives a recurrence

• T(n) <= T(n/2) + Theta(1) = Theta(log n).

Note however that the size of the multiplier is lg n, so this is closer to being a linear-time algorithm (or quadratic-time if we charge Omega(k) time to add k bits).

The usual recursive description of the Russian Peasant's Algorithm requires keeping track of all the stray m's that have to be added back in, which has the advantage of simplicity but the disadvantage of storing up to lg n extra numbers, which is well beyond the atrophied memory capacity of most literate 21st-century humans and is likely to tax the brains of even the smartest 19th-century Russian peasants. The original algorithm keeps track of these with a single accumulator, and has the following iterative structure. Note that the algorithm as written only works for n > 0.

{{{RussianMultiply(n, m):

• accumulator = 0

  while n > 1:

  • if n is even:
    • n = n/2 m = m*2
    else:
    • n = (n-1)/2 accumulator = accumulator + m m = m*2
  return accumulator + m

}}}

The algorithm can easily be proven correct by showing that n*m+accumulator does not change during each pass through the loop.

Exercise: Try multiplying some big numbers in your head using this algorithm.

CategoryAlgorithmNotes