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

 2012-04-15, 15:39 #23 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 2×29×101 Posts I get: Code: E:\OurDevelopment\David\Pascal>Quad.exe 1500 0 2 Initializing Primes ... Done. Quad n=1500 k=27-1999999999977 p<=1190494759 Initializing Sieve ... Done. Runtime error 216 at $000000010000206B$000000010000206B $00000001000023E0$00000001000091F5 E:\OurDevelopment\David\Pascal>triple.exe 1500 0 2 Initializing Primes ... Done. Triple n=1500 k=3-1999999995 p<=1190494759 Initializing Sieve ... Done. Runtime error 216 at $0000000100001F2B$0000000100001F2B $00000001000022A0$00000001000090B5 after compiling with: "C:\Program Files\FPC\2.6.0\bin\i386-win32\ppcrossx64" -Sg Quad.pas "C:\Program Files\FPC\2.6.0\bin\i386-win32\ppcrossx64" -Sg triple.pas any hints?
 2012-04-15, 16:32 #24 axn     Jun 2003 7×19×37 Posts can you compile with -gl option and post the debug output?
2012-04-15, 18:52   #25
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT/BST)

2×29×101 Posts

Quote:
 Originally Posted by axn can you compile with -gl option and post the debug output?
Strangely they start working when I compile with -gl. I had tried running with options like -O- to disable optimisations already.

 2012-04-15, 20:56 #26 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 2·29·101 Posts Am I correct in thinking that adding +11 to to search for quintuplets isn't that hard? You used 6 all over the triplet code and 30 all over the quads code. Quads needed 30 because 7>6. Quins can keep 30 as 11<30 so all that needs adding is Code:  { c = +1 ==> x = -[11*t+k] } x := t*2; if(x >= n) then x := x - n; {2t} x := x*2; if(x >= n) then x := x - n; {4t} x := x+t; if(x >= n) then x := x - n; {5t} x := x*2; if(x >= n) then x := x - n; {10t} x := x+t; if(x >= n) then x := x - n; {11t} x := x+k; if(x >= n) then x := x - n; {11t+k} if(x > 0) then x := n-x; { - } ndx[i, 5] := x; plus changing the dimensions of ndx and a few loop counters Is there any way of me getting it running not under debug logging? edit: Is the minimum n of 1000 critical? from the code I would guess that n=31 or maybe 61 would actually be the minimum for the quads code. I will experiment comparing with newpgen's output. Last fiddled with by henryzz on 2012-04-15 at 21:00
2012-04-15, 22:42   #27
axn

Jun 2003

7×19×37 Posts

Quote:
 Originally Posted by henryzz Am I correct in thinking that adding +11 to to search for quintuplets isn't that hard? You used 6 all over the triplet code and 30 all over the quads code. Quads needed 30 because 7>6. Quins can keep 30 as 11<30 so all that needs adding is Code:  { c = +1 ==> x = -[11*t+k] } x := t*2; if(x >= n) then x := x - n; {2t} x := x*2; if(x >= n) then x := x - n; {4t} x := x+t; if(x >= n) then x := x - n; {5t} x := x*2; if(x >= n) then x := x - n; {10t} x := x+t; if(x >= n) then x := x - n; {11t} x := x+k; if(x >= n) then x := x - n; {11t+k} if(x > 0) then x := n-x; { - } ndx[i, 5] := x; plus changing the dimensions of ndx and a few loop counters
Should be fine.

Quote:
 Originally Posted by henryzz Is there any way of me getting it running not under debug logging?
Can you compile with -al and post the assembly listing (.s) file. It could be that in optimizing mode, I might need to save/restore a few of the registers in the various asm blocks.

Quote:
 Originally Posted by henryzz edit: Is the minimum n of 1000 critical? from the code I would guess that n=31 or maybe 61 would actually be the minimum for the quads code. I will experiment comparing with newpgen's output.
You're right. That check was added to make sure that you are using sensible n values. I think n = 30 would be the lowest. As long as k*2^n > max sieve prime it should be fine.

 2012-04-16, 12:25 #28 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 16E216 Posts Downloading the windows sdk to get ml64.exe which is needed for -al
 2012-04-16, 16:23 #29 Puzzle-Peter     Jun 2009 2AB16 Posts So who can / will extend this to 6-, 7-, 8-tuplets or even farther? I know I can't
2012-04-16, 16:50   #30
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT/BST)

2·29·101 Posts

I think I should be able to extend it to 6 7 or 8 -tuplets

I have attached the .s file produced by ppcrossx64 -al
masm then fails to assemble it with mulitple errors of the following types:
Quad.s(1072) : error A2022:instruction operands must be the same size

Looks to me like the assembler included in ppcrossx64 lets the code get away with something that it shouldn't and masm picks up on it.

Attached Files

2012-04-16, 21:04   #31
axn

Jun 2003

7×19×37 Posts

Quote:
 Originally Posted by henryzz I have attached the .s file produced by ppcrossx64 -al masm then fails to assemble it with mulitple errors of the following types: Quad.s(1060) : error A2101:cannot add two relocatable labels Quad.s(1072) : error A2022:instruction operands must be the same size Looks to me like the assembler included in ppcrossx64 lets the code get away with something that it shouldn't and masm picks up on it.
Those errors should be harmless. If the object code is produced, it should work. Looking thru the asm listing, I can't see anything obviously wrong with the code sections that I was worried about.

EDIT:- Did you, by any chance, use the -gl setting along with the -al setting?

Last fiddled with by axn on 2012-04-16 at 21:05

2012-04-16, 21:21   #32
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT/BST)

2×29×101 Posts

Quote:
 Originally Posted by axn Those errors should be harmless. If the object code is produced, it should work. Looking thru the asm listing, I can't see anything obviously wrong with the code sections that I was worried about. EDIT:- Did you, by any chance, use the -gl setting along with the -al setting?
I don't think I did with the .s file I provided. I get the same errors with the -gl setting added to the -al setting.

I have produced versions for quintuples and sextuples. They have hardly been tested and I am only pretty certain I added -5 right as it is negative. The source is attached.
Attached Files
 5and6.zip (5.2 KB, 116 views)

2012-04-16, 22:30   #33
axn

Jun 2003

7·19·37 Posts

Quote:
 Originally Posted by henryzz I don't think I did with the .s file I provided. I get the same errors with the -gl setting added to the -al setting.
I am out of ideas Perhaps you can save/restore registers in each asm block. Try adding "push <reg>" statements at the beginning of each asm block and do a "pop <reg>" at the end. Save/restore all registers except eax & edx.

I am thinking of rewriting the whole thing in C without asm.

Quote:
 Originally Posted by henryzz I have produced versions for quintuples and sextuples. They have hardly been tested and I am only pretty certain I added -5 right as it is negative. The source is attached.
They look correct. Note that for sextuples, you can include 7 (30 becomes 210) also into the mix and thus be 7 times faster.

 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 05:42.

Wed Apr 21 05:42:16 UTC 2021 up 13 days, 23 mins, 0 users, load averages: 1.38, 1.77, 1.86