mod to symmetric range

Roman Pearce rpearcea at
Sun Sep 5 10:48:06 CEST 2010

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

More information about the gmp-discuss mailing list