mod to symmetric range

[Paul Zimmermann]

       Dear Roman,

> Date: Sun, 5 Sep 2010 01:48:06 -0700 (PDT)
> From: Roman Pearce <rpearcea at cecm.sfu.ca>
> 
> I'm trying to efficiently compute r = a mod b with
> -(b-1)/2 <= r <= b/2.  Any suggestions?  All of my
> solutions move too much data around.
> 
> Ideally I could call an mpz_cmp_2exp function that
> would tell me if r * 2^1 > b using shifts and adds
> and O(1) memory.  That's a lot to ask for though.
> 
> I can do it with a copy, shift, and comparison but
> that's a lot of overhead for one bit of information.
> Heuristics could be used, but that's a mess.
> 
> Is there any interest in this?  In my application
> (computer algebra) the symmetric range is used to
> reconstruct small integers from images modulo p.
> It's preferable to have -k instead of p-k.
> 
> BTW, thanks for the library.
> 
> Roman Pearce
> CECM/SFU

this is a function I have written maybe ten times (if not more),
and I would like very much to have it included in GMP.

In my applications b is invariant, thus we might indeed precompute b/2,
but this is inefficient memory-wise, and the heuristic that compares the
most significant limbs of r and b should decide in most cases what to do
(note that b/2 is only needed for the comparison, not for the subtraction r-b
in case r > b/2).

Paul Zimmermann