8 ms·
Looking at https://en.wikipedia.org/wiki/Multiplication_algorithm#Peasant_or_binary_multiplication https://en.wikipedia.org/wiki/Multiplication_algorithm#Peasa.
by pbiggar 13y ago
Looking at https://en.wikipedia.org/wiki/Multiplication_algorithm#Peasant_or_binary_multiplication https://en.wikipedia.org/wiki/Multiplication_algorithm#Peasa..., isn't this exactly the same as decimal long multiplication, except using binary?
- bcoates 13y agoThe long multiplication algorithm has two nested inner loops, each reducing one of the inputs to digits (dividing and multiplying by fixed values), multiplying them with a lookup table, then performing add-with-carry against inner and outer accumulators. The Russian Peasant Algorithm optimizes this for the binary case by noticing that the inner multiply is always by 0 or 1 so it's trivial and never carries, removing the inner loop entirely and allowing you to use only one accumulator.