mersenneforum.org Alternative Sieving for 10M digit prime search
 Register FAQ Search Today's Posts Mark Forums Read

 2006-10-26, 21:41 #1 jasong     "Jason Goatcher" Mar 2005 66638 Posts Alternative Sieving for 10M digit prime search Because of interest in my idea for an alternative sieving project for the 10M-digit prime hunt, I'm starting this thread. I'm putting it in LMH because at the moment there are only three of us, and this seemed the best place to come without cluttering the boards with a new forum. Basically, we'll just be doing combined trial-factoring, instead of the Prime95 version. So far there are 3 different factoring efforts going on: k=5 plus 1, k=5 minus 1, and a k=9 minus 1, starting from n=33,000,000 for k=9(I really hope this is a typo or shorthand, because this wouldn't produce a a number with more than 10M digits) If anyone has any additional information, please post. At the moment, I'm headed over to Riesel Sieve to see if it's possible to use JJSieve with this project.
 2006-10-26, 23:16 #2 jasong     "Jason Goatcher" Mar 2005 66638 Posts correction: it's k=7 plus 1, k=7 minus 1, k=9 minus 1
2006-10-28, 00:33   #3
jasong

"Jason Goatcher"
Mar 2005

66638 Posts

Additional information having to do with FFT lengths, gleaned from another thread:
Quote:
 k*2^N+-1 is a good option to find primes with close to 10000000 digits. Before you start sieving, please take a careful look at the fft lengths. They might have quite an impacht on the running time. LLR has the feature, that it can use relatively small (compared to Mersenne) FFT sizs, if the mantissa (k) is small. I did some calculations with a p4 and small mantissas on +1 2^33219281-1 needs a 1792k FFT 3 * 2^N+1 needs 2048k FFT for N = 33219281-37800000 beyond that the FFT size gets larger. for 15 * 2^N+1, a 2048k FFT is enough for N up to 35400000 and for 31 * 2^N+1, a 2048k FFT only reaches up to 34300000 Beyond k=63, you cannot test any 10M digit number with 2048k FFT. It needs a larger one. Conclusion: With horizontal sieving, the sieving is much faster, but you might need larger FFT sizes. Vertical sieving is slower, but the FFT size is smaller. But still the exponent and thus the number of iterations is growing. I hope this information helps you to find the optimal parameters for finding primes. biwema

 2006-10-28, 07:36 #4 ValerieVonck     Mar 2004 Belgium 84310 Posts Yes I am testing from 33M?
2006-10-29, 01:06   #5
jasong

"Jason Goatcher"
Mar 2005

3×7×167 Posts

Quote:
 Originally Posted by CedricVonck Yes I am testing from 33M?
Unless your k is more than about 66,010 digits, the k/n pair won't meet the 10 million digit mark.

Edit: Try n=33,219,281

Last fiddled with by jasong on 2006-10-29 at 01:07

 2006-10-29, 01:15 #6 jasong     "Jason Goatcher" Mar 2005 3×7×167 Posts I've been informed that if we sieve 3^16*2^n+1 the sieve will be faster, because only numbers of the form 32x+1 will have to be checked. If JJSieve automatically makes us of this fact, then I will do a little sieving to start a file and state a goal to be reached for sieving. Probably the same goal as the bit depth the numbers are sieved to with Prime95(could someone please post the bit depth that Prime95 normally uses for these numbers?), although people can check out numbers early. Checked out numbers will continue to be sieved, just in case we(they?) get lucky. I'm asking some questions over at Riesel Sieve in the "General Sieve" forum, if anybody wants to drop in and look.
2006-10-30, 10:10   #7
ValerieVonck

Mar 2004
Belgium

3·281 Posts

Quote:
 Originally Posted by jasong Unless your k is more than about 66,010 digits, the k/n pair won't meet the 10 million digit mark. Edit: Try n=33,219,281
Ok then I will update my sieve file
Note: I am still using NewPGen

2006-10-31, 00:29   #8
Citrix

Jun 2003

5·317 Posts

Quote:
 Originally Posted by jasong I've been informed that if we sieve 3^16*2^n+1 the sieve will be faster, because only numbers of the form 32x+1 will have to be checked. If JJSieve automatically makes us of this fact, then I will do a little sieving to start a file and state a goal to be reached for sieving. Probably the same goal as the bit depth the numbers are sieved to with Prime95(could someone please post the bit depth that Prime95 normally uses for these numbers?), although people can check out numbers early. Checked out numbers will continue to be sieved, just in case we(they?) get lucky. I'm asking some questions over at Riesel Sieve in the "General Sieve" forum, if anybody wants to drop in and look.
I am working on 3^16 currently. Please get in touch, if you decide to sieve 3^16. JJsieve does not work for 3^16. Geoff's sieve is faster.

2006-10-31, 23:52   #9
jasong

"Jason Goatcher"
Mar 2005

DB316 Posts

Quote:
 Originally Posted by Citrix I am working on 3^16 currently. Please get in touch, if you decide to sieve 3^16. JJsieve does not work for 3^16. Geoff's sieve is faster.
Awesome.

I'm going to receive some AMD parts in about a week. Sometime in the week after that they'll be running Linux. Then I'll finally be able to help with this.

 2006-11-03, 17:12 #10 japelprime     "Erling B." Dec 2005 2×32×5 Posts Status: I am sieving for k=7 For k=7, K*b^n+1, n=33219281 - 33259281 (40.000 candidates) Sieve with NPGen up to 1.1 trillion. there is 1996 n's remaining (candidates) For k=7, K*b^n-1, n=33219281 - 33259281 (40.000 candidates) Sieve with NPGen up to 1.2 trillion. there is 840 n's remaining (candidates) I was estimating that sieving up to 1.500 trillion will be the goal here (bit >50 if I am correct) and see what will be left? ...and I will continue sieving ….
 2006-11-03, 18:00 #11 ValerieVonck     Mar 2004 Belgium 3×281 Posts FWIW, I am doing the search from 33.2M to 100M, 3M candidates remaining.

 Similar Threads Thread Thread Starter Forum Replies Last Post Drdmitry Aliquot Sequences 25 2016-12-16 15:26 fivemack Factoring 45 2012-02-14 08:50 lavalamp Open Projects 53 2008-12-01 03:59 lavalamp Riesel Prime Search 26 2008-05-25 08:24 jasong Math 5 2006-06-07 10:39

All times are UTC. The time now is 09:26.

Mon Nov 29 09:26:36 UTC 2021 up 129 days, 3:55, 0 users, load averages: 1.06, 0.94, 1.05