14 ms·
Four multiplications, not two (three if you only need the low 16b of the result).
by stephencanon 10y ago
Four multiplications, not two (three if you only need the low 16b of the result).
- yorwba 10y agoYou can get the full 32-bit result in only three multiplications using https://en.wikipedia.org/wiki/Karatsuba_algorithm https://en.wikipedia.org/wiki/Karatsuba_algorithm , but it requires more additions.
- stephencanon 10y agoYeah, in practice Karatsuba isn't a performant option for small operands unless your multiplier is catastrophically slow. (And it still doesn't get you to two multiplications.)