mersenneforum.org  

Go Back   mersenneforum.org > Other Stuff > Archived Projects > 15k Search

 
 
Thread Tools
Old 2005-09-27, 08:04   #12
Cruelty
 
Cruelty's Avatar
 
May 2005

2·809 Posts
Default

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
Cruelty is offline  
Old 2005-09-27, 11:13   #13
TTn
 

D0D16 Posts
Default

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.
 
Old 2005-09-27, 12:15   #14
Flatlander
I quite division it
 
Flatlander's Avatar
 
"Chris"
Feb 2005
England

31×67 Posts
Default

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
Flatlander is offline  
Old 2005-09-27, 12:42   #15
Flatlander
I quite division it
 
Flatlander's Avatar
 
"Chris"
Feb 2005
England

31×67 Posts
Default

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
Flatlander is offline  
Old 2005-09-27, 13:21   #16
Flatlander
I quite division it
 
Flatlander's Avatar
 
"Chris"
Feb 2005
England

81D16 Posts
Default

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.)
Flatlander is offline  
Old 2005-09-27, 14:36   #17
Cruelty
 
Cruelty's Avatar
 
May 2005

65216 Posts
Default

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"
Cruelty is offline  
Old 2005-09-27, 15:38   #18
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

109316 Posts
Default

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.
VBCurtis is online now  
Old 2005-09-27, 15:42   #19
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

4,243 Posts
Default

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
VBCurtis is online now  
Old 2005-09-27, 16:32   #20
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

4,243 Posts
Default

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
VBCurtis is online now  
Old 2005-09-27, 18:02   #21
Flatlander
I quite division it
 
Flatlander's Avatar
 
"Chris"
Feb 2005
England

1000000111012 Posts
Default

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?
Flatlander is offline  
Old 2005-09-27, 18:23   #22
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

23·3·139 Posts
Default

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
paulunderwood is offline  
 

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Parallel sieving with newpgen fivemack And now for something completely different 3 2017-05-16 17:55
NewPgen Cybertronic Factoring 0 2014-03-22 10:07
Does NewPGen have a bug? MooooMoo Riesel Prime Search 16 2008-12-11 11:46
Faster sieving with NewPGen and srsieve geoff Sierpinski/Riesel Base 5 11 2006-07-10 01:10
Sieving multiple NewPGen files in a row(How?) 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.