mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Reply
 
Thread Tools
Old 2007-12-04, 22:02   #1
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

1101101100012 Posts
Default Newpgen worthwhile for n*2^n+/-1 numbers?

PrimeGrid has finished their sieving and they only got up to about 2^33(a little under 8.6G).

I'm wondering if it would be a good idea to throw newpgen at these numbers? And, if, so, how high should I go? Also, I'm running Linux, and I've heard that newgen can be run commandline under Linux, is that true? I tried a number and it was banging along at about 10G every 1:30(m:s).
jasong is offline   Reply With Quote
Old 2007-12-05, 00:59   #2
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

13×463 Posts
Default

Quote:
Originally Posted by jasong View Post
PrimeGrid has finished their sieving and they only got up to about 2^33(a little under 8.6G).

I'm wondering if it would be a good idea to throw newpgen at these numbers? And, if, so, how high should I go? Also, I'm running Linux, and I've heard that newgen can be run commandline under Linux, is that true? I tried a number and it was banging along at about 10G every 1:30(m:s).
Your thread title and thread text do not belong together. If you have paid any attention to PrimeGrid, you would know that n*2^n+/-1 are known as Cullens and Woodalls. Also, if you have paid any attention to the PrimeGrid message boards you would know that you need to use a combination of MultiSieve and gcwsieve to sieve numbers of this form.

BTW, I also gave Geoff the code so that gcwsieve would not need to rely on MultiSieve for the initial sieving, but AFAIK, he has not implemented it.
rogue is online now   Reply With Quote
Old 2007-12-05, 01:02   #3
axn
 
axn's Avatar
 
Jun 2003

7·683 Posts
Default

NewPGen cannot handle these series. It can do "fixed-n variable-k" or fixed-k variable-n" sieves, but Cullen-Woodalls are "variable-n variable-k" (ok, well n /is/ the k), and so NewPGen can't.

I am aware of only two publicly available programs -- rogue's multisieve and geof's gwcsieve -- that can handle these series. And the latter is being used by PrimeGrid.

EDIT:- Beaten to the post by rogue :)

Last fiddled with by axn on 2007-12-05 at 01:03
axn is offline   Reply With Quote
Old 2007-12-05, 03:01   #4
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

5·701 Posts
Default

I don't think you two considered my post for much longer than it took to skim it. 10G in a minute and a half is nothing to sneeze at, and you'll note that I was informed enough about gcwsieve to know that it had gotten to about 2^33 using PrimeGrid software(I suppose I didn't state that last part straight out, but I think it would be kind of obvious to someone who was knowledgeable of the sieving scene in general, given a little thought)

So, I'll restate my question, which I don't consider answered. Does anyone think it would be worthwhile to take the various numbers individually higher using NewPGen, like say, a bit-level or two. Or, maybe not even a bit level.
jasong is offline   Reply With Quote
Old 2007-12-05, 03:23   #5
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

13×463 Posts
Default

Quote:
Originally Posted by jasong View Post
I don't think you two considered my post for much longer than it took to skim it. 10G in a minute and a half is nothing to sneeze at, and you'll note that I was informed enough about gcwsieve to know that it had gotten to about 2^33 using PrimeGrid software(I suppose I didn't state that last part straight out, but I think it would be kind of obvious to someone who was knowledgeable of the sieving scene in general, given a little thought)

So, I'll restate my question, which I don't consider answered. Does anyone think it would be worthwhile to take the various numbers individually higher using NewPGen, like say, a bit-level or two. Or, maybe not even a bit level.
Are you asking if it is faster to take a specific n and sieve it deeper? The easy answer is "No". There is an economy of scale in doing many n concurrently. By doing fewer n, the factor removal rate goes down considerably. Based upon my knowledge, doubling the sieving depth will give you a 3% chance of finding a factor. If you can quadruple the sieving depth in the same amount of time it takes to do a PRP test, then the PRP test is clearly what you want to do.

BTW, I believe that gcwsieve will be faster than NewPGen for a single n, but only testing that hypothesis will prove it to be correct.
rogue is online now   Reply With Quote
Old 2007-12-05, 03:38   #6
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

5·701 Posts
Default

Ok, thanks for the answer, and sorry for my stiff response. 10G in a minute thirty seemed fast to me and I didn't think that that had been noticed.
jasong is offline   Reply With Quote
Old 2007-12-05, 03:52   #7
axn
 
axn's Avatar
 
Jun 2003

7·683 Posts
Default

Quote:
Originally Posted by jasong View Post
I don't think you two considered my post for much longer than it took to skim it.
Mea culpa. I am so used to thinking NewPGen used for sieving a series that I didn't even register your question.

Quote:
Originally Posted by jasong View Post
So, I'll restate my question, which I don't consider answered. Does anyone think it would be worthwhile to take the various numbers individually higher using NewPGen, like say, a bit-level or two. Or, maybe not even a bit level.
Ok, let's plugin the numbers.

90 seconds to 2^34 - 2.9% chance of factor.
270 seconds to 2^35 - 5.7% chance of factor.
630 seconds to 2^36 - 8.3% chance of factor
1350 seconds to 2^37 - 10.8% chance of factor

Breakeven points (i.e., how long must an LLR test take for these to be worthwhile).

To 2^34: 90 + (1-2.9%)*t = t ==> t = 90/.029 = 3100 sec.
To 2^35: t = 270/.057 = 4700 sec
To 2^36: t = 7500 sec
To 2^37: t = 12500 sec.

So, depending on the t value (LLR test time), you can decide how far you can sieve. NOTE that these are /breakeven/ points -- the optimal sieving point will be somewhat lesser (or alternately, the LLR test time should be greater than what is indicated)

Last fiddled with by axn on 2007-12-05 at 04:02 Reason: added clarification
axn is offline   Reply With Quote
Old 2007-12-05, 04:17   #8
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

48516 Posts
Default

Quote:
Originally Posted by jasong View Post
PrimeGrid has finished their sieving and they only got up to about 2^33(a little under 8.6G).
I don't think this is right, my current manual reservation is 6300G-6400G, much higher than 2^33.

Quote:
I'm wondering if it would be a good idea to throw newpgen at these numbers? And, if, so, how high should I go? Also, I'm running Linux, and I've heard that newgen can be run commandline under Linux, is that true? I tried a number and it was banging along at about 10G every 1:30(m:s).
That is 90sec for one number? You are using NewPGen with a one-line input file?

My 2.88GHz Celeron is sieving about 58,000 numbers for PrimeGrid at the rate of about 46,000 p/sec. That is equivilent to 240G for one number in 90 sec. Unless your machine is 24 times slower than mine, you are wasting your time.
geoff is offline   Reply With Quote
Old 2007-12-05, 04:29   #9
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

5·701 Posts
Default

Thanks for the response, and sorry for the harsh words. I'm positive I've rushed to respond to something I didn't read adequately in the past, I just can't think of anything in particular. In the meantime, I need to Google 'mea culpa' to find out precisely what it means, since I'm only familiar with the context it's used in and not the precise meaning.
jasong is offline   Reply With Quote
Old 2007-12-05, 04:44   #10
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

5×701 Posts
Default

Quote:
Originally Posted by geoff View Post
I don't think this is right, my current manual reservation is 6300G-6400G, much higher than 2^33.



That is 90sec for one number? You are using NewPGen with a one-line input file?

My 2.88GHz Celeron is sieving about 58,000 numbers for PrimeGrid at the rate of about 46,000 p/sec. That is equivilent to 240G for one number in 90 sec. Unless your machine is 24 times slower than mine, you are wasting your time.
Um, Geoff, there's more than one one sieving effort that's been going on at PrimeGrid. Actually, over it's short life, there have been three separate sieving projects for three separate objectives, (1) Cullen/Woodall sieving, which uses gcwsieve, which is the best method, at least for the lower p-values (and this is the project I'm talking about),(2) twin prime search, which involves n=333,333 at the moment, and involved n=195,000 in the past, and (3) what you're involved in, which is the Sierpinski sieve, which helps both the Prime Sierpinski project and the Seventeen or Bust project which have some overlapping and nonoverlapping k's in their initiatives.

Last fiddled with by jasong on 2007-12-05 at 04:47
jasong is offline   Reply With Quote
Old 2007-12-05, 05:14   #11
axn
 
axn's Avatar
 
Jun 2003

7×683 Posts
Default

Quote:
Originally Posted by jasong View Post
Um, Geoff, there's more than one one sieving effort that's been going on at PrimeGrid. Actually, over it's short life, there have been three separate sieving projects for three separate objectives, (1) Cullen/Woodall sieving, which uses gcwsieve, which is the best method, at least for the lower p-values (and this is the project I'm talking about),(2) twin prime search, which involves n=333,333 at the moment, and involved n=195,000 in the past, and (3) what you're involved in, which is the Sierpinski sieve, which helps both the Prime Sierpinski project and the Seventeen or Bust project which have some overlapping and nonoverlapping k's in their initiatives.
LOL. Now you gone done it Sierpinski sieve is running at at least a 1000 times higher values than what geoff said. And I'm pretty sure, considering that geoff wrote 2 out of 3 of those sieve programs that he knows what he's talkin about

Ah, here is the thread in question -- looks like the sieve reservation has reached 2^43.

[PS:- I must be having a really off day -- getting a C/W sieve to 2^33 is like a week's job on a single PC]
axn is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
NewPgen Cybertronic Factoring 0 2014-03-22 10:07
Does NewPGen have a bug? MooooMoo Riesel Prime Search 16 2008-12-11 11:46
NewPGen reliability Cruelty Riesel Prime Search 3 2006-02-15 05:15
NewPGen header. Flatlander 15k Search 1 2005-10-28 01:01
Sieving with NewPGen Cruelty 15k Search 41 2005-10-27 10:28

All times are UTC. The time now is 17:56.

Mon Nov 30 17:56:42 UTC 2020 up 81 days, 15:07, 3 users, load averages: 3.14, 2.15, 1.95

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.