Optimal depth?

[axn]

As a reality check: sieving from 25P to 200P will eliminate roughly 1-ln(25P)/ln(200P) = 5.2% candidates only. So as a rule of thumb, no more than 5% of resource should be spent in sieving.

[Bananaman42]

To make sure I'm understanding this correctly: sieving saves time because it finds factors, making it unnecessary to run the proth test on that number. Also, at this point, sieving is eliminating n faster than proth tests are. The optimal sieve depth is the point at which sieving removes candidates at the same rate as proth tests. Are these statements accurate?

[Joe O]

To make sure I'm understanding this correctly: sieving saves time because it finds factors, making it unnecessary to run the proth test on that number. Also, at this point, sieving is eliminating n faster than proth tests are. The optimal sieve depth is the point at which sieving removes candidates at the same rate as proth tests. Are these statements accurate?

More or less!
Since we are running 2 proth tests on most k n pairs, you could argue that the optimal sieving depth is the point at which sieving removes candidates at half the rate that proth tests do.

[enderak]

This begs a question that's been bugging me the last couple days - is it possible while sieving for a memory or CPU error to remove a (potentially prime) candidate in error?

Is there some sort of built in check that prevents this?

[hhh]

As a reality check: sieving from 25P to 200P will eliminate roughly 1-ln(25P)/ln(200P) = 5.2% candidates only. So as a rule of thumb, no more than 5% of resource should be spent in sieving.

While this is correct, these 5 percent of work should be done before the other 95% of work. So, now, the higher the percentage of work spent on sieving, the better. Later, sieving will be stopped, and LLR togehter with P-1 will be 100% of the work.

This begs a question that's been bugging me the last couple days - is it possible while sieving for a memory or CPU error to remove a (potentially prime) candidate in error?

Is there some sort of built in check that prevents this?

Yes; checking for this is very easy, and is done by the server once factors are submitted.

I havn't looked at P-1 lately but that may be near no longer optimal :couch:

I have. We are near the threshold of efficiency, but Prime95 still agrees to run P-1 when started with

Pfactor=k,2,17M,1,55,1.6,0

Meaning that even at a sieve depth of 2^55, it will be worth. Currently, we are at around 2^54.* . Yet, when sieving will approach 40P or 50P, we will have to reevaluate the question. Later, when firstpass reaches around 22M, P-1 will be effective even if we have sieved to 200P or 300P.

H.

[axn]

While this is correct, these 5 percent of work should be done before the other 95% of work. So, now, the higher the percentage of work spent on sieving, the better. Later, sieving will be stopped, and LLR togehter with P-1 will be 100% of the work.

Only if you plan to test all the k/n pairs being sieved. However, in a project like SoB, where a prime found will eliminate a whole k, this is not true. Here, you're better off putting your resources into PRP:Sieve at 20:1 ratio and be done with it. Here's the reasoning:

Sieving will make the project 5% faster (assuming the current 25P to future 200P, and zero cost of sieving). How else can we make the project 5% faster? Why, putting 5% more resource in the PRP stage, of course. So if you're using more than 5% of resource on sieving, move it to PRP, and it will achieve the same thing.

Admittedly, this is not a thorough analysis of optimality, but it is good enough. People are seriously overestimating the value of sieve, and losing sight of the big picture.

[Joe O]

Admittedly, this is not a thorough analysis of optimality, but it is good enough. People are seriously overestimating the value of sieve, and losing sight of the big picture.

And you are assuming that all the people who sieve could or would PRP. That is not true. There are many who enjoy sieving but do not enjoy the longer PRP units and will not do them.

[hhh]

Only if you plan to test all the k/n pairs being sieved. However, in a project like SoB, where a prime found will eliminate a whole k, this is not true.

Or if you take into account that fact into your calculations of the optimal sieve depth. Which I did. Basically: Even after throwing out of the window tons of factors due to the primes found, we are still better off first sieving to 100P and then starting the PRP tests.

Here, you're better off putting your resources into PRP:Sieve at 20:1 ratio and be done with it. Here's the reasoning:

Sieving will make the project 5% faster (assuming the current 25P to future 200P, and zero cost of sieving). How else can we make the project 5% faster? Why, putting 5% more resource in the PRP stage, of course. So if you're using more than 5% of resource on sieving, move it to PRP, and it will achieve the same thing.

You do not define what you mean by faster. Of course, if you don't sieve, at the beginning you are flying through the ranges faster. Later, you realize that you should perhaps sieve a little. But this work would have saved much of your earlier work if it had been done earlier. This is especially true at the current levels where the primes start to be rare.

Admittedly, this is not a thorough analysis of optimality, but it is good enough. People are seriously overestimating the value of sieve, and losing sight of the big picture.

IMO, people love to start crunching and to find the easy primes without proper preparation.

Anyway, there is no way to start a flamewar on this topic. Our little discussion will have no impact whatsoever on the average behaviour. Primegrid is happily sieving, SoB happily PRPing, I think everything is just fine as it is.

H.

[vjs]

... ... ...

We are probably no where near 5% of the total projects resources spent on sieve. If we have spent 1% of our computational effort thus far on sieve I'd amazed.

[Matt]

... ... ...

We are probably no where near 5% of the total projects resources spent on sieve. If we have spent 1% of our computational effort thus far on sieve I'd amazed.

Are you considering the contribution of PrimeGrid to sieving? They have added a significant boost to the sieve effort. Do we have any figures to compare?

[engracio]

Are you considering the contribution of PrimeGrid to sieving? They have added a significant boost to the sieve effort. Do we have any figures to compare?

Ya vjs, got any figures or is that just your best wag?

I would not consider Primegrid contribution not significant. Individual contribution previous to Primegrid were definitely less than 1% compare to prp individual contributions. Primegrid changes that.