mersenneforum.org  

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

 
 
Thread Tools
Old 2005-09-24, 15:14   #1
Cruelty
 
Cruelty's Avatar
 
May 2005

2·809 Posts
Unhappy Sieving with NewPGen

I have been working on my k=736320585 for some time, I am now LLR'ing both 250-300k and 300-350k ranges of "n". The problem I have is the number of candidates per every 50k range of "n" - I have sieved both ranges till 1T and I still have ~7900 candidates per every range which is a lot compared to what others report on this forum... any hints on what I may be doing wrong?
Cruelty is offline  
Old 2005-09-24, 17:56   #2
Citrix
 
Citrix's Avatar
 
Jun 2003

22·383 Posts
Default

Try sieving from scratch and see if you get the same number of candidates. Other than that if you post the first few lines of the file, we can look into it.
Citrix is offline  
Old 2005-09-24, 19:09   #3
Flatlander
I quite division it
 
Flatlander's Avatar
 
"Chris"
Feb 2005
England

207710 Posts
Default

Assuming you have chosen k.b^n-1 with k fixed in NewPGen:

My testing of various 'k's (between 1000 and 20000) up to an n of 40000 indicates that a higher number of 'n's left after sieving probably means there will be more primes produced.

I suppose it is reasonable to assume this holds for higher n and larger k?

I don't think you are doing anything wrong. I have never had to sieve passed 500-600 billion. Your larger amount of 'n's left suggest to me the possibility of more primes than I have been finding at those ranges. But, of course, it will take you longer to test all those 'n's !

I only ever sieve to the level suggested in the instructions for NewPGen.

Happy hunting!

(Not my use ofthe words ''probably', 'suggest' and 'possibility' ! )
Flatlander is offline  
Old 2005-09-24, 20:32   #4
Cruelty
 
Cruelty's Avatar
 
May 2005

2×809 Posts
Default

Quote:
Originally Posted by Citrix
Try sieving from scratch and see if you get the same number of candidates. Other than that if you post the first few lines of the file, we can look into it.
Here is the beginning of NewPGen result file:
Quote:
1002680287792:M:0:2:258
736320585 300002
736320585 300012
736320585 300018
736320585 300020
736320585 300029
736320585 300032
736320585 300039
As for sieving the range again from the beginning - is it possible that NewPGen will return different results each time I run it?
Cruelty is offline  
Old 2005-09-24, 20:40   #5
Templus
 
Templus's Avatar
 
Jun 2004

2×53 Posts
Default

This k you are testing is a quite heavy one! For k*2^n+/-1, each choice for k has a certain weight, or: the numbers that remain after sieving.

Resieving will not help: sieving is the process to determine which numbers are divisible by a certain numer (in NewPGen, this is 'p'). So all values for 'n' that are divisible by a number 'p', will also be divisible by that same value for 'p' the next time.

As I see it: you (by accident) chose a k that has a very large weight, so non-primes are not easily detected by sieving. I recommend you to stop sieving.

If I am mistaken, please correct me!
Templus is offline  
Old 2005-09-24, 20:44   #6
Cruelty
 
Cruelty's Avatar
 
May 2005

31228 Posts
Default

Quote:
Originally Posted by Flatlander
I have never had to sieve passed 500-600 billion. Your larger amount of 'n's left suggest to me the possibility of more primes than I have been finding at those ranges.
I have sieved a little bit more than I should based on the LLR/NewPGen break-even point - according to my test it should be 8'25" for n=350000, and I sieved until ~9'30".
Same applies to 200-250k and 250-300k ranges - in first range I have found zero primes (the number of candidates was ~8000), in second range I am currently at ~269k and still no primes
So I guess it's just my luck to pick such a "nasty" k...
Cruelty is offline  
Old 2005-09-24, 20:52   #7
Cruelty
 
Cruelty's Avatar
 
May 2005

2×809 Posts
Default

Quote:
Originally Posted by Templus
As I see it: you (by accident) chose a k that has a very large weight, so non-primes are not easily detected by sieving. I recommend you to stop sieving.
I am stubborn and I will get this k till 1M... eventually
Cruelty is offline  
Old 2005-09-24, 23:06   #8
TTn
 

5,807 Posts
Post

Why not use RMA.NET? It does the work for you, with less waste.

If you sieve to a p bound, you will most likely:
A. Over sieve and waste cycles.
B. Under sieve and waste cycles.

The quickest, and most acurate way to do this is to, sieve until the rate at which Newpgen is throwing out compostites, is equal to the rate at which LLR can perform a primality test on the numbers.
Hence no Over/Under sieving.

Other distributed projects can also have this problem, although in general they save time by, pre-sieving files on machines that are good at sieving.
If both stategies were used in combination, optimal CPU time can be achieved.

Last fiddled with by TTn on 2005-09-24 at 23:08
 
Old 2005-09-26, 08:49   #9
Kosmaj
 
Kosmaj's Avatar
 
Nov 2003

362210 Posts
Default

7900 candidates per 50k range of n is not a lot! That's usual for this kind of numbers. Have a look at the thread for k=2995125705, the average is about 150 per a 1000 range of k, which means 7500 per 50k, that's only 400 less than your case (because it is sieved to 18T). So just keep on going.

OTOH, some k's have large gaps (in terms on n) between primes. If you want you can stop this one and select another k.

Quote:
Originally Posted by Cruelty
I have been working on my k=736320585 for some time, I am now LLR'ing both 250-300k and 300-350k ranges of "n". The problem I have is the number of candidates per every 50k range of "n" - I have sieved both ranges till 1T and I still have ~7900 candidates per every range which is a lot compared to what others report on this forum... any hints on what I may be doing wrong?
Kosmaj is offline  
Old 2005-09-26, 15:36   #10
fatphil
 
fatphil's Avatar
 
May 2003

3·7·11 Posts
Default

Quote:
Originally Posted by Templus
This k you are testing is a quite heavy one! For k*2^n+/-1, each choice for k has a certain weight, or: the numbers that remain after sieving.

Resieving will not help: sieving is the process to determine which numbers are divisible by a certain numer (in NewPGen, this is 'p'). So all values for 'n' that are divisible by a number 'p', will also be divisible by that same value for 'p' the next time.

As I see it: you (by accident) chose a k that has a very large weight, so non-primes are not easily detected by sieving. I recommend you to stop sieving.

If I am mistaken, please correct me!
Roughly speaking, ks with high weight prefer to be sieved more deeply. This is because the each new prime you sieve with is more likely to remove a remaining candidate compared to a k where small primes have already removed a large proportion of the candidates. This implies that candidate removal times will tend to stay higher with heavy k, and so you'll stop sieving later, and so get a marginally better prime/test ratio from the testing phase.

Phil
fatphil is offline  
Old 2005-09-26, 17:06   #11
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

101178 Posts
Default

When planning to run LLR to a very high value (on a high-weight k, 1M is very high), I find that maximum efficiency is produced by breaking a "chunk" off for LLR when the sieve time is a little less than double the LLR test for that exponent. This is not traditional wisdom, because sieve time per p-value does not scale linearly with range to be sieved-- it scales with the square root of range, so it's more efficient to leave n-values in than it first seems. Since you're planning to run to 1M eventually, I'd sieve 300k-350k until sieve time is quite a bit longer than LLR time-- if LLR is 8 min, I'd go 12 to 14 min on the sieve before breaking those off. This adds sieve time up front, but reduces LLR time at least as much.

Shane-- you say RMA automates this. Does it take this effect into account? Your reply sounds like it breaks off a power when LLR time is equal to sieve time-- this is not as efficient as it could be. Comments?
-Curtis
VBCurtis 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 08:23.

Thu May 28 08:23:54 UTC 2020 up 64 days, 5:56, 1 user, load averages: 2.03, 1.93, 1.90

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.