mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > Riesel Prime Search

View Poll Results: Will you help me sieve these 10m digit candidates?
Yes, definately! 0 0%
Maybe... 5 41.67%
No. 5 41.67%
No, and I'm willing you to die with hate rays. 2 16.67%
Voters: 12. You may not vote on this poll

Reply
 
Thread Tools
Old 2008-05-15, 19:58   #1
lavalamp
 
lavalamp's Avatar
 
Oct 2007
Manchester, UK

2×3×227 Posts
Default Help Sieving 10 Million Digit Candidates

Hey everyone, apologies if this is the wrong forum but I was wondering how many people would be interested in helping to sieve some 10 million digit candidates?

The candidate range I'm sieving is:
k = 27 for 33,219,273 <= n <= 33,554,432

The aim of the project is to make available a relatively large number of candidates that have been sieved very deeply (though not as deeply as GIMPS).

Currently there are just under 15,000 candidates remaining, and the sieve is still removing candidates quite frequently. I need help to sieve the candidates to at least 1 quadrillion (~ 2^50), 2 quadrillion would be nice (~ 2^51), and 4 quadrillion would be perfect (~ 2^52).

I've been sieving for some time by myself and I'm at 150 trillion now (a bit past 2^47), with other people helping on the forum I hope the sieving could be sped up significantly.

I've been sieving on a Core 2 Duo E6600 and an AMD Athlon 3200+. The Athlon XP can sieve 1 trillion in 3 days, and each core of the E6600 can sieve 1 T in 2 days. It would take me another 21 months to get to 1 quadrillion by myself.

If you're not convinced yet, here are some facts:
  • For the range of n searched for k=27 so far, almost twice as many primes have been found than for k=1 (Mersenne) in the same range. (60 primes for k=27 and n<1.25 million, 34 for Mersennes, and only 44 in total for Mersennes).
  • All of the candidates in the sieve for k=27 will take less time to test than any of the available candidates in GIMPS.
  • The probability that any candidate is prime is roughly 1 in 350,000 (I think), which is in the same ballpark as the GIMPS candidates.
If there is some interest in this then I'll create another thread to keep track of the ranges people are sieving, so please vote in the poll.
lavalamp is offline   Reply With Quote
Old 2008-05-15, 22:02   #2
masser
 
masser's Avatar
 
Jul 2003
Behind BB

25×5×11 Posts
Default

Quote:
Originally Posted by lavalamp View Post

If you're not convinced yet, here are some facts:
  • For the range of n searched for k=27 so far, almost twice as many primes have been found than for k=1 (Mersenne) in the same range. (60 primes for k=27 and n<1.25 million, 34 for Mersennes, and only 44 in total for Mersennes).
  • All of the candidates in the sieve for k=27 will take less time to test than any of the available candidates in GIMPS.
  • The probability that any candidate is prime is roughly 1 in 350,000 (I think), which is in the same ballpark as the GIMPS candidates.
If there is some interest in this then I'll create another thread to keep track of the ranges people are sieving, so please vote in the poll.
Given that you have sieved up to p=1.5*10^14, and you are interested in testing n>33200000, the probability (heuristically) that a candidate is prime will be roughly 1 in 400,000. Given that you only have 15000 tests remaining, that is only a 1 in 26 chance that you will find a prime in that range.

Do you really want to ask people to help you in a project 1) that will require A LOT of computational time and 2) with such a high chance of failure?

just food for thought....
masser is offline   Reply With Quote
Old 2008-05-16, 00:20   #3
Kosmaj
 
Kosmaj's Avatar
 
Nov 2003

2×1,811 Posts
Default

There was already a similar project to sieve k=3, 5, and some other small Ks at n=33M aiming at a 10M-digit prime but I don't know what happened to it. Most likely people lost interest as nobody was willing to dedicate machines to run LLR long enough (meaning 3-6 months).

Therefore, what's most important for your project IMO is not the sieving depth but willingness to dedicate machines to run LLR.

The next most important thing is the selection of k and n. After k=1 (Mersennes) the next "best" K to try is k=3 followed by 5, 7 and so on because they require smaller FFT lengths (meaning faster LLR exe times) than larger Ks. And the range of n has to be large enough so that chances of finding a prime are reasonable. In case of k=27 I'm afraid your range only 340k wide is too small. Why? Because k=27 already has a gap between primes larger than 300k at n=1M. Here is the list of all k=27 primes with more than 100k digits:
340682, 444622, 627794, 729314, 777992, 1108214, 1163629

There are about 300 candidates below n=1.1M still untested but the gap after 777992 more than 320k wide will most likely remain. And at n=30M you can expect much larger gaps.

So I think it's the best to reconsider your selection of k and n. If you want to stick with k=27 I'd suggest a range of n going at least to 40M.
Kosmaj is offline   Reply With Quote
Old 2008-05-16, 01:02   #4
lavalamp
 
lavalamp's Avatar
 
Oct 2007
Manchester, UK

25228 Posts
Default

masser, using the same method that Prime95 uses to calculate odds, and assuming that the sieve will proceed until only 2^50, and working with the largest exponant remaining in the sieve 33554422, I calculate the odds to be:

( 33,554,422 + log_2(27) ) / 2 = 16,777,213.377

50 / 16,777,213.377 = 1 in 335,544 that any single candidate is prime.

Alternately, based on an average density of primes log(exponant), I come to the expected figure of 1/23.3 primes in the range, and assuming 14,000 candidates left after sieving (I think this is a high estimate), that would put the chance any individual candidate is prime at 1 in 319,150.

So yes, there is a high chance of failure for this particular range, I guess in that case we would do what GIMPS do and move on to a higher range. Individually speaking though, the odds are very similar to (if not a little better than) the odds of finding a prime with GIMPS.

It is very likely that the first known 10 million digit prime will be found as part of GIMPS, but wouldn't it be something if it wasn't? And even if the first is a Mersenne, to see a non-Mersenne prime slot in a number 2 would be a nice break from tradition.

Some people just like to find primes full stop, so they stick to the smaller exponants, some people like to find large primes so they may search among numbers with over a million digits, and some people like to search for staggeringly HUGE primes with over 10 million digits, knowing that the odds against finding them are exceedingly slim. This project would be for people in that last group.

Kosmaj, I agree that the range is quite small, and so the odds are against there being a prime within it. In fact I think that there is a 4.29% chance of finding a prime in this range. However, in order to keep the sieve reasonably fast, I chose a smaller range. Despite the small range though, there are still a lot of candidates to test, so even with a lot of interest it will take a long time to crunch through all of the exponants.

If there is enough of an effort made with LLRing to get through all of those candidates, then there will be far and away enough participants to sieve a much larger range for further testing.

As far as the choice of k, I have already done a quick test of iteration times. For k=3 I had an iteration time of 48.7ms, and for k=27 I had a time of 48.9ms, a 0.41% increase. Even on the largest exponant in the range, that would only make a 1hour 40min difference in run time. I did the test on a Core 2 Duo E6600, on which a test would take 19 days.

Last fiddled with by lavalamp on 2008-05-16 at 01:05
lavalamp is offline   Reply With Quote
Old 2008-05-16, 15:50   #5
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

2·17·149 Posts
Default

Lava-
Run times for k=3 vs k=27 will be identical for some values of n, and quite a bit different for other values of n, as the FFT-length jumps up at lower n for larger k's. You tested k=3 vs k=27, and learned you are in a "lucky" range where they are identical.

However, if you do ever expand to a larger n-range with a larger chance to find a prime, kosmaj's advice becomes more relevant. Perhaps it's worth learning what n has a jump in FFT length (thus iteration time)? I imagine the jump will be 15% or more. If that happens 500k sooner for k=27 than k=3, that band of exponents "wastes" 15% of LLR time compared to selecting k=3.

In short, your current project is equally good on 27 as 3. Happy hunting!
-Curtis
VBCurtis is offline   Reply With Quote
Old 2008-05-16, 18:42   #6
lavalamp
 
lavalamp's Avatar
 
Oct 2007
Manchester, UK

2·3·227 Posts
Default

I took your advice and investigated where the next increase is. For k=3 and k=27 over the entire range I'm sieving, the FFT length is 2^21. The FFT length stays the same all the way up to n=34,514,134 for k=27 and up to n=37,838,044 for k=3.

So if and when the first batch of candidates are all sieved and LLRed, perhaps 27 and a couple of other small ks that sieve well could be searched up to their next FFT length jump. This would be the most efficient way to find 10m digit primes aside from the Mersennes.
lavalamp is offline   Reply With Quote
Old 2008-05-17, 13:58   #7
biwema
 
biwema's Avatar
 
Mar 2004

1011111012 Posts
Default

I recommend sieving a rectangular area like k=3-49 for a smaller area of n with k*2^n+1 and k*2^n-1 together.

This reduces the performance disadvantage of vertical sieving. Note that the k range cannot be too large depending on the chosen n range in order to prevent larger FFT sizes.

See older discussion at:
http://www.mersenneforum.org/showthread.php?t=6449
and
http://www.mersenneforum.org/showthread.php?t=5959

Are there any improved implementations for the Generalized fermat number search (after Proth) that are optimized for the newer computer architecteres (at least SSE2)?
biwema is offline   Reply With Quote
Old 2008-05-17, 15:18   #8
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

506610 Posts
Default

as far as I know, sr2sieve does not sieve both riesel and proth numbers together. I believe using an older program to achieve this costs more than it gains.

since such a sieve would run for CPU-years, it would pay to build a 20-k narrow sieve and a 1-k wide sieve and see which is faster for a given number of candidates (not faster speed, but faster p-removal).

If sieve resources are limited, it may make sense to pick a number of candidates for which you are willing to sieve to 1q (sounds like this is what you did for this first effort). It's silly to build a super-efficient sieve and then give up early because you want to move on to LLR testing.
-Curtis
VBCurtis is offline   Reply With Quote
Old 2008-05-17, 15:21   #9
Kosmaj
 
Kosmaj's Avatar
 
Nov 2003

2×1,811 Posts
Default

48ms per iteration means about 19 days to complete one test at n=33.3M. What kind of machine are you using? Sounds like a fast one.

Does somebody know where is GIMPS (40M ?) and how long does it take to complete one test on a modern cpu.
Kosmaj is offline   Reply With Quote
Old 2008-05-17, 15:40   #10
mdettweiler
A Sunny Moo
 
mdettweiler's Avatar
 
Aug 2007
USA (GMT-5)

3×2,083 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
as far as I know, sr2sieve does not sieve both riesel and proth numbers together. I believe using an older program to achieve this costs more than it gains.

since such a sieve would run for CPU-years, it would pay to build a 20-k narrow sieve and a 1-k wide sieve and see which is faster for a given number of candidates (not faster speed, but faster p-removal).

If sieve resources are limited, it may make sense to pick a number of candidates for which you are willing to sieve to 1q (sounds like this is what you did for this first effort). It's silly to build a super-efficient sieve and then give up early because you want to move on to LLR testing.
-Curtis
Yes, sr2sieve can sieve both +1 and -1 numbers in the same sieve--in fact, that's what the Sierpinski/Riesel Base 5 project is doing right now (they use sr5sieve, which is extremely similar to sr2sieve code-wise). The only stipulation is that you use ABCD format for your sieve file, but that's probably a given anyway since ABCD and dat formats are the only formats sr2sieve accepts anyway.

To start such a sieve, just specify the sequences for both sides to srsieve in the usual manner, making sure of course to use the "-a" option to specify that you want to save your sieve file in ABCD format.
mdettweiler is offline   Reply With Quote
Old 2008-05-17, 16:19   #11
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

102558 Posts
Default

Quote:
Originally Posted by Kosmaj View Post
48ms per iteration means about 19 days to complete one test at n=33.3M. What kind of machine are you using? Sounds like a fast one.

Does somebody know where is GIMPS (40M ?) and how long does it take to complete one test on a modern cpu.
GIMPS is at about 43.5M for the majority of the never-assigned first-time LLs. Depends on your definition of a modern CPU, of course, but according to http://www.mersenne.org/bench.htm a Core 2 at 2600 MHz will take 30 CPU days.
If the time is about the same as GIMPS's times for a number of the same size (I think Prime95 is faster, but just theoretically) that would be a 2048K FFT size and 48 ms would be around a Core 2 Duo E6600 at standard clock of 2400MHz.
Mini-Geek is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Million digit moonshot MooMoo2 Twin Prime Search 9 2017-12-23 17:36
When will the first 10 million digit prime be reported? Uncwilly Lounge 13 2009-07-22 13:56
Deep Sieving 10m Digit Candidates lavalamp Open Projects 53 2008-12-01 03:59
k = 2 thru 31 Ten Million Digit numbers TTn 15k Search 4 2004-08-21 18:20
100 MILLION DIGIT NUMBER lpmurray Software 8 2004-05-31 19:22

All times are UTC. The time now is 08:36.


Mon Nov 29 08:36:40 UTC 2021 up 129 days, 3:05, 0 users, load averages: 1.52, 1.36, 1.23

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.