Wraparound multiplicaton vs mullo

[Niels Möller]

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