mod to symmetric range
Torbjorn Granlund
tg at gmplib.org
Mon Sep 6 22:32:06 CEST 2010
Paul Zimmermann <Paul.Zimmermann at loria.fr> writes:
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).
I implemented a function that attempts to compute the following function:
/*
GMP symmetric mod, i.e., floor((2-|B|)/2) <= A smod B <= floor(|B|/2)
E.g.:
B = 1: return 0
B = 2: return 0 1
B = 3: return -1 0 1
B = 4: return -1 0 1 2
B = 5: return -2 -1 0 1 2
*/
Efficient code at the mpz level is attached. I'd appreciate if you Paul
could review my code skeptically and if you Roman could test it!
-------------- next part --------------
A non-text attachment was scrubbed...
Name: smod.c
Type: application/octet-stream
Size: 2619 bytes
Desc: not available
URL: <http://gmplib.org/list-archives/gmp-discuss/attachments/20100906/a4cfe0fd/attachment.obj>
-------------- next part --------------
--
Torbj?rn
More information about the gmp-discuss
mailing list