user42 at zip.com.au
Sat Nov 15 08:39:22 CET 2003
nisse at lysator.liu.se (Niels Möller) writes:
> Are there any hard theoretic results that give lower bounds for the
> number of k x k -> 2k multiplications that are needed for multiplying
> two n-bit numbers?
I guess all the usual karatsuaba, toom and fft approaches can apply.
At small sizes it probably comes down to the relative cost on the CPU
of mul versus add+carry.
Ultrasparc would be one where additions are reasonable but the integer
multiplier is pretty ordinary. K6 on the other hand does a mul in
only 1 cycle longer than an adc.
More information about the gmp-discuss