Alternative Sieving for 10M digit prime search - Page 9

em99010pepe · 2007-04-26, 18:53

Can I join the fun?

Reserving 10T-15T

Carlos

VBCurtis · 2007-04-26, 20:11

I did some very rough estimates for sieve depth on k=3^16. I used mfh's result of 2120 expected factors in a 450B range near 5T, as well as the posted P4 sieve speed of 6.3 Mp/sec at 3.0Ghz to get a candidate removal rate of 40 sec/k at 5T on a P4-3.0.

I then ran a few hundred iterations of an LLR test on n=30,000,001, with a result of roughly 50 days per LLR test. 50 days is around 42M seconds. Even allowing for removal of n smaller than 30M for testing before this depth, I think you will have to sieve about a quarter-million-fold deeper before LLR at 30M makes sense, or 1250Q (yes, quadrillion). This assumes all sieving is done on P4 machines; proper depth could easily be 50% higher on AMD64.

At 10T/week per machine (around what an AMD64 could do now or soon), we're talking 100 CPU-weeks of sieving to get to 1Q, and a mere 2000-3000 CPU-years of sieving before LLR at 30M makes sense.

I rounded down most of my estimates generously, I believe. If anyone is curious about more detail for the estimates, I'm happy to share; I didn't want to bog down this post unnecessarily.

Finally: 2000Q is around 2^61. How deep can geoff's sieve go?
-Curtis

Citrix · 2007-04-26, 20:33

Quote:

Originally Posted by VBCurtis

Finally: 2000Q is around 2^61. How deep can geoff's sieve go?
-Curtis

2^62.

jasong · 2007-04-27, 00:31

I've read this thread once, and I'm a little confused. Could someone please consolidate the information and post an update? Then I can decide how best to use my machine(I have four machines, but only one is appropriate for this project.)

jasong · 2007-04-27, 00:47

Has anyone thought about making a sieving program that sieves only one k/n pair at a time? It would have to be much more complex than Mr. Woltman's program, but is probably do-able.

I'm going to ask the maker of JJSieve, next time I see him, if he would like to attempt this.

Citrix · 2007-04-27, 01:53

Quote:

Originally Posted by jasong

Has anyone thought about making a sieving program that sieves only one k/n pair at a time? It would have to be much more complex than Mr. Woltman's program, but is probably do-able.

I'm going to ask the maker of JJSieve, next time I see him, if he would like to attempt this.

What is the point of this? Newpgen can test 1k/n pair at a time.

As I posted previously, that if there is enough interest in 3^16 project, I can start a thread in the PSP forum (where I have mod rights) and eventually if the project, gains interest, get a new sub forum for 3^16. The new thread would be managed much better as I will have mod rights.

Do you guys think there is enough interest in 3^16 for a new thread?

MooMoo2 · 2007-04-27, 05:38

Quote:

Originally Posted by em99010pepe

6000031008577 | 43046721*2^42038368+1

My suggestion would be to use a k that's much lower (3, 5, or 7). The sieving might not be as fast as for k= 3^16, but you can LLR two k=3 candidates in the time that it takes to LLR just one k=3^16 candidate.

jasong · 2007-04-28, 02:51

Since I'm assuming we actually want to be competitive with GIMPS, I feel we should pick a range where the group could conceivably get up to, say, 2^58 or more within a reasonable amount of time.

I'll back off immediately if the following isn't the group's goal, but I came up with my idea because I thought people wanted a competitive alternative for attempting to win the $100,000 prize. If the prize money IS the reason most people are involved in this project, I would recommend a small range of k and an n-value that puts those values above the 10M digit watermark.

Citrix · 2007-04-28, 03:34

Personally my goal is to
1) Find the largest generalized fermat number on the top 20 page.
2) Find large primes.
3) Study distribution of primes for the 3^16 series
4) I don't think we will ever be able to compete with GIMPS and win the prize money.
5) Have some fun....

If no one is interested in going for the 10M digit prime, we can even reduce the .dat file and sieve to n=4M or so.

The advantage 3^16 has over other series is the fast sieve speed. But as it has been pointed out, these numbers are 2 times slower than smaller k's for LLR.

Could everyone else post their goals?

Citrix · 2007-04-28, 05:40

Attached is the file till n=4M. It is almost 3 times faster. File contains about 33,000 candidates between n=1-4M

If the members decide that sieving till n=4M is enough, this file can be used.

ValerieVonck · 2007-04-28, 07:53

8T - 9T Complete

I will use the new dat file after my current range is complete

2007-04-28, 03:34	#97
Citrix Jun 2003 2²×11×37 Posts	Personally my goal is to 1) Find the largest generalized fermat number on the top 20 page. 2) Find large primes. 3) Study distribution of primes for the 3^16 series 4) I don't think we will ever be able to compete with GIMPS and win the prize money. 5) Have some fun.... If no one is interested in going for the 10M digit prime, we can even reduce the .dat file and sieve to n=4M or so. The advantage 3^16 has over other series is the fast sieve speed. But as it has been pointed out, these numbers are 2 times slower than smaller k's for LLR. Could everyone else post their goals? Last fiddled with by Citrix on 2007-04-28 at 03:34

2007-04-28, 07:53	#99
ValerieVonck Mar 2004 Belgium 1517₈ Posts	8T - 9T Complete I will use the new dat file after my current range is complete Last fiddled with by ValerieVonck on 2007-04-28 at 07:54

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

2007-04-26, 18:53	#89
em99010pepe Sep 2004 5416₈ Posts	Can I join the fun? Reserving 10T-15T Carlos

2007-04-26, 20:11	#90
VBCurtis "Curtis" Feb 2005 Riverside, CA 2·2,927 Posts	I did some very rough estimates for sieve depth on k=3^16. I used mfh's result of 2120 expected factors in a 450B range near 5T, as well as the posted P4 sieve speed of 6.3 Mp/sec at 3.0Ghz to get a candidate removal rate of 40 sec/k at 5T on a P4-3.0. I then ran a few hundred iterations of an LLR test on n=30,000,001, with a result of roughly 50 days per LLR test. 50 days is around 42M seconds. Even allowing for removal of n smaller than 30M for testing before this depth, I think you will have to sieve about a quarter-million-fold deeper before LLR at 30M makes sense, or 1250Q (yes, quadrillion). This assumes all sieving is done on P4 machines; proper depth could easily be 50% higher on AMD64. At 10T/week per machine (around what an AMD64 could do now or soon), we're talking 100 CPU-weeks of sieving to get to 1Q, and a mere 2000-3000 CPU-years of sieving before LLR at 30M makes sense. I rounded down most of my estimates generously, I believe. If anyone is curious about more detail for the estimates, I'm happy to share; I didn't want to bog down this post unnecessarily. Finally: 2000Q is around 2^61. How deep can geoff's sieve go? -Curtis

2007-04-27, 00:31	#92
jasong "Jason Goatcher" Mar 2005 3×7×167 Posts	I've read this thread once, and I'm a little confused. Could someone please consolidate the information and post an update? Then I can decide how best to use my machine(I have four machines, but only one is appropriate for this project.)

2007-04-27, 00:47	#93
jasong "Jason Goatcher" Mar 2005 110110110011₂ Posts	Has anyone thought about making a sieving program that sieves only one k/n pair at a time? It would have to be much more complex than Mr. Woltman's program, but is probably do-able. I'm going to ask the maker of JJSieve, next time I see him, if he would like to attempt this.

2007-04-28, 02:51	#96
jasong "Jason Goatcher" Mar 2005 3·7·167 Posts	Since I'm assuming we actually want to be competitive with GIMPS, I feel we should pick a range where the group could conceivably get up to, say, 2^58 or more within a reasonable amount of time. I'll back off immediately if the following isn't the group's goal, but I came up with my idea because I thought people wanted a competitive alternative for attempting to win the $100,000 prize. If the prize money IS the reason most people are involved in this project, I would recommend a small range of k and an n-value that puts those values above the 10M digit watermark.