mod to symmetric range
Paul Zimmermann
Paul.Zimmermann at loria.fr
Tue Sep 7 17:45:07 CEST 2010
Torbjörn,
> mpz_add (rem, rem, divisor); /* PZ: if B is odd, then the symmetric mod
> is fully symmetric, thus we could simply
> mod |rem|, and change its sign
> afterwards, avoiding an addition.
> If B is even, the only case where this
> would fail is when rem = -|B|/2, but
> this can be detected below. */
>
> I am afraid I don't understand this comment.
>
> I don't understand "we could simply mod |rem|". The addition could be
> avoided if we used mpn division, computing mod |divisor|. Perhaps
> that's what you're saying?
if rn < 0, which means that the remainder rem is negative, instead of adding B
to make it positive, you can continue with |rem| (as in the positive case), and
negate the result only at the very end:
- if B is odd, since the output range is symmetric, just flip the result sign
- if B is even, flip the result sign, and only when the result is -|B|/2, add B
Is that clearer?
The code will be a little more complex, but should be more efficient. On the
other hand, in most applications B will be positive and thus rn >= 0, thus I'm
not sure this is critical.
> The size passed to mpn_cmp is different (bn vs rn), unfortunately. But
> your cmp comment implies that we can always use size rn!
sorry I did not spot the bn vs rn difference. But indeed, you can replace
mpn_cmp (rp, tp, bn) by mpn_cmp (rp, tp, rn) in the rn == bn branch, and then
both branches are equal (up to the computation of bhl).
> if (mpn_cmp (rp, tp, rn) > 0) /* PZ: same remark as above */
>
> I don't think this cmp can use fewer limbs.
yes it could, since rp[rn - 1] == bhl, thus rp[rn - 1] == tp[rn - 1].
(We only have to compare rn-1 limbs of rp, thus bn-2 of tp.)
Another concern is about bp[bn - 2], where we need bn >= 2. But since in that
case bn > rn, and rn >= 1 (you checked the special case rn == 0 before), this
is ok.
> Thanks for nice feedback!
you are welcome.
Paul
More information about the gmp-discuss
mailing list