mersenneforum.org How do you efficiently sieve for prime 3/4-tuples?
 Register FAQ Search Today's Posts Mark Forums Read

 2015-09-05, 05:25 #144 MattcAnderson     "Matthew Anderson" Dec 2010 Oregon, USA 119210 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-09-06, 19:44 #145 Puzzle-Peter     Jun 2009 2BC16 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
 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-09-26, 14:07   #147
Puzzle-Peter

Jun 2009

22·52·7 Posts

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!
Attached Files
 fortsetzen.txt (17.7 KB, 128 views)

Last fiddled with by Puzzle-Peter on 2018-09-26 at 14:12 Reason: Typos. Lots of typos.

2018-09-26, 19:58   #148
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

2×19×43 Posts

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.

 2018-09-28, 03:40 #149 Puzzle-Peter     Jun 2009 22×52×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
 2018-10-10, 13:07 #150 Puzzle-Peter     Jun 2009 70010 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 22×52×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 22×52×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.
2018-12-21, 09:57   #154
henryzz
Just call me Henry

"David"
Sep 2007
Liverpool (GMT/BST)

11×557 Posts

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.

 Similar Threads Thread Thread Starter Forum Replies Last Post Stargate38 And now for something completely different 2 2017-04-28 00:08 fivemack Math 27 2015-12-12 18:42 tapion64 GPU Computing 7 2014-04-10 06:15 Unregistered Information & Answers 2 2010-05-25 20:51 Sloth Prime Sierpinski Project 1 2006-05-10 02:02

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

Thu Jun 1 04:39:51 UTC 2023 up 287 days, 2:08, 0 users, load averages: 1.17, 1.06, 1.12