mod to symmetric range
Paul.Zimmermann at loria.fr
Mon Sep 6 20:24:49 CEST 2010
> 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
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).
More information about the gmp-discuss