mod to symmetric range
rpearcea at cecm.sfu.ca
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.
More information about the gmp-discuss