Russian peasant multiplication

[Marc Glisse]

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>?

No.

> http://en.wikipedia.org/wiki/Ancient_Egyptian_multiplication#Russian_peasant_multiplication
>
> 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