Wraparound multiplicaton vs mullo
Niels Möller
nisse at lysator.liu.se
Sun Oct 18 15:44:45 CEST 2009
Torbjorn Granlund <tg at gmplib.org> writes:
> nisse at lysator.liu.se (Niels Möller) writes:
>
> In the current code, the x^2-1 algorithm requires that n is even, and
> the x^4-1 algorithm requires that n is divisible by 4. That could of
> course be relaxed at the cost ofextra shifting, assuming that
> the number of bits is divisible by 2 and 4, respectively.
>
> Just to make sure we have the same understanding, what you mean is that
> size*GMP_NUMB_BITS is divisible by 2 and 4, respectively, correct?
Current code requires that size (measured in limbs) is divisible by 2
and 4. It could be improved to require that size*GMP_NUMB_BITS is
divisible by 2 or 4. And in the common case that GMP_NUMB_BITS is
itself divisible by 2 or 4, that's of course true for all values of
size.
A different way to generalize the code would be to allow for
multiplication mod 2^n-1 for any n divisible by 2 or 4, but I don't
think that's terribly useful. For typical applications of wraparound
arithmetic (newton iterations, and ab - cd), it's no problem to round
n up a bit if needed to fit the algorithm, I think.
> Which proper mullow_basecase, mpn_mul_n should not be used at all.
> Furthermore, x^2-1 will get pushed upwards.
And maybe there will be no place left for it...
/Niels
More information about the gmp-devel
mailing list