Would someone mind elaborating the explanation in the manual?
Sisyphus
kalinabears at iinet.net.au
Sat Oct 25 18:38:30 CEST 2003
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
--
Any emails containing attachments will be deleted from my ISP's mail
server before I even get to see them. If you wish to email me an
attachment, please provide advance warning so that I can make the
necessary arrangements.
More information about the gmp-discuss
mailing list