Am I unlucky, or are we close to Optimal Sieve depth?

[wolfemancs]

So I've been running PSP Sieve on PrimeGrid for the last month or so and I've found 9 factors in 4131 workunits for an average of 1 in every 459 WU.

Does anyone know what the PrimeGrid overall average has been for the last month or so? And does anyone know how long the current batch of SoB workunits are taking on an Athlon 64 3000+?

Here's my rough attempt at a calculation for whether I should be sieving or prime testing based off readings in the sieve forum.

Last time I was running Prime95 my computer was crunching through about 6%/day, so 1 Prime Test was taking about 16 2/3 days. So now to see if I'm being more useful sieving:

(1 Sieve WU/36.6666 min)(60 min/hr)(24 hr/day)(16.6666 days/Sob WU) = 654.5 Sieve WU / Sob WU

Assuming factors found are evenly distributed between SoB and PSP, only 6/15 or 40% of the factors found will be SoB factors, so:
654.5*.4 = 261.8 SoB Useful Sieve WU/ SoB WU

But since a factor for an untested n cancels 2 WU, and 1 WU if it's been tested and not double checked, but doesn't count for anything if we find a prime for the k before we would have reached that n, we need some sort of multiplier on the value of factors, and I think I've seen Louie use about 1.7, which makes sense to me, so:
261.8 * 1.7 = 445 Equivalent SoB Useful Sieve WU / Sob WU

So for my specific computer if I can find a factor ever 445 sieve WU, I think I'm breaking even on whether I should be running the sieve or working on SoB WU. Obviously this ignores the fact that as a byproduct of running the sieve at an SoB break even point, I'm helping the PSP project at the same time, so even if it's a little worse for SoB for me to sieve, I'm helping the set of Sierpinski problems more by sieving . . .


So, CLIFFS NOTES VERSION: Am I just unlucky and haven't been finding as many factors as I should have been running PSP Sieve on PrimeGrid, or are we pretty close to the optimal Sieve depth for my particular computer (1 factor in 445 WU is "optimal" and I'm finding 1 factor ever 459 WU)?

[enderak]

Well... when I ran PSP Sieve for a while back in Jan/Feb 2009, I found 109 factors in about 20,200 work units (185 WU / factor).

During the last week's Primegrid challenge, I think I did 726 WU (give or take) and only found 1 factor. Clearly this isn't a big enough sample to get a good average, but it matches up with your calculation of 459 WU/factor. It is definitely less factor density than it was 10 months ago.

On the Primegrid message board post for last week's challenge, they state "over 300" factors found in "over 191K" WU's. Not sure how far over they mean, but 191K/300 is 636 WU/factor.

In contrast, the PSP Sieve challenge back in April 2009 had 1500 factors in 389K WU, for about 260 WU/factor.

So yes, it seems like the density is going down, and going down FAST!

[Matt]

I've noticed that there do seem to be a lot less factors being found during sieving, I've switched to running Prime95 on my main cruncher.

On my primegrid account page it says I have found 184 factors in 35,729 completed tasks, that's 194 WU / factor, bearing in mind I have crunched less tasks recently so this might be a slightly historic figure but it gives you an idea.

Would be nice if we could get a monthly breakdown of work done vs factors found, surely this information must be available from primegrid?

Or even (as suggested by opyrt) a breakdown of factors found per 100T. Perhaps the graphs that Joe O produces will show us whether the cloud of factors is becoming less dense?

[opyrt]

Just one thing that came to mind... As there is no speed gain from running LLR in a 64 bit environment, but a 1.5 times speed gain with sieve, won't there be two different "optimal sieve depths"?

If I'm thinking about this correctly, it could be that 64 bit computers would still remove more candidates by sieving than LLRing.

[wolfemancs]

These numbers are from running the LLR in a 32-bit environment, and Sieving in a 64-bit environment. If I was running pure 32-bit, I think it would be even worse.

CW
Edit:
From PrimeGrid Forums:

John:
49P-50P 969 factors
50P-51P 936 factors
51P-52P 930 factors
52P-53P 923 factors
53P-54P 875 factors
54P-55P 862 factors
55P-56P 865 factors
56P-57P 875 factors
incomplete ranges below
57P-58P 827 factors
58P-59P 863 factors

1 WU = 3G

So if one WU is 3G, that means there's 333,333 WU per P, so even if the 57P-58P range was complete (Only 45 UW left in progress) that'd still be 333,333/827 = 403 WU / Factor which still falls within my optimal to be sieving while still being selfish for SoB range. But if we drop below about 750 factors/1P range, then we'll be much closer to my estimate. If you want to see how many factors each of the last couple ranges done by primegrid have found (and how many the in progress ones have found) try http://www.primegrid.com/stats_psp_sieve.php

[ltd]

Here are some numbers from the PSP transfer tables:

These are for the range of 1P from 57p-58p which is nearly complete at primegrid (only 45 WU open)

SOB Results:
339 factors found total
101 factors are lower then 14M (probably no test removed)
14 factors between 14M and 17M most likely removing 1 test
224 tests above 17M most likely removing 2 tests

PSP results:

465 factors found total
16 factors below 1.7M removing no test
50 between 1.7M and 8M around ~70% chance to remove 1 test
399 above 8M most likely removing 2 tests

[wolfemancs]

Here are some numbers from the PSP transfer tables:

These are for the range of 1P from 57p-58p which is nearly complete at primegrid (only 45 WU open)

SOB Results:
339 factors found total
101 factors are lower then 14M (probably no test removed)
14 factors between 14M and 17M most likely removing 1 test
224 tests above 17M most likely removing 2 tests

PSP results:

465 factors found total
16 factors below 1.7M removing no test
50 between 1.7M and 8M around ~70% chance to remove 1 test
399 above 8M most likely removing 2 tests

Interesting. Even though this is just one sample (is there a place where we can see these results for the last 10 or so sets of 1P results?) assuming the ratios are the same, and scaling up from 827 factors to 969 which is the most we've had recently, we'd have:

SOB Results:
397 factors found total
118 factors are lower then 14M (probably no test removed)
16 factors between 14M and 17M most likely removing 1 test
263 tests above 17M most likely removing 2 tests

PSP results:

545 factors found total
19 factors below 1.7M removing no test
59 between 1.7M and 8M around ~70% chance to remove 1 test
467 above 8M most likely removing 2 tests

So again for my Athlon 64 3000+, running 333,333 PSP_sieve tasks would take (333,333 WU)(2,200 sec/WU)(1 hr/3600 sec)(1 day/24 hr) = 8,487.64 days, and I'd remove 263*2+16 = 542 tasks.

To LLR those 542 tasks in the same amount of time I would have to run a WU in 8,487.64/542 = 15.66 days.

With the numbers ltd put up, I'd have the same 8,487.64 days sieving, but only eliminate 462 tasks, which would put my LLR rate at 1 WU per 18.37 days.

The last WU I ran LLR for was in the n=16.8M range, and it took me about 16.66 days. So assuming the n=17.3M LLR tests aren't taking too much more time, I seem to be hovering right there around the break even point as to which is more useful to SoB.

I guess since Sieving also produces results for PSP at the same time that wouldn't be generated by working SoB LLRs I'll focus most of my time on Sieving still.

Interesting exercise though. Thanks for all the data everyone,
CW

[ltd]

Sorry there is no way at the moment to look at these numbers directly.
I made some manual SQL queries to analyse the range.

Second thing I wanted to say is that we also should keep in mind that sooner or later there will be the changeover to the next FFT. And when that happens there will be a significant increase in LLR runtime which will make sieving even more valuable.

[MikeH]

This doesn't really answer the question, but here's a few more stats (all relate to SoB alone).

In 2009, sieving has found about 430 factors per million N. For 2008, that same number was about 1100, 2007 was 160, 2006 was 160. Note the massive difference that PrimeGrid has made!

That 430 factors per million N represents almost 3% of all remaining factors - that sounds like a very worthwhile effort to me.:thumbs:

At the beginning of the year, the sieve point was at about 21P, it is now at 62P. A doubling of the sieve point will result in slightly less than half the factor density. So you should realistically expect to find little more than 25% of what you were finding at the start of the year.

Number of first pass PRP tests saved as a direct result of sieveing/factoring in 2009: 682

These numbers all still sound very healthy to me. Keep up the good work sievers!
Cheers,
Mike.

http://www.henleyclan.co.uk/sobsieve/2009/scores_p.htm
http://www.henleyclan.co.uk/sobsieve/2008/scores_p.htm
http://www.henleyclan.co.uk/sobsieve/2007/scores_p.htm