How do you efficiently sieve for prime 3/4-tuples? - Page 14

MattcAnderson · 2015-09-05, 05:25

Hi Math People,
Thanks to Henry for showing me polysieve2. I used it to sieve for some primes of up to 19 digits to the Online Encyclopedia of Integer Sequences. My last entry was http://oeis.org/A257140. The sequence is a 13 tuplet with pattern [0, 2, 8, 14, 18, 20, 24, 30, 32, 38, 42, 44, 48]. Here is the associated .b file with 104 primes.

I have been using some Maple code that I wrote also, but it is very slow.

It would be great if there was software that could search primes with 20 or more digits of similar forms quickly.

Does anyone know of such a software?

Regards,

Matt

Puzzle-Peter · 2015-09-06, 19:44

Forget what I wrote here first. I finally understood the core of the problem.

danaj · 2015-10-14, 04:00

I looks like we have both this thread and this one to discuss constellations. Any others? I don't think that one belongs in the GIMPS math forum, but that seems to be another contentious discussion.

From what I can tell from both the OP and almost all discussion, this thread is about finding record large values (e.g. k*2^n-1), so looking for huge quadruplets, rather than what Matt is doing, which is finding comprehensive lists of the first N tuples. That's what the other thread is about.

Matt, I updated A257140 tonight with 1036 values, as well as the other 13-tuplets earlier this week. I'm working on the 14-tuplets now (I already found a missing value in A257167). More discussion of this should be on the other thread or a new one.

Puzzle-Peter · 2018-09-26, 14:07

It's me again...

I am using polysieve quite a lot and i recently ventured into the realms of pretty big numbers. It works just fine. I love it.

But there is one problem. I would like to use it to sieve quite deeply, but I cannot run my machine for months on end due to power outages, updates etc. So I thought about restarting an existing sieve file.

I am a really poor programmer. So my way of tackling this problem was to change as little as possible in the original code. Plus I am willing to accept poor user friendliness.

So here's what tried to do:
I wouldn't even attempt to parse the header line, so the user (i.e. myself) simply needs to input all the information again and some more. No big deal. So I start with a presieved file with the header line deleted. I can always add it with an editor after sieving .

Then I fill the alist array from the file and continue sieving. At least that's what I would like to do

After several solvable problems I am now at a loss. Everything seems to work just fine until the program tries to assign an array called invtable. That's where I get a segmentation fault and no further error message. My compiler (gcc 4.4) does not say a thing when compiling.

The last screen output I get is "Using M=30, mres=15" and the very next line in the code is the line reading "int **invtable". I put a printf command immediately after this, but it does not get executed so I guess that's where the segmentation fault happens. Could anyone please point me to where this is going wrong? That's a section of the code I didn't even touch so I really don't understand what's happening here.

I'll attach what I have so far. It's not pretty and there are a lot of printf statements that are left from hunting previous errors. Plus I realized I have started with the version that does not have the assembler bit for mulmod, but I can always change that once it's running. Any help or hints on how to deal with such an error is greatly appreciated.

PS: the filename should end in .c but that's not accepted so I changed it to .txt

Thanks!

R. Gerbicz · 2018-09-26, 19:58

Quote:

Originally Posted by Puzzle-Peter

But there is one problem. I would like to use it to sieve quite deeply, but I cannot run my machine for months on end due to power outages, updates etc. So I thought about restarting an existing sieve file.

Thanks for your interest! I'll look the code.

Puzzle-Peter · 2018-09-28, 03:40

I wasn't looking for someone to do the work. But it's great you want to look at it as your result is guaranteed to be better than what I would have come up with.
Thanks a lot!

Puzzle-Peter · 2018-10-10, 13:07

After some more testing I need to correct my statement. The whole invtable thing is being executed. I had compiler optimization active which seems to have rearranged the order of execution. The problem seems to be somewhere else.

Puzzle-Peter · 2018-10-20, 07:21

Okay, I think I got it.

It's still not very comfortable but for me it's good enough. When I think about time I spent hunting a pretty stupid mistake... well, I did learn quite a bit so that's okay I guess.

Puzzle-Peter · 2018-12-19, 18:30

Does anyone know what it would take to make the code run on GPU? Is it even worth trying? I have no idea so if this is a stupid approach please tell me so

I know some sieves have been massively accelerated by using GPU computing, but I don't know if this kind of sieve is even suited for GPUs

henryzz · 2018-12-20, 08:33

I think your best idea is to get this sieve integrated into mtsieve in order to make it easier to add gpu support.
There are various things that could potentially speed up the code as is. The code currently makes no use of SIMD. That could potentially speed it up massively for p < 2^53. I am not sure where the slowest points of this sieve are though so I can't make any guarantees.

henryzz · 2018-12-21, 09:57

Quote:

Originally Posted by henryzz

I think your best idea is to get this sieve integrated into mtsieve in order to make it easier to add gpu support.
There are various things that could potentially speed up the code as is. The code currently makes no use of SIMD. That could potentially speed it up massively for p < 2^53. I am not sure where the slowest points of this sieve are though so I can't make any guarantees.

After thinking about it some more we can forget about a speedup due to SIMD as the time is spent sieving rather than modular multiplications. I also think it would be difficult to maintain the current speed in mtsieve due to how clever polysieve is with the caches(don't know how much we actually gain from this or how hard it would be to replicate). I don't know whether this would be a good case for a gpu sieve. rogue would be the person to ask about that I think.

2015-09-06, 19:44	#145
Puzzle-Peter Jun 2009 2BC₁₆ Posts	Forget what I wrote here first. I finally understood the core of the problem. Last fiddled with by Puzzle-Peter on 2015-09-06 at 19:47 Reason: Slow brain

2018-09-28, 03:40	#149
Puzzle-Peter Jun 2009 2²×5²×7 Posts	I wasn't looking for someone to do the work. But it's great you want to look at it as your result is guaranteed to be better than what I would have come up with. Thanks a lot! Last fiddled with by Puzzle-Peter on 2018-09-28 at 03:41

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

2015-09-05, 05:25	#144
MattcAnderson "Matthew Anderson" Dec 2010 Oregon, USA 1192₁₀ Posts	Hi Math People, Thanks to Henry for showing me polysieve2. I used it to sieve for some primes of up to 19 digits to the Online Encyclopedia of Integer Sequences. My last entry was http://oeis.org/A257140. The sequence is a 13 tuplet with pattern [0, 2, 8, 14, 18, 20, 24, 30, 32, 38, 42, 44, 48]. Here is the associated .b file with 104 primes. I have been using some Maple code that I wrote also, but it is very slow. It would be great if there was software that could search primes with 20 or more digits of similar forms quickly. Does anyone know of such a software? Regards, Matt

2015-10-14, 04:00	#146
danaj "Dana Jacobsen" Feb 2011 Bangkok, TH 2×5×7×13 Posts	I looks like we have both this thread and this one to discuss constellations. Any others? I don't think that one belongs in the GIMPS math forum, but that seems to be another contentious discussion. From what I can tell from both the OP and almost all discussion, this thread is about finding record large values (e.g. k*2^n-1), so looking for huge quadruplets, rather than what Matt is doing, which is finding comprehensive lists of the first N tuples. That's what the other thread is about. Matt, I updated A257140 tonight with 1036 values, as well as the other 13-tuplets earlier this week. I'm working on the 14-tuplets now (I already found a missing value in A257167). More discussion of this should be on the other thread or a new one.

2018-10-10, 13:07	#150
Puzzle-Peter Jun 2009 700₁₀ Posts	After some more testing I need to correct my statement. The whole invtable thing is being executed. I had compiler optimization active which seems to have rearranged the order of execution. The problem seems to be somewhere else.

2018-10-20, 07:21	#151
Puzzle-Peter Jun 2009 2²×5²×7 Posts	Okay, I think I got it. It's still not very comfortable but for me it's good enough. When I think about time I spent hunting a pretty stupid mistake... well, I did learn quite a bit so that's okay I guess.

2018-12-19, 18:30	#152
Puzzle-Peter Jun 2009 2²×5²×7 Posts	Does anyone know what it would take to make the code run on GPU? Is it even worth trying? I have no idea so if this is a stupid approach please tell me so I know some sieves have been massively accelerated by using GPU computing, but I don't know if this kind of sieve is even suited for GPUs

2018-12-20, 08:33	#153
henryzz Just call me Henry "David" Sep 2007 Liverpool (GMT/BST) 11·557 Posts	I think your best idea is to get this sieve integrated into mtsieve in order to make it easier to add gpu support. There are various things that could potentially speed up the code as is. The code currently makes no use of SIMD. That could potentially speed it up massively for p < 2^53. I am not sure where the slowest points of this sieve are though so I can't make any guarantees.