Wraparound multiplicaton vs mullo
Niels Möller
nisse at lysator.liu.se
Sun Oct 18 10:07:54 CEST 2009
Torbjorn Granlund <tg at gmplib.org> writes:
> nisse at lysator.liu.se (Niels Möller) writes:
>
> Nut it *is* mod 2^n - 1, for certain values of n.
>
> Which values of n?
For the current code, bitsize n must be a multiple of GMP_NUMB_BITS
(for the ref code), 2*GMP_NUMB_BITS (for x^2-1) or 4*GMP_NUMB_BITS
(for x^4-1).
> I don't see how zero can be generated ever in the ref code, except
> when multiplying zero. (The mul_2nm1_2 and mul_2nm1_4 functions
> are more likely to generate zero, I think.)
That might be the case: Whenever zero is represented as B^n-1 rather
than 0 in the inputs, a zero output is also represented as B^n-1. But
I haven't thought carefully about that.
> The testing code does not seem to think that the two representations of
> zero are equal. :-)
The relevant test cases would be all zeros inputs, and inputs that
contain factors of B^n-1. The random numbers used by the testcode
probably doesn't include such inputs.
Regards,
/Niels
More information about the gmp-devel
mailing list