20080104, 16:45  #23  
May 2007
Kansas; USA
13^{2}·61 Posts 
Quote:
It's interesting that you mention ignoring my suggestions on k=5 to go ahead and break off the pieces. I think I remarked that I didn't claim to know the math involved but that we had so many LLRers ready that I thought the timing of when to do so made sense at that point. But I'm sure you were dead on on the efficiency of when to break off the individual pieces. It's just that n=470K4M is such a HUGE range! I had suspected that you had to be doing some sort of marginal analysis. Like in calculus...the 'instantaneous rate of change' so to speak. Now that you mention it, it does make a lot of sense to sieve to 2X (or more) the sieve removal rate vs. LLR rate of the highestn candidate of each breakoff piece. Leaving a small nrange in the sieve adds so little time to the overall sieve time. I did make an assumption here. I assumed the 2X was referring to the highestn candidate of each range not the 70% point of each range. You just referred to the 'LLR time for a range'. Not that it makes much difference but since we're splitting hairs here... Technically, this would mean that I should continue sieving the team drive for Sierp base 16 for n=30K100K just a small amount further (I think). But I am leaving out 8 k's...5 for future individual testing and 3 already reserved, which I had included in the sieve, so it should be very close (I previously thought it was oversieved for the range). Regardless, I shall start it now (it just finished to P=600G) because I think it will help jumpstart the project. Also, if a # of k's go down relatively quickly, it should be sieved more than sufficiently. If you can and have the time, would you be able to send me in a PM (or even post here) your timing results for your tests and how you arrived at them? If not, no big deal. I'm certainly not questioning the tests. But what I think it will do is help me understand how to design such tests myself in the future for different sieving scenarios. You know what you need to do? Create some software with various parameters that will spit out the optimum way to sieve any range for any effort. Although the complexity would be horrendous because you'd have to allow for different speeds of machines sieving vs. LLRing, whether it's a conjectures effort, multiplek sieve, yada, yada, yada... Actually, just creating some software that does the calculation on a very simple singlek sieve (no conjectures effort) for a wide nrange, similar to k=5 at RPS, would be a great start. That would be cool! Gary 

20080105, 01:00  #24 
"Curtis"
Feb 2005
Riverside, CA
3×1,559 Posts 
The short answer:
I have zero coding experience, so will not be attempting any such software. However, I do plan eventually to make my explanations concise enough to function as a recipe for optimal sievedepth. I said "LLR time for a range" assuming the range was relatively small enough that LLR time is constant for the entire range. Since it's a marginal analysis, in principle we're discussing breaking off a *small* piece. Consider a single k/n pair, for instance... we break off ranges to save overhead of manipulating and breaking constantly. In practice, use the average LLR time for the range, which often is the 50% point (unless there is an FFT jump in the middle of the range then to be anally accurate you'd find the 50% point before FFT jump, 50% point of the large FFT, and do a weighted average... yea, right). The 70% number comes from LLR scaling with timesquared, which it does via a linear scaling of iterations and a lumpylinear scaling due to FFT jumps. Within a single FFT size, LLR timings scale linearly. For large ranges with many FFT jumps, we ignore the lumpiness and use 70%. For smaller ranges, it really doesn't matter, since the results will all be so similar. Curtis 
20080105, 02:48  #25  
May 2007
Kansas; USA
13^{2}×61 Posts 
Quote:
This makes perfect sense now. So when breaking off HUGE pieces like I did for the team drive, I SHOULD use the 70% timing point because there are many fftlen jumps from n=25K100K for base 16. (In which case the team drive was definitely sieved far enough and too far for the lower range of n=25K50K.) But if a smaller range such as the small pieces of k=5, then the 50% point makes sense. And by extension... If you went to anal level #2 , you could LLR every n=5K range and average all of those. I actually did that a long time ago after you told me about the 70% rule in order to convince myself that it was an accurate one for a relatively large nrange. And if you went to anal level #3, you could create an automated process that LLR's a single candidate, sieves a very small amount to a new optimum point, LLR's another single candidate, sieves a little again to a new optimum point, etc., etc. such that the overall testing time spent is as little as mathematically possible. I suspect that HUGE projects such as GIMPS or maybe Riesel Sieve or SOB actually do somethiing similar to 'anal level #3'. It's just that they have others do the LLRing while they do the sieving. Do you know anything about how they decide how to sieve those projects? Gary 

20080105, 03:42  #26  
Jun 2003
2^{3}×607 Posts 
Quote:
The other projects  SoB, RS  they're in it for the long haul. So they don't do any breaking off. They just keep on sieving the whole range forever and ever. Maybe once you guys have figured out an optimal sieving/LLR sequence, you can let them know Last fiddled with by axn on 20080105 at 03:42 

20080105, 04:24  #27  
May 2007
Kansas; USA
10100001000101_{2} Posts 
Quote:
The only conclusion that I could draw about GIMPS is that they must have some extremely fast way of trial factoring that is faster than sr1sieve or its equivalent sieving multiple candidates. I always thought that sieving over the largest nrange possible (that you know will be tested) is the most efficient way to go if you're in it for the long run. And on SoB and RS, I strongly suspect that they are constrained by what people volunteer to do. If 25% of the CPU cycles that people volunteer are for sieving, then there will be some way oversieved files out there but you certainly can't 'force' sieving people to primality test if they either can't or have poor machines for doing so (or simply don't want to). Or maybe it's the reverse...perhaps only 12% of CPU cycles are volunteered for sieving and hence the files aren't sieved quite far enough. But I'm guessing that the people who run the projects 'enourage' people to go one way or another depending on whether they think the files need to be sieved more or less for current testing. All three are amazing and outstanding efforts but don't quite fit my primesearching tolerance. I'd go nuts waiting for months or years between primes (or never)! Gary 

20080105, 05:42  #28 
Mar 2006
Germany
2×1,439 Posts 
Mersenne numbers M(p) can only have factors of the form 2*k*p+1, k > 0 and M(p) can only be prime if p is prime, so the conditions are slightly different and very effective in 'sieving' or better trial factoring.

20080105, 05:44  #29  
A Sunny Moo
Aug 2007
USA (GMT5)
6249_{10} Posts 
Quote:
Quote:
As for SOB, I've never crunched for them, so I don't know the details about them, but from the looks of it they've struck a good balancethe majority of the project's running primality testing (they use their own software, which does Proth tests like LLR does for k*2^n+1 numbers), but there's also some considerable power being thrown on sieving, especially since with them doing their sieving combined with PSP, PSP's collaboration with PrimeGrid affects SOB too. So, I'd say that, as an outsider, they seem to have a pretty good balance between sieving and primality testing. (I don't know any percentage figures, though, like you were discussing.) FYI, the PSP/SOB combined dat goes up to 50M, so the depth at which they will have sieved the whole dat file optimally will definitely be much higher than for Riesel Sieve. 

20080105, 19:04  #30  
"Curtis"
Feb 2005
Riverside, CA
3·1,559 Posts 
Quote:
The *fast* trialfactoring in that project is due to only iterating over the kvalue in the formula above. For p in the 30 million range, you only have to trialdivide by 1 number every 60+ million! That's how they get factor depths up near 70 bits (10^21). Finally, for a search like this project's, we need at some point to take doublechecks into account. I don't know how to estimate the chance of error on a single test, but let's say it's 1/1000. When a firsttime test takes ~50 times longer than a doublecheck range, there is a higher chance to find a prime per time expended via doublecheck versus firsttime testing. However, this is mitigated by firsttime testing being well into top5000 range by then, so minimizing project length is not the only priority. I'll hit upon this again once you folks are up in the 300500k range for n's. Curtis 

20080105, 23:18  #31  
A Sunny Moo
Aug 2007
USA (GMT5)
1869_{16} Posts 
Quote:


20080106, 00:26  #32  
May 2007
Kansas; USA
13^{2}×61 Posts 
Quote:
Yes, we'll have to talk about double checks when we get up a little higher. Every conjectures project at some point has to do double checks on stubborn k's. This is why I'm asking everyone for results files. Gary 

20080122, 03:09  #33 
May 2007
Kansas; USA
10309_{10} Posts 
More sieved files available for singlek searching
Anon posted sieved files for Sierp base 6 for k=154797, 157473, and 166753 for n=30K100K in a thread here. There is now a link to them on the Sierp base 6 reservations page.
I have also posted links to files on the Sierp base 16 reservations page for k=2908, 6663, and 10183 for n=100K200K. The Sierp base 16 files were run in conjuntion with team drive #1, which now has links in that thread for files up to n=120K. I will add them up to n=200K as ranges are completed. Gary 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Coordination thread for redoing P1 factoring  ixfd64  Lone Mersenne Hunters  80  20210119 17:17 
Another sieving gap in Psieve files  Batalov  Riesel Prime Search  38  20140314 02:59 
Sieving reservations and coordination  gd_barnes  No Prime Left Behind  2  20080216 03:28 
Offer your sieved files here  kar_bon  Riesel Prime Search  8  20080108 04:52 
Sieving multiple NewPGen files in a row(How?)  jasong  Software  18  20051230 20:23 