Sieving discussion thread

[axn]

Isn't Prime Grid already testing Proth primes with k < some value (10000?) In that case, those can be removed from our sieve, no? Same for RPS.

[Ken_g6]

Yes, but removing K's, particularly at the low end, does practically nothing to speed up the sieve. It might be worth skipping them in LLR, though.

[axn]

Originally Posted by Ken_g6

Yes, but removing K's, particularly at the low end, does practically nothing to speed up the sieve. It might be worth skipping them in LLR, though.

Not a speed issue -- just wanted to point out that we'd be doing redundant work.

[mdettweiler]

I'm trying tpsieve for the first time today, and I noticed that it doesn't start outputting factors to the screen until at least a minute or so (approximately, since I wasn't monitoring it too closely) after the program is first started. Is this some sort of pre-calculation it needs to do but isn't being especially talkative about?

[axn]

Originally Posted by mdettweiler

I'm trying tpsieve for the first time today, and I noticed that it doesn't start outputting factors to the screen until at least a minute or so (approximately, since I wasn't monitoring it too closely) after the program is first started. Is this some sort of pre-calculation it needs to do but isn't being especially talkative about?

Yes. For starters, it needs to load up the sieve file and create a 1GB bitmap. Plus, compute the sieve primes (upto sqrt(Pmax)). I don't know if there are any additional computations.

[mdettweiler]

Originally Posted by axn

Yes. For starters, it needs to load up the sieve file and create a 1GB bitmap. Plus, compute the sieve primes (upto sqrt(Pmax)). I don't know if there are any additional computations.

Ah, I see. I was wondering what that thing with the sieve primes in tpconfig.txt was all about. BTW, that option came pre-set to 10e6 in the file; I'm pretty sure that is NOT sqrt(pmax). Is this supposed to be a better setting for this?

Also, just curious, how exactly does this sieve primes thing work? Does it pre-calculate all the primes up to sqrt(pmax) to begin with, then check the candidates to see which ones are divided out, then calculate the next batch of primes, check those, etc? Or have I got something mixed up here?

[axn]

Originally Posted by mdettweiler

Ah, I see. I was wondering what that thing with the sieve primes in tpconfig.txt was all about. BTW, that option came pre-set to 10e6 in the file; I'm pretty sure that is NOT sqrt(pmax). Is this supposed to be a better setting for this?

I don't know if the program slavishly computes all small primes upto qmax, or intelligently lowers it to sqrt(pmax). Anyway...

Originally Posted by mdettweiler

Also, just curious, how exactly does this sieve primes thing work? Does it pre-calculate all the primes up to sqrt(pmax) to begin with, then check the candidates to see which ones are divided out, then calculate the next batch of primes, check those, etc? Or have I got something mixed up here?

The object is to generate all primes in the range pmin <= p < pmax.I assume tpsieve uses a Sieve of Eratosthenes (sp?) to generate those primes on the fly. For that, you'll use all primes < sqrt(pmax). But if sqrt(pmax) is too big, you can use a lower value (which is where qmax would come into picture) -- but downside is that you may test some composites also.

In summary, there are three sieves.

1. Initial sieve to generate all small primes upto sqrt(pmax). This is done only once per run of the program -- in fact it may not even be a sieve, but brute force trial division (I dont know).
2. Use these small primes to do a secondary sieve to generate the actual sieve primes between pmin and pmax [we specify via -p & -P flags]. These will be generated blocks at a time.
3. Each of these p will then be used to sieve out our twin candidates.

Phew!

[cipher]

Reserving 1100G-1300G [480000-485000] cipher

MoooMoo @ what point can we merge ranges [480000-490000] ? or even get a new file which is smaller to handle, according to my calculation upon completion of 1T we would remove almost 30-35% of factors from the original file thats 180MB smaller file than current 570MB.

I recommend we bring both ranges to 3T and than merge them.

thanks
cipher

[gribozavr]

I have downloaded and verified all submitted factor files.

After sieving to 10G each file with 5000 n's has approximately 39.2 million k's.
Sieving n=480k-485k p=10G-500G has produced 12.3 million factors. That is ~31% of original file.
Sieving n=485k-490k p=10G-200G has produced 9.6 million factors. That is ~24% of original file.

[axn]

Originally Posted by cipher

I recommend we bring both ranges to 3T and than merge them.

Until a hash-based version of tps is out, this will not be feasible -- the bitmap version for the combined range will take 2GB memory to run, regardless of how many factors you remove.

EDIT:- Additionally, there is no net speed gain in merging two ranges.

[mdettweiler]

Originally Posted by MooooMoo

I haven't done many benchmarks yet, so I'm not sure. But it's almost certainly above 50T (50000G), so we're nowhere near the optimal sieve depth yet.

edit: LLR testing will resume before we get to the optimal sieve depth. If we wait too long, any primes found may be too small to get on the top 5000 list.

50T? Hmm...that sounds a little high. For NPLB, we had an optimal depth of 30T for the range of k=2000-3400, n=50K-650K. Obviously TPS's sieve is a completely different type of range, though I would think that, since it's only for 480K-500K (even for a rather large range of k's), the optimal depth would be somewhat lower than that.

Is there any way to get tpsieve to produce an expected # of factors in a given range, a la sr(x)sieve? If we can get that information, calculating optimal depth is a rather straightforward matter.