Opteron speed

Kevin Ryde 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 mailing list