mersenneforum.org  

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

Reply
 
Thread Tools
Old 2012-04-20, 18:46   #45
Puzzle-Peter
 
Puzzle-Peter's Avatar
 
Jun 2009

10101010112 Posts
Default

Quote:
Originally Posted by firejuggler View Post
where should i change Sprime to sieve a bit deeper for quad? (right now, quad10011_5_20... 32.3 M k ...at 1.22 B, advancing slooowly 1k every 0.2/0.1 sec)
You're running NewPGen, right?

Mx experience is that if sieving to 1e9, the max. k-range is 10T. It can take more, but it is slow. Try splitting the range in half and you should get much faster progress.
Puzzle-Peter is offline   Reply With Quote
Old 2012-04-20, 18:54   #46
firejuggler
 
firejuggler's Avatar
 
Apr 2010
Over the rainbow

22×5×127 Posts
Default

thank you, that did the trick... now the rate is at 60 k per sec, much quicker... ( test primality on several machine)

Last fiddled with by firejuggler on 2012-04-20 at 18:55
firejuggler is offline   Reply With Quote
Old 2012-04-20, 20:43   #47
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

585810 Posts
Default

Quote:
Originally Posted by firejuggler View Post
just a minor nitpick : when you sieve for 7-tuple the file is named "quinxxx.txt"
Whoops. I will correct in the morning.

The 30/210 thing is just a speedup. The list axn posted assumed -5 -1 +1 +5 +7 +11. So this cannot be used for the 7-tuple combination I used. You can add to this list but cannot remove from it without missing candidates. Sometimes you can tighten it after adding more which is why we moved from 30 to 210.

I have been trying to use candidates that include all the previous types as well. I also test them in this order so if I find 5 primes when searching for 6-tuples then I have a 5-tuple. This isn't always possible. 6 and 7 were just too different. I managed to find one for 7 that includes 5 and below though. I would suggest we search for something like 8 at the size for a record at 6. This would mean even if we don't find a 8 we find something useful. I think running separate searches at 6 and 8 would be less effficient. Maybe people at tps would like to search for larger tuples. Some of these records seem to be sitting here for the taken by a project/person with a few cpu years as far as I can see.

@ puzzle-peter The site said there are no known 24-tuples. This basically means there aren't any small optimal tuples which have been found. The trivial search space was exhausted before they came across the first one. Relying on the law of small numbers didn't work in this case.
henryzz is offline   Reply With Quote
Old 2012-04-21, 06:03   #48
Puzzle-Peter
 
Puzzle-Peter's Avatar
 
Jun 2009

683 Posts
Default

Hm. I'm starting to realize just how much of the basics I'm missing.

A sixtuplet is a quadruplet with additions on each end, another -4 and +4. This is a pattern I don't see in any of the longer tuplets (well, I found one contained in a 19 *lol*). So sieving for 8 won't get any 6 as bycatch, right? But there is an 8-pattern that includes a 7-pattern, which is
8: 0 2 6 8 12 18 20 26
7: 0 2 6 8 12 18 20

The quadruplet pattern appears on most of the larger tuplets, which is why the quad code can be reused by adding to this pattern, correct?

I'm just trying to make sure I am able to make use of everything I read here without messing things up.

Thanks to everybody for your help and explanations!
Puzzle-Peter is offline   Reply With Quote
Old 2012-04-21, 11:47   #49
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

2·29·101 Posts
Default

I added a new constant tuple_size to all the source files. It basically changes the dimensions of ndx and the two loop counts. This means it is easier to do a change and is less error prone. All are attached. The only files with functional different are six and seven. I have changed seven to work mod 210 which should multiple the speed by 7 I believe.

Has anyone ever experimented with adding a prime to the presieve?
Has anyone fiddled with SieveSize?
Attached Files
File Type: zip tuples.zip (12.8 KB, 136 views)
henryzz is offline   Reply With Quote
Old 2012-04-21, 13:27   #50
Puzzle-Peter
 
Puzzle-Peter's Avatar
 
Jun 2009

683 Posts
Default

Quote:
Originally Posted by henryzz View Post
Has anyone ever experimented with adding a prime to the presieve?
Has anyone fiddled with SieveSize?
I added 19 to presieve, but by now I believe there are other changes to be made besides adding "*19" to the code. It worked and gave an identical result file, but I saw no speed gain.

I also tried different sievesizes, again with ambigous results. On one core it seemed to be faster when sievesize was larger than L2 cache size. Using all cores at the same time it seemed to be slower. I'm not sure if the constant disk access may have warped my timings as there were other processes needing a lot of bandwidth. I saw the iteration counter went up in irregular time intervals so I probably have to do the timings again.

I fiddled around with the number of smallprimes also and saw it can be quite large and still be lucrative. Depending mainly of N of course.

What's up with the 10000T limit? AFAIK qword can go higher by a factor 100.

EDIT: in Quin, Six and Seven K_START is being size checked as given in G while K_END is handled as given in T. Search ranges grow rapidly with long tuples so I think T is fine. It's really fast anyway.

Last fiddled with by Puzzle-Peter on 2012-04-21 at 13:39
Puzzle-Peter is offline   Reply With Quote
Old 2012-04-21, 15:32   #51
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

2·29·101 Posts
Default

k limit now increased to 10000P (10^19). There were a few arbitrary limits left in there from it being a twin prime sieve.
Both k_start and k_end are being checked in G now. I prefer G because it allows me to do small ranges for testing. I might try and work on a 5e9 sort of notation at some point.
There are more changes needed for changing the presieve.
henryzz is offline   Reply With Quote
Old 2012-04-21, 17:51   #52
Puzzle-Peter
 
Puzzle-Peter's Avatar
 
Jun 2009

683 Posts
Default

Quote:
Originally Posted by henryzz View Post
I might try and work on a 5e9 sort of notation at some point.
Don't do it because of me! G is fine and even I could do the switch back to T.
Puzzle-Peter is offline   Reply With Quote
Old 2012-04-22, 15:40   #53
Puzzle-Peter
 
Puzzle-Peter's Avatar
 
Jun 2009

12538 Posts
Default

Next question: the main part is do_sieve_iter. Its outer loop counts to sprime_ctr, so for each subrange sieved the runtime time should be linear with the number of small primes, right?

Decreasing SmallPrimes to a ridiculously low value like 1000 does not give very much of a speedup. Could it be that looping through the array to find the candidates left after sieving and write them to the outfile takes quite a lot of time?
Puzzle-Peter is offline   Reply With Quote
Old 2012-04-22, 17:32   #54
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

2·29·101 Posts
Default

Quote:
Originally Posted by Puzzle-Peter View Post
Could it be that looping through the array to find the candidates left after sieving and write them to the outfile takes quite a lot of time?
Quite possibly.
I am going to attempt running it with gprof. Win64 with gpof support isn't supported by fpc so trying linux.
Unfortunately my ubuntu virtual machine is 9.04 and can't upgrade easily. Downloading the 12.04 Beta 2 iso now.
henryzz is offline   Reply With Quote
Old 2012-04-22, 20:49   #55
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

1,459 Posts
Default

I have written a sieve in c language for this problem, see https://sites.google.com/site/robertgerbicz/gsieve.

It should be faster than axn's version. It uses different type of sieves depending on the number of candidates and p value.

Set bound_small_primes as 13, if 2*3*5*7*11*13*SmallPrimes<=end_k-start_k. You can try to use 13 earlier also. Or even higher. Play also with sieve_len. From the printed timing information and ratio of the progress you can get quickly an estimation for the completion time.

Note that this sieve doesn't care about tiny ranges, it is really slow if you give say a 1 billion range. The current setup is fast if end_k-start_k>>2310*10^9.

Due to the wheelsieve it doesn't print out the remaining k candidates in increasing order.

Last fiddled with by R. Gerbicz on 2012-04-22 at 20:50
R. Gerbicz is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
How/Where to get Jens Kruse Andersen's prime constellation sieve? Stargate38 And now for something completely different 2 2017-04-28 00:08
Efficiently finding a linear progression in data fivemack Math 27 2015-12-12 18:42
GPU Prime Sieve tapion64 GPU Computing 7 2014-04-10 06:15
Sieve depth vs. prime probability Unregistered Information & Answers 2 2010-05-25 20:51
Prime in Riesel Sieve Project Sloth Prime Sierpinski Project 1 2006-05-10 02:02

All times are UTC. The time now is 04:24.

Wed Apr 21 04:24:27 UTC 2021 up 12 days, 23:05, 0 users, load averages: 1.10, 1.68, 1.84

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.