Would someone mind elaborating the explanation in the manual?
David McKen
cic_3_b at yahoo.com
Sat Oct 25 06:43:08 CEST 2003
Ahh well now that makes sense.
What I am trying to do is factor a number so the more of the small
primes that I can test for divisibility the less time I waste trying
numbers that simply won't divide into my number.
Thank you for your time Rob.
Signed
David McKen
--- Sisyphus <kalinabears at iinet.net.au> wrote:
> David McKen wrote:
> > 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--
> >
>
> It's telling you to calculate R = bignum % 20677, and to then check
> R
> for divisibility by 23, 29, and 31.
>
> That will work because if x divides bignum, x also divides
> bignum % (x * a) for all non-zero integers a.
> And if x does not divide bignum, x does not divide
> bignum % (x * a) for any non-zero integer a.
>
> It will be quicker because it is faster to check R for divisibility
> by
> 23, 29, and 31 than it is to check bignum for divisibility by those
> same
> 3 numbers. There's a cost in calculating R in the first place, but
> that
> cost is more than offset by the savings.
>
> At least, that's how I'm reading it. As to whether there's a saving
>
> would, I think, depend upon the size of bignum, and upon the number
> of
> small integers for which divisibility needs to be tested. (If it
> were
> me, I'd want to do some timings to check .... I'm a little dubious
> that
> you'll find a saving for only 2 small test divisors).
>
> I've also seen literature (not specifically relating to GMP)
> suggesting
> that you could simply calculate the gcd of bignum and 20677 - or
> you
> could extend that to calculating the gcd of R and 20677. You have
> to be
> a little careful there if the "small" numbers are not primes - and
> I
> don't know how that method stacks up (speed-wise) against the above
>
> recommendation.
>
> Hth.
>
> Cheers,
> Rob
=====
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