On 22 Jun 99, at 17:38, Gary Diehl wrote:
>
> 1. Why only put the first six prime numbers in the sieve table? (Don't
> you want to eliminate other prime numbers too, or am I missing a bigger
> issue here?)
For a 1-pass sieve table, the table size is the product of the
numbers you're sieving out. 3 * 5 * 7 * 11 * 13 * 17 = 255255, which
seems a reasonable table size, whereas 19 times that size is getting
a bit large, and 19 * 23 times that size is too damn big to fit in
memory on (most) current PC systems.
Each extra prime sieved for eliminates 1/pth of the remaining
candidate factors. So, as p gets bigger, the "gain" gets
progressively smaller, whilst the "pain" involved increases.
Eventually you arrive at a balance.
Whilst keeping memory requirements reasonable, we could build a
second stage sieve to eliminate the primes 19, 23, 29 & 31 in a
second table of size 392863. Doing this would eliminate about 15% of
the candidates remaining from the first pass, whereas the first pass
eliminates about 64%. Apart from the memory cost, we'd also need to
keep track of 2kp+1 (mod 392863) as well as of 2kp+1 (mod 255255). If
this takes more than 1/6th of the time to do the trial division, it's
not worth it. (Actually it almost certainly _is_ worth it - though a
third stage would be of dubious value. I was trying to illustrate the
sieving procedure without complicating things too much.)
>
> 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?)
>
I know the factors I'm looking at are of the form 2kp+1. So, if I
have a candidate factor f and I know x = f (mod 255255), I can
generate the next index into the table by adding 2p (mod 255255) to x
and taking the modulus again. Note that 2p (mod 255255) is fixed so I
only need to calculate this once. And, because x < 255255 and 2p (mod
255255) < 255255, x + 2p (mod 255255) < 2 * 255255, so all I need to
do to reduce to mod 255255 again is to subtract 255255 if the result
is >= 255255. This is a lot quicker than doing the modulus operation
again (which has an implied division - and don't forget that f is
usually bigger than the word size, so you're straight into multi-
precision arithmetic - whereas the index manipulation fits easily
into a 32 bit word).
Once you have the index, the table lookup is essentially
instantaneous.
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.
> I guess i'm still kinda clueless as to why LL factoring is done this
> way.
>
As usual, there's more than one way to skin the cat. The method I've
outlined seems to be reasonably quick. If you can find a faster way,
tell us about it!
Regards
Brian Beesley
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
