Trial Factoring Sieve?

[wblipp]

Originally Posted by ewmayer

True, but merely examining a given bit for is-equal-to-zero needs about as much time as clearing it, so I don't see an obvious speedup to be had here.

It seems like there should be a way to efficiently avoid remarking the multiples of three, and that should pay off by itself. Done cleverly, it might generalize into avoiding marking of some other primes, too.

Cheesehead and George's remarks implemented simplistically and limited to "3" could be 3 arrays of 1/3 length, of which you only need to keep 2, so they can be longer.

Alternatively, two passes through the array at step size 3q would eliminate the multiples of q that were not already multiples of 3, hitting only 2/3 as many points - is the extra pass more expensive than 50% more marking?

I don't really know - but it seems there really should be an efficiency from algorithmically avoiding the 3's.

William

[Prime95]

Originally Posted by ewmayer

George, what is a typical small-prime limit used by your code, and roughly what fraction of the TF time does it spend in sieve-related operations?

I don't know the limit. It is in the 25000 - 50000 area. The asm code builds its small primes array from a byte array of the distances between successive primes below 64K.

When I optimized the sieve ages ago (probably on a PII or PIII) I inserted a premature end-of-table until I got the best timings. The best timings definitely came well before building a full list of all primes up to 64K.

If I recall correctly, sieving was about 5% of total time.

[jasonp]

If there are many large primes to sieve with, and their average size greatly exceeds the sieve size, then perhaps you can divide the sieve into blocks and drop sieve updates into buckets that are each one block wide. Sieving proceeds in two passes, the first to fill the buckets and the second to move updates from the buckets to the sieve array. When one bucket is processed, the primes in that bucket all scatter to their 'next bucket' individually. Perhaps that could be a cheap way of artificially increasing the sieve size, and would change the balance of where runtime goes.

Of course George already implemented this optimization in Bob Silverman's lattice siever, so if it would help Prime95's trial factoring then he probably would have coded it there too.

'Bucket sorting' is starting to become a reflex with me...

[cheesehead]

Originally Posted by Prime95

Try mod 120 = 3 * 5 * 8. It eliminates sieving for candidates divisible by 3, 5, and 3-or-5 mod 8.

I was beginning to notice that mod 210 seemed not to lead to 16 passes.

Mod 120 with 3-or-5 mod 8 excluded leaves congruence classes 1, 7, 17, 23, 31, 41, 47, 49 and the corresponding reflections above 60, for the 16 total.

[lfm]

Originally Posted by wblipp

The second stage would apply these small primes to an array where the k'th bit represents "2kp+1". One of the first 3 values of "2kp+1" is divisible by 3. Mark that and every 3rd one after it as composite. Likewise for 5, 7, etc.

At the end of the second stage, the remaining "k's" represent values of 2kp+1 that might be prime (they might also be composite with smallest divisor bigger than you tested). Trial divide with these by calculating 2^n mod 2kp+1.

So if the range of k is large, to keep the size of the bitmap manageable, one may have to generate the bitmap in stages? Alternating sieving then power/mod stages? I think this is the idea I was missing.