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

[henryzz]

I get:

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?

[axn]

can you compile with -gl option and post the debug output?

[henryzz]

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.

[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

      { 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.

[axn]

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

      { 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.

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.

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.

[henryzz]

Downloading the windows sdk to get ml64.exe which is needed for -al

[Puzzle-Peter]

So who can / will extend this to 6-, 7-, 8-tuplets or even farther? I know I can't

[henryzz]

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(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.

Anyone know the best pfgw ABC header for quads or larger?

[axn]

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?

[henryzz]

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.

[axn]

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.

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.