Russian peasant multiplication

Marc Glisse marc.glisse at
Sat Feb 22 13:44:29 UTC 2014

On Sat, 22 Feb 2014, Oskar Wieland wrote:

> isn't the Russian peasant multiplication not to prefer against the
> grammar school method in <mpn/generic/mul_basecase.c>?


> For every step there is only:
> one left shift
> one right shift
> one addition (odd numbers only)

Think of multiplying just 2 64-bit numbers. In one case, that's just one 
instruction (hardware multiplication). In the other, depending on the 
number of bits that are 1 in the binary representation of the numbers, it 
can be a few hundred operations.

This technique is only worth it when you know in advance there are very 
few 1 bits in one of the numbers, and indeed we have special code for 
multiplication by 3 and 5 somewhere.

> This might be an O(log N) algorithm...

Certainly not.

Marc Glisse

More information about the gmp-discuss mailing list