Thread: Idea for faster sieve View Single Post
2007-07-10, 00:36   #48
geoff

Mar 2003
New Zealand

13·89 Posts

Quote:
 Originally Posted by Citrix Shouldn't we look to see if last_composite is already greater than low_end_of_range or not? Code:  last_composite = (low_end_of_range / max_prime) * max_prime;
That ensures last_composite can't be greater than low_end_of_range.

I think the original sieve works fine when x is a power of 2, say 2^y, because last_composite is odd, and so the inverse of x mod last_composite is always found after at most y additions, and so overflow doesn't have to be checked as long as you don't expect to sieve beyond 2^(64-y).

However I think the prime sieve is not the only problem you face. Sr2sieve doesn't do SPH, it doesn't use the Chinese Remainder Theorem, it just knocks out some congruence classes and sends what remains to BSGS. The fastest part of sr2sieve is the BSGS, most of the rest of the code is not particularly flash. But by sieving with smooth p-1 you end up minimising the time in BSGS, and maximising the time spent in the slow code.

So this is the problem: If you restrict sieving to very smooth p-1 then you get bogged down in the slow code. But if you allow less smooth p-1 then the gains over normal sieving are not going to be great enough to justify the effort.

The solution might seem to be to speed up the slow code, but that means a lot of work in all sorts of different areas that is only going to have a small benefit to the normal sieve.