On 23 Jun 99, at 6:17, Brian J. Beesley wrote:
>
> On 22 Jun 99, at 17:38, Gary Diehl wrote:
> > 2. Why use a table at all? Is it faster than doing a calculation to
> > determine if [f % 255255] != 0 ? (I know sometimes tables can speed
> > things up, but does it really help with so few numbers involved in the
> > table?)
Calculating f % 255255 does not tell us if f is divisible by
3, 5, 7, 11, 13 or 17 but only their product. You would want to
test if GCD (f, 255255) > 1.
> On a Pentium, recalculating the index & looking up the table takes of
> the order of 20 clocks (allowing for a cache miss on the table read),
> irrespective of the size of f, whereas just dividing f by 255255 to
> get the remainder costs 39 clocks, even if f/255255 < 2^32.
If f = 2*k*P + 1 is a potential factor of 2^P-1, then we can calculate
s[i] == -(p[i] + 1)/2 (mod p[i]) where p[i] are the primes 3, 5, 7, ...
Then solve the linear congruence P * c[i] == s[i] (mod p[i]) for c[i].
To test if f is divisible by p[i] test if k == c[i] (mod p[i]).
That reduces the dividend from f to k. The division can be done by
multiplication by the reciprocal of p[i], this and c[i] can be
precomputed.
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
