mod to symmetric range

[Paul Zimmermann]

       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