Would someone mind elaborating the explanation in the manual?
David McKen
cic_3_b at yahoo.com
Fri Oct 24 21:42:39 CEST 2003
In the efficiency section of the GMP manual I came across the
following couple lines
--Begin quote--
However when testing divisibility by several small integers, it's
best to take a remainder modulo their product, to save
multi-precision operations. For instance to test whether a number is
divisible by any of 23, 29 or 31 take a remainder modulo 23*29*31 =
20677 and then test that.
--End quote--
Needless to say I don't understand this. Does someone have either a
web site that has the formulas describing this process (also if
possible a proof) or some example code that achieves this purpose?
I have already searched google and I keep coming up with the disible
"tricks" these only show divisibility for one number. I am interested
in checking if a number is divisible by a couple small numbers (to
weed out values before I waste time doing detailed computation)
Thanks in Advance
=====
Signed
David Mcken
Life Sucks
Live with it
__________________________________
Do you Yahoo!?
The New Yahoo! Shopping - with improved product search
http://shopping.yahoo.com
More information about the gmp-discuss
mailing list