mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Lone Mersenne Hunters

Reply
 
Thread Tools
Old 2006-10-26, 21:41   #1
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

5·701 Posts
Default 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.
jasong is offline   Reply With Quote
Old 2006-10-26, 23:16   #2
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

350510 Posts
Default

correction: it's k=7 plus 1, k=7 minus 1, k=9 minus 1
jasong is offline   Reply With Quote
Old 2006-10-28, 00:33   #3
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

5×701 Posts
Default

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
jasong is offline   Reply With Quote
Old 2006-10-28, 07:36   #4
ValerieVonck
 
ValerieVonck's Avatar
 
Mar 2004
Belgium

15058 Posts
Default

Yes I am testing from 33M?
ValerieVonck is offline   Reply With Quote
Old 2006-10-29, 01:06   #5
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

5·701 Posts
Default

Quote:
Originally Posted by CedricVonck View Post
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
jasong is offline   Reply With Quote
Old 2006-10-29, 01:15   #6
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

5×701 Posts
Default

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.
jasong is offline   Reply With Quote
Old 2006-10-30, 10:10   #7
ValerieVonck
 
ValerieVonck's Avatar
 
Mar 2004
Belgium

33×31 Posts
Default

Quote:
Originally Posted by jasong View Post
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
ValerieVonck is offline   Reply With Quote
Old 2006-10-31, 00:29   #8
Citrix
 
Citrix's Avatar
 
Jun 2003

157510 Posts
Default

Quote:
Originally Posted by jasong View Post
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.
Citrix is offline   Reply With Quote
Old 2006-10-31, 23:52   #9
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

5·701 Posts
Default

Quote:
Originally Posted by Citrix View Post
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.
jasong is offline   Reply With Quote
Old 2006-11-03, 17:12   #10
japelprime
 
japelprime's Avatar
 
"Erling B."
Dec 2005

22×19 Posts
Default

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 ….
japelprime is offline   Reply With Quote
Old 2006-11-03, 18:00   #11
ValerieVonck
 
ValerieVonck's Avatar
 
Mar 2004
Belgium

33·31 Posts
Default

FWIW, I am doing the search from 33.2M to 100M, 3M candidates remaining.
ValerieVonck is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Search of all even-15-digit Aliquot cycles Drdmitry Aliquot Sequences 25 2016-12-16 15:26
Polynomial search for 204-digit cofactor of M1009 fivemack Factoring 45 2012-02-14 08:50
Deep Sieving 10m Digit Candidates lavalamp Open Projects 53 2008-12-01 03:59
Help Sieving 10 Million Digit Candidates lavalamp Riesel Prime Search 26 2008-05-25 08:24
idea about 10 million digit search(possibly dumb) jasong Math 5 2006-06-07 10:39

All times are UTC. The time now is 16:52.

Sun Oct 25 16:52:50 UTC 2020 up 45 days, 14:03, 1 user, load averages: 2.10, 1.94, 1.88

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.