mersenneforum.org Sieving with NewPGen
 Register FAQ Search Today's Posts Mark Forums Read

 2005-09-27, 08:04 #12 Cruelty     May 2005 2·809 Posts I have randomly chosen 100 consecutive candidates from my 250-300k range and tested each with proth "factor only" mode till ~9T... guess what: no factor has been found Last fiddled with by Cruelty on 2005-09-27 at 08:05
 2005-09-27, 11:13 #13 TTn   D0D16 Posts VBCurtis, Not sure I totally agree, although I do understand your viewpoint, which is valid. Here is what I think you are saying: By leaving in the numbers longer (in one way or another) any factor found by a newpgen k/n pair eliminates candidates larger than the pair. A problem with this in theory, is that p get large by then, and so is no longer as usefull at eliminating more composites. I found this in practice. I do agree that a very large file, has to follow your theory especially with fixed k. Sounds like we need to do a head-to-head comparison on a k/n pair. Not sure how to do this acurately. ? The RMA option on, relies on the same principle, for a different algorithm. This option, favors LLRing sooner, because finding the prime, is what eliminates candidates larger than the pair.
 2005-09-27, 12:15 #14 Flatlander I quite division it     "Chris" Feb 2005 England 31×67 Posts A thought: If you are sieving a large range of n then the LLR time might vary from (say) 2min at the low end to 20min at the high end. Why sieve to 20mins when most candidates will LLR much quicker than that? There must be a sweet-spot between 2min and 20min. Is it sqr(0.5) of the distance between the min and max times? edit :typos Last fiddled with by Flatlander on 2005-09-27 at 12:18
 2005-09-27, 12:42 #15 Flatlander I quite division it     "Chris" Feb 2005 England 31×67 Posts Another thought: (I know 200,000 is a bit low.) Say you have found a promising k and you want to see if it produces primes. Start a sieve from (say) 200,000 to 800,000 and stop it when it hits the 'sweet-spot' time between 200,000 and 300,000. Run LLR from 200,000 to 300,000. If you have finished with that k then stop. If you want to carry on (maybe you found 'lots' of primes), trim the candidates to start from 300,000 and sieve again until it reaches the next sweet-spot between 300,000 and 400,000. Stop and LLR from 300,000 to 400,000. And so on. Last fiddled with by Flatlander on 2005-09-27 at 12:50
 2005-09-27, 13:21 #16 Flatlander I quite division it     "Chris" Feb 2005 England 81D16 Posts 3rd thought! Have a sticky thread on this forum containing donated abandoned sieve files with details of primes found so far (see my 2nd thought.)
2005-09-27, 14:36   #17
Cruelty

May 2005

65216 Posts

Quote:
 Originally Posted by Flatlander Have a sticky thread on this forum containing donated abandoned sieve files with details of primes found so far (see my 2nd thought.)
The idea is OK, however I don't know if anyone is actually missing such a "feature"

 2005-09-27, 15:38 #18 VBCurtis     "Curtis" Feb 2005 Riverside, CA 109316 Posts Flatlander: Your idea of donated sieve files is fine; they are rare enough to possibly be uploaded here, hosted on the server, or at worst we can start a thread with who has what sieve on offer, available for email. Your second idea encompasses both of the main ideas for calculating sieving depth-- sqrt(0.5) of the way from min n to max n is the candidate you want to calculate LLR time on, and stop the entire sieve when sieve time matches that LLR time; you had that idea perfect. Your idea for pausing a sieve to LLR a smaller range is exactly what I was referring to in my post yesterday-- but since the sieve has so little speed penalty for leaving in a range-piece (such as 200-300k on a 200-1M sieve), it is not time-efficient to remove that piece for LLR until the sieve time is about double the "sweet-spot" time for LLRing that range. "Sweet spot" is time to LLR the 70th percentile number in the range, 270k in a 200-300k range for example. The doubling is because sieving speed increases with the square root of n-range, not linearly. Sieving a 10% larger range would take sqrt(1.1)-1 of the time, which is roughly 5% longer.. ergo my new rule of thumb. Summary: Break off pieces for LLR when sieve time is double LLR time, and stop sieving altogether when sieve time is equal to LLR time for the 70th percentile of whatever range is left to sieve. I'm not sure yet if this is most efficient, but it's close.
 2005-09-27, 15:42 #19 VBCurtis     "Curtis" Feb 2005 Riverside, CA 4,243 Posts Shane-- if you do fixed-k sieving, my theory is worthless, and you simply LLR when LLR time is slightly more than sieve time. In that case, your method is most certainly best. -Curtis
 2005-09-27, 16:32 #20 VBCurtis     "Curtis" Feb 2005 Riverside, CA 4,243 Posts Edit last msg: I meant fixed-N , not fixed-k . Fixed-k is what we normally do, while it sounded like RMA does some fixed-N work. -Curtis
 2005-09-27, 18:02 #21 Flatlander I quite division it     "Chris" Feb 2005 England 1000000111012 Posts I'm still trying to understand some of the posts here but here is an adjustment to my sweetspot stuff anyway: I read on another thread that the sweetspot is not sqr(0.5) but I didn't understand that either! http://www.mersenneforum.org/showthread.php?t=577 Wherever the sweetspot is, in my example it is only necessary to seive to 1/6 of the sweetspot for the range 200-300,000, 1/5 for the range 300-400,000 etc. beacause most of the factored/rejected candidates are from ranges that might not be LLRed. For this to work, decide beforehand how far you are definitely going to LLR. Decide after LLRing that far, whether you are going to carry on to the next range etc. Off topic: How long do I get to edit my posts before the button disappears?
 2005-09-27, 18:23 #22 paulunderwood     Sep 2002 Database er0rr 23·3·139 Posts Using the formula ((max^3+min^3)/2)^(1/3) for the range 300k-400k the avererage LLR test is: ((400000^3+300000^3)/2)^(1/3) =357001.8 Time an LLR test at 357k and sieve to that time limit. This is over-simplyfied becuase it does not take into account "FFT breaks" where the timing jumps for an LLR test due to "n" increasing across a new FFT boundary -- we are really dealing with a steady increase in LLR timings. Also it is far, far more efficient to sieve a large a range as possible at once and not to break it into sub-ranges and sieve seperately. Last fiddled with by paulunderwood on 2005-09-27 at 18:32

 Similar Threads Thread Thread Starter Forum Replies Last Post fivemack And now for something completely different 3 2017-05-16 17:55 Cybertronic Factoring 0 2014-03-22 10:07 MooooMoo Riesel Prime Search 16 2008-12-11 11:46 geoff Sierpinski/Riesel Base 5 11 2006-07-10 01:10 jasong Software 18 2005-12-30 20:23

All times are UTC. The time now is 05:51.

Wed Aug 12 05:51:37 UTC 2020 up 26 days, 1:38, 1 user, load averages: 1.32, 1.53, 1.62