Fastprime Quadrupel und Primzahlvierlinge

Horst_H · Verfasst: Di 29.08.17 10:22

Hallo,

ich versuche ja, das sieben zu beschleunigen, da ich den PrimzahlTest selbst nicht beschleunigen kann.
Und, wer hätte das gedacht, das geht auch ;-)

4e9 durchsiebt er bei mir in 1,5 Sekunden. ( Edit4 Freepascal Linux 64-Bit oder 32-Bit gleich )
Berechnung der nächsten Position stark vereinfacht, aber nicht unbedingt verständlicher.

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
167:
168:
169:
170:
171:
172:
173:
174:
175:
176:
177:
178:
179:
180:
181:
182:
183:
184:
185:
186:
187:
188:
189:
190:
191:
192:
193:
194:
195:
196:
197:
198:
199:
200:
201:
202:
203:
204:
205:
206:
207:
208:
209:
210:
211:
212:
213:
214:
215:
216:
217:
218:
219:
220:
221:
222:
223:
224:
225:
226:
227:
228:
229:
230:
231:
232:
233:
234:
235:
236:
237:
238:
239:
240:
241:
242:
243:
244:
245:
246:
247:
248:
249:
250:
251:
252:
253:
254:
255:
256:
257:
258:
259:
260:
261:
262:
263:
264:
265:
266:
267:
268:
269:
270:
271:
272:
273:
274:
275:
276:
277:
278:
279:
280:
281:
282:
283:
284:
285:
286:
287:
288:
289:
290:
291:
292:
293:
294:
295:
296:
297:
298:
299:
300:
301:
302:
303:
304:
305:
306:
307:
308:
309:
310:
311:
312:

program FindeQuadrupel;
//Sieben nach Quadrupeln der Form 30*n+(11,13,17,19)
//also muss Mod30 aus Menge [11,13,17,19] sein
//die Faktoren bestimmen den Abstand zum nächsten Element aus der Menge
//Beispiel 1 -> 0R 1 hat bei *11, *13, *17, *19, einen Treffer,
//wieder bei *(30+11-19) = *22
//faktorenmässig Start bei +11,dann +2+4+2+22,+2+4+2+22 ....
//Also 4 Treffer bei einem Schritt von 30.
//ich bestimme die Faktoren einmal und dann wird nur noch addiert
//
//Vergleich mit https://oeis.org/A007530/b007530.txt

{$IFDEF FPC}
  {$MODE DELPHI}
  {$OPTIMIZATION ON,REGVAR,CSE,PEEPHOLE}
  //{$R+,I+,O+} //gibt kein mecker mehr...
{$ELSE}
  {$APPTYPE CONSOLE}
{$ENDIF}
uses
  sysutils;
type
  tSieveElem = NativeUint;

  tDelta30 = array[0..3] of  NativeUint;
  tMulOfs = record
              moMul,moOfs: byte;
            end;
  tMulPosArr = array[0..3] of  tMulOfs;

  tPrimMod30   =packed record
//                 deltaP     : p[n-1]-p[n] (delta DIV30 + delta MOD30 )
                   pm30Offset   : LongWord;  //Uebertrag bis 22 * p DIV 30
                   pmNextSivbNr : word;
                   pm30AktIdx,
                   pm30Delta  : byte;//delta DIV30 shl 3 + delta MOD30Idx
                 end;
  tpPrimMod30 = ^tPrimMod30;

const
  cMulOfs : array [0..7]of tMulPosArr =
    (((moMul: 2;moOfs:0),(moMul: 4;moOfs: 0),(moMul: 2;moOfs:0),(moMul:22;moOfs: 1)), // 1
     ((moMul: 4;moOfs:1),(moMul: 8;moOfs: 2),(moMul: 4;moOfs:1),(moMul:14;moOfs: 3)), // 7
     ((moMul: 6;moOfs:2),(moMul:16;moOfs: 6),(moMul: 6;moOfs:2),(moMul: 2;moOfs: 1)), //11
     ((moMul:12;moOfs:5),(moMul: 4;moOfs: 2),(moMul:12;moOfs:5),(moMul: 2;moOfs: 1)), //13
     ((moMul:12;moOfs:7),(moMul: 4;moOfs: 2),(moMul:12;moOfs:7),(moMul: 2;moOfs: 1)), //17
     ((moMul: 6;moOfs:4),(moMul:16;moOfs:10),(moMul: 6;moOfs:4),(moMul: 2;moOfs: 1)), //19
     ((moMul: 4;moOfs:3),(moMul: 8;moOfs: 6),(moMul: 4;moOfs:3),(moMul:14;moOfs:11)), //23
     ((moMul: 2;moOfs:2),(moMul: 4;moOfs: 4),(moMul: 2;moOfs:2),(moMul:22;moOfs:21)));//29

  cMod30ToIdx : array[0..29] of byte =
                 (111,0,111,111,111,111,111,1,111,111,111,2,111,3,111,
                  111,111,4,111,5,111,111,111,6,111,111,111,111,111,7);

  cIdxToMod30 : array[0..7] of byte = (1,7,11,13,17,19,23,29);

//Anzahl der Bits eines Sieb-Elementes
  cBitSize = SizeOf(tSieveElem)*8;
  cAndMask = cBitSize-1;


//Abfolge der Streichpositionen
//Nextpos = k*p DIV 30
//idx = cMod30ToIdx[p MOD 30]
//i = 0;
//repeat
//  NextPos = Lastpos + (cStartOffset[idx][i] + (p DIV 30)*cFaktoren[idx][i]);
//  i = (i+1) AND 3;
//until JetztIstAberGut;

//1*151 == 5*30+1
//idx -> 0
//Ausnahme erster Wert dort NextPos = NextPos shr 1;
// 11*151 = 1661 = 55*30+11
// i:= 3;
//  NextPos = (1 + 5* 22) shr 1;//(1 +110) shr 1 -> 55
//  i = (i+1) AND 3 => 0
// 13*151 = 1963 = 65*30+13
//  NextPos = 55+(0 + 5* 2);//55+10 -> 65
//  i = (i+1) AND 3 => 1
// 17*151 = 1963 = 85*30+17
//  NextPos = 55+(0 + 10* 2);//65+20 -> 85
//  i = (i+1) AND 3 => 2
// 19*151 = 1963 = 65*30+19
//  NextPos = 85+(0 + 5* 2);//85+10 -> 95
//  i = (i+1) AND 3 => 3
// (30+11)*151 = 6191 = 206*30+11
//  NextPos = 95+(1 + 5* 22);//95+111 -> 206
//  i = (i+1) AND 3 => 0
// (30+13)*151 = 6493 = 216*30+13
//  NextPos = 206+(0 + 5* 2);//206+10 -> 216

//Ein Sieb x64-bit
//  cSiebGroesse = 500*1000*1000*1000;//->4671000 in 521s/57089 Primz

//mehrfach mit Übertrag gesiebt 2000*cSiebgroesse
//Anzahl Primzahlen 57089  Anzahl      : 4671012    210s

// etwa 1 MB
  cSiebGroesse  = 64*30*130208;//2.5e8-640

  cPrimeMax =63245;//trunc(sqrt(MaxZahl))+1;
var
  SiebMod30 : array[0..(cSiebGroesse-1) DIV 30 DIV cBitSize] of tSieveElem;
  Prim30List :array[0..11895200] of tPrimMod30;
  PrimSieb  : array of boolean;
  T0,T1: TDAteTime;
  gblP30,
  Prim30idx,
  LastPrime : longWord;

  tmpDelta30:tDelta30;

function Auszaehlen:Longint;
var
  i:NativeUInt;
  elem:tSieveElem;
begin
  result := 0;
  Begin
    For i := Low(SiebMod30) to High(SiebMod30)-1 do
    Begin
      //Bits umkehren
      elem := NOT SiebMod30[i];
      repeat
        inc(result,elem AND 1);
        elem := elem shr 1;
      until elem  = 0;
    end;
    // die letzten Bits zaehlen
    elem := NOT SiebMod30[High(SiebMod30)];
    i := High(SiebMod30)*30*cBitsize;
    while i < cSiebGroesse do
    Begin
      inc(result,elem AND 1);
      elem := elem shr 1;
      inc(i,30);
    end;
  end;
end;

procedure MulListErstellen(p30:LongWord);
var
  pMulPos : ^tMulOfs;
begin
  pMulPos := @cMulOfs[p30 AND 7][0];
  //p30 zu p DIV 30
  p30 := p30 shr 3;
  with pMulPos^ do
    tmpDelta30[0] := moOfs+p30*moMul;
  inc(pMulPos);
  with pMulPos^ do
    tmpDelta30[1] := moOfs+p30*moMul;
  inc(pMulPos);
  with pMulPos^ do
    tmpDelta30[2] := moOfs+p30*moMul;
  inc(pMulPos);
  with pMulPos^ do
    tmpDelta30[3] := moOfs+p30*moMul;
end;
procedure PrimSieben;
var
  i,p: NativeInt;
Begin
  p := 2;
  repeat
    i := p*p;
    while i <= cPrimeMax do
    Begin
      PrimSieb[i] := true;
      inc(i,p);
    end;
    repeat
      inc(p);
    until NOT PrimSieb[p]
  until (p*p) >cPrimeMax;
end;

procedure PrimListeErstellen;
var
  i: NativeInt;
  p30,p30Idx,DIV30,Aktidx,Last30Prime: NativeUInt;
Begin
  T0 := now;
  setlength(PrimSieb,cPrimeMax+1);
  PrimSieben;

  Prim30idx   := 0;
  LastPrime   := 1;
  Last30Prime := 0;//==  1;
  For i := 7 to cPrimeMax do
    IF Not PrimSieb[i] then
    Begin
      DIV30 := i DIV 30;
      p30Idx := cMod30ToIdx[i-30*DIV30];
      p30 := DIV30 shl 3+p30Idx;
      MulListErstellen(p30);
      //>>ersten Offset bestimmen
      IF cMulOfs[p30Idx][3].moMul = 2 then
      Begin
        inc(DIV30,tmpDelta30[0]);
        Aktidx:= 1
      end
      else
      Begin
        DIV30:= tmpDelta30[3] shr 1;
        Aktidx:= 0;
      end;
       //<<ersten Offset bestimmen

      with Prim30List[Prim30idx] do
      Begin
        pm30Offset:= Div30;
        pm30Delta := p30-Last30Prime;
        pm30AktIdx:= Aktidx;
      end;
      inc(Prim30idx);
      if Prim30idx>High(Prim30List) then
      Begin
        BREAK;
      end;
      Last30Prime:= p30;
      LastPrime := i;
    end;
  dec(Prim30idx);
  setlength(PrimSieb,0);
  T1 := now;
  writeln('Anzahl Primzahlen ',Prim30idx,' Letzte PrimZahl ', lastPrime);
  Writeln('Laufzeit sieben',FormatDateTime('S.ZZZ',T1-T0));
end;

procedure EinmalSieben(var Prim30:tPrimMod30);
var
  p30,mytmp,AktIdx: NativeUInt;
begin
   with Prim30 do
   Begin
     MulListErstellen(gblP30);
     p30 := pm30Offset;
     AktIdx := pm30AktIdx;
   end;
  //Jetzt einfaches markieren und addieren
  //number of the highest Bit (High(SiebMod30)+1)*cBitSize-1
  while p30 < cSiebGroesse DIV 30 do
  Begin
    mytmp := p30 DIV cBitSize;
    SiebMod30[mytmp]:= SiebMod30[mytmp] OR (tSieveElem(1) shl (p30 AND cAndMask));
    inc(p30,tmpDelta30[AktIdx]);
    AktIdx := (AktIdx + 1) AND 3;
  end;
  with Prim30 do
  Begin
     pm30Offset:= p30-cSiebGroesse DIV 30;
     pm30AktIdx := AktIdx;
   end;

end;

function AlleSieben:longint;
var
  pPL : tpPrimMod30;
  i,k,cnt : NativeInt;

begin
  k := 0;
  cnt := 0;
repeat
  fillchar(SiebMod30,SizeOf(SiebMod30),0);
  i := 0;
  pPL := @Prim30List[0];
  gblP30 := 0;// == 1
  repeat
      inc(gblP30,pPL^.pm30Delta);
      If pPL^.pm30Offset < cSiebGroesse DIV 30 then
        EinmalSieben(pPl^)
      else
        dec(pPl^.pm30Offset,cSiebGroesse DIV 30);
    inc(pPL);
    inc(i);
  until i > Prim30idx;
  inc(cnt,Auszaehlen);
  inc(k);
until k >=8;//2000;
  result := cnt;
end;

var
  cnt:NativeUInt;
BEGIN
  PrimListeErstellen;
  cnt := AlleSieben;

  writeln('Limit         : ',cSiebGroesse);
  writeln('Suchfeldlimit : ',(High(SiebMod30)+1)*30*cBitSize);
  writeln('Anzahl        : ',cnt);
end.
(*
//i386
Limit         :16*(250e6-640)
Suchfeldlimit : 4000000320
Anzahl        : 85911

real  0m1.451s


Anzahl Primzahlen 57089 Letzte PrimZahl 707197
Laufzeit sieben 0.004
499.99e9 fast 500e9
Anzahl        : 4670987
real  3m31.657s -> 212 Sekunden

*)

Jetzt muss nur noch eine clevere Lösung gefunden werden, dass für die Quadrupelsuche zu nutzen.
Die Platzersparnis für das Sieb ist ja enorm.Wenn man auf Bytebene bleibt ist es ein Faktor 30 auf Bitebene nochmals 8.
Bei 1MB levelII-Cache bei mir könnten da jetzt um 240 Mio Zahlen passen.
AMD-Rechner vor Ryzen sind leider im Speicherzugriff relativ lahm.Je "näher" an der CPU, desto besser.
Für jede Streichprimzahl mir auch noch OffsetMod30[0..3] und den momentanen Index [0..3] zu merken bläht die Primzahlliste auf, aber die wird ja sequentiell und damit schnell gelesen.
Vielleicht wieder holt sich das Muster wieder alle 30 0R1(=1),1R1(=31),2R1(=61)..30R1(=901)
Mal schauen

Gruß Horst
Edit:
Das Bitfeld ist jetzt implementiert.Jetzt fehlt die Berechnung der Überträge.

Edit2->3:
Die Uebtraege habe ich immer noch nicht.Aber ich kämpfe mit einer kompakten Speicherung der Siebprimzahlen.
Jetzt 8 Byte,weil ich die Differenz zum Vorgänger speichere.pm30Delta als Byte entspricht maximal 959 als Abstand.
Das ist irgendwo bei 1e15 der Fall...

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:

type
tPrimMod30   =packed record
//                 p30   = (p DIV 30 shl 3)+ cMod30ToIdx[p Mod 30]
                   pm30Offset   : LongWord;  //Uebertrag bis 22 * p DIV 30
                   pmNextSivbNr : word;      // Wenn siebnr erreicht dann erst damit sieben
                   pm30AktIdx,
                   pm30Delta  : byte;//delta DIV30 shl 3 + delta MOD30Idx (== p30[n]-p30[n-1] )
                 end;

EDIT3: Es geht einfacher, siehe Programm.

Mathematiker · Verfasst: So 03.09.17 21:03

Hallo,
ich habe die Primzahlvierlingssuche jetzt auf 2 Threads aufgeteilt.
Der erste siebt jeweils einen Bereich von 500000 mit 10 Millionen Primzahlen vor und ermittelt die "Kandidaten" für einen Vierling, d.h. in dem Zehner dürfen die auf 1,3,7,9 endenden Zahlen nicht ausgesiebt sein.
Die Kandidaten werden über eine threadsichere Stringliste an den 2.Thread übergeben.

Dieser testet nun die 4 Zahlen eines Kandidaten auf Primzahleigenschaft und entfernt den getesteten Kandidaten aus der Stringliste.

Es funktioniert eigentlich ganz gut.
Leider ist der 2.Thread deutlich langsamer als der erste. Damit es nicht zu einem Stau in der Stringliste kommt, prüfe ich im ersten Thread mit

markieren

Delphi-Quelltext

1:
2:

while liste.count>50 do begin
end;

die Listeneinträge und bremse den 1.Thread bei mehr als 50 Kandidaten.
Wichtig ist das vor allem, wenn die Berechnung abgebrochen wird, da dann erst alle Kandidaten abgearbeitet werden müssen, d.h. der Hauptthread wartet bis der 2. fertig ist.
Schön ist das nicht.

Meine Frage nun: Seht ihr eine andere Möglichkeit, beide Threads auf etwa gleiche Geschwindigkeit zu bringen? Gibt es eine andere Möglichkeit, den ersten Thread mit dem 2. zu synchonisieren?

Der angehängte Quelltext ist Lazarus-64-Bit. Diese Exen sind deutlich schneller als bei meinem Delphi 5.

Danke
Steffen

Nachtrag: Nach 19 min Laufzeit stürzt es jetzt auch noch ab. Warum? Ich weiß es nicht.

Nebenbei: Unsere kleine Gruppe, die erfolgreich nach Primzahlvierlingen sucht, benötigt noch Rechenleistung. Mitstreiter sind herzlich willkommen. :wink:

siehe: matheplanet.com/math...lps=1680408#v1680408
bzw. mathematikalpha.de/primzahlvierlinge

Einloggen, um Attachments anzusehen!

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein

Delphi-Laie · Verfasst: Mo 04.09.17 00:48

Statt Polling mit der while-Schleife sind Botschaften auf der Sendeseite und deren ressourcenschonender Empfang mit Getmessage ratsam. So programmierte ich einige parallele Sortieralgorithmen.

Ansonsten kannst Du es mit vertauschter Reihenfolge der Threaderstellung und / oder mit Änderung ihrer versuchen.

Generell läßt sich Windows aber in bezug auf die Abarbeitung der Threads und Tasks kaum bis gar nicht hineinreden, und dementsprechend sind die Möglichkeit, da einzugreifen, äußerst begrenzt und nur "pseudo".

pzktupel · Hält's aus hier Beiträge: 129 Erhaltene Danke: 30

Hallo,
ich bin neu hier und habe mich mal hier angemeldet.

Durch eine Anfrage mit meinem kleinsten 1000-stelligen Primzahl-4-Tupel , hatte ich mir
2 Tage mühe gemacht um was zu programmieren, um bis n=999 alle zu finden.

Im Moment schafft mein Programm für jeden Exponenten in derselben Zeit ca. k= 300 000 000 000 / Stunde für 10^n + k abzusieben.... und das bei nur 1 Kern einer modernen CPU. Bei RYZEN wahrscheinlich bis 1 Billion pro Stunde.

Wollte ich nur mal erwähnen...

Gruß

cryptnex · Beiträge: 23 Erhaltene Danke: 5

pzktupel hat folgendes geschrieben :

Durch eine Anfrage mit meinem kleinsten 1000-stelligen Primzahl-4-Tupel , hatte ich mir
2 Tage mühe gemacht um was zu programmieren, um bis n=999 alle zu finden.

Wollte ich nur mal erwähnen...

Würdest Du den Quellcode zum Studieren hier veröffentlichen? Ich führe nur ungern Programme aus unbekannten Quellen auf meinem Rechner aus.

Viele Grüße

pzktupel · Hält's aus hier Beiträge: 129 Erhaltene Danke: 30

Ok, es ist Freebasiccode, mit C++ habe ich es nicht so.
Anmerkung aber: Das ist ein Ergebnis nach Jahren der Tüftellei. Auch ist dieser unübersichtlich.

Letzte Fassung:

markieren

FreeBASIC

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:

#INCLUDE "windows.bi"
#INCLUDE "vbcompat.bi" 
  

 DIM AS INTEGER i,j,C,COUNT,XX,TT,A,PP,QZ,U,RR ,CON , n ,maxP , STC
 DIM AS LONGINT Start,ST,STT
 DIM AS STRING FF,FF1,FF2,FF3
 DIM AS BYTE zaehler
 
 FF=CURDIR
 FF2=FF+"\primes.txt"
 FF3=FF+"\QuadR.txt" //Quelldatei der 4Tupel 101 bis 9699690 , welche ab 23 erst Teiler haben, sind 36855 Stück

 
 REDIM Q(36855) AS INTEGER
 REDIM QC(36855) AS INTEGER
 
 INPUT " - 10^n+.... - Exponent n";n
 INPUT "Start Milliarden";Start:Start=Start*1000000000
 INPUT "Stop  Milliarde ";ST:St=St*1000000000
 INPUT "Primzahlen ins Sieb ab 100000 bis 80 M";maxP
 maxP=INT (maxP/log(maxP)) // Abschätzung der Anzahl für maxP
 
 RR=1
 FOR J=1 TO n
 RR=(RR*10) MOD 96996900   // 10 ^ n MOD 96996900  = 10 Block a 9699690 wegen Rasterversatz 
 NEXT J
 
 Start= (Start \ 96996900) * 96996900 - RR <- siehe hier
 
 OPEN FF3 FOR INPUT AS #1  //einlesen der 4Tupel
 FOR C=1 TO 36855
 INPUT #1,A:Q(C)=A+8
 
 NEXT C
 CLOSE #1

 
 
 REDIM P(maxP) AS INTEGER   // einlesen der Primteiler bis maxP
 
 OPEN FF2 FOR INPUT AS #2
 FOR C=1 TO maxP
 INPUT #2,A
 P(C)=A
 NEXT C
 CLOSE #2
 REM Erstellung der RESTTABELLE
 
 REDIM R(maxP) AS INTEGER
 
 FOR I=1 TO maxP   // ermitteln der Resttabelle aller Primteiler für 10^n+Startwert, für Verschiebungsstart des Blockes nötig
 RR=1
 FOR J=1 TO n
 RR=(RR*10) MOD P(I)
 NEXT J
 R(i)=(RR+Start) MOD P(I)   // Der Restwert für 10^n+Start MOD Primteiler 
 NEXT I
  
 
 REDIM R2(maxP) AS INTEGER  // ersten 3000 Teiler Restwert für 96996900 Primteiler für die Unterblockverschiebung 9699690
 
 FOR I=1 TO 3000
 R2(I)=9699690 MOD P(I)
 NEXT I 
 
 FOR I=3001 TO maxP // ab 3001 Teiler Restwert für 96996900 Primteiler für die Unterblockverschiebung 96996900
 
 R2(I)=96996900 MOD P(I)
 NEXT I 
 
 REM ENDE
 
 REM Erstellung der RESTTABELLE 2  - 9699690 MOD P
 
 REM BEGIN SIEBEN
 CLS
 
 B0:
 STC=INT(Start/10^11) // Schnitt volle 100 Mrd Blöcke für paralelles PRPing mit PFGW.exe
 FF1=FF+"\"+STR(n)+"."+STR(STC)
 
 // Datei PFGW Style erstellung

 IF FILEEXISTS(FF1) THEN OPEN FF1 FOR APPEND AS #9 ELSE OPEN FF1 FOR OUTPUT AS #9
 
 PRINT #9,"ABC 10^";n;"+$a & 10^";n;"+$a+2 & 10^";n;"+$a+6 & 10^";n;"+$a+8"
 
 
 BEGIN:
 LOCATE 1,1:PRINT "10^";n;"+";Start
 
 REDIM F(96996900) AS BYTE  

 FOR zaehler=0 TO 9 // 10 mal 9699690 Block 
 
 FOR I=1 TO 36855  //Konstantes Feld Q - Feld für jeden Blockdurchlauf  in QC kopiert, weil im QC Feld  hier reduziert wird
 QC(I)=Q(I)
 NEXT I

 count=36855
 
 FOR i=1 TO 3000
 U=1
 XX=R(I)
 PP=P(i)
 
  
 WHILE u<count  // und das hier ist das Meisterstück ! REST (Primzahl bzgl Block ) MOD Primzahl
 soll hier 0,2,6, oder 8 sein, damit der 4er ungültig wird bei einer Bedingung 
 QZ=(QC(u) + XX ) MOD PP 
 IF QZ>8 THEN GOTO WEITER 
 IF QZ MOD 2 = 1 OR QZ=4 THEN GOTO WEITER // <10 und ungerade fallen auch raus
 QC(u)=QC(COUNT):COUNT-=1:u-=1 // Primärsieb ! Hole das letzte 4Tupel ins erste, wenn das 1. rausfällt, reduziere Anzahl der 4er im Block um 1
 WEITER:
 u+=1
 WEND
 
 R(I)=(R(I)+R2(I)) MOD PP // Errechne neuen Rest bei Blockverschiebung 9699690
 
  
 NEXT i
 
  
 

 // kopiere die übrigen in ein BYTE Feld der Größe 96996900 für weiteres Sieben, weil hier erstmals die 96996900 / Primteiler die Anzahl der Restkandidaten unterschreitet
F() ist das neue Siebfeld, der Endblock als Raster

 FOR j=1 TO count
    F(QC(j)+zaehler*9699690)=1
  F(QC(j)-2+zaehler*9699690)=1
  F(QC(j)-6+zaehler*9699690)=1
    F(QC(j)-8+zaehler*9699690)=1
 NEXT j
 

NEXT zaehler

// Siebe alle Primteiler ab der 3001. bis maxP wie gewohnt durch
 
 FOR i=3001 TO maxP
 U=1
 RR=P(i)-R(i)
 IF RR MOD 2= 0 THEN RR+=P(i)
 FOR j=RR TO 96996900 STEP P(i)*2
 F(j)=0
 NEXT j
 R(I)=(R(I)+R2(I)) MOD P(i)  // Auch hier die Restblock bzgl Primteiler bei Verschiebung Block 96996900
 
 NEXT i
 
 // Ausgabe aller übrigen 4er ab 41 in 30er Block aussuchen und in Datei fürs PRPing schreiben
 FOR i=41 TO 96996900 STEP 30
 IF F(i)=1 AND F(i+2)=1 AND F(i+6)=1 AND F(i+8 )=1 THEN PRINT #9,I+Start
 NEXT i
 
 
 STC=INT(Start/10^11)
 Start+=96996900
 IF START>ST THEN CLOSE #9:STOP
 // Prüft ob Datei abgeschlossen wird bei volle 100 Mrd
 IF INT(Start/10^11)>STC THEN CLOSE #9:GOTO B0
 
 GOTO BEGIN

Zusatz: Die Zahl 36855 ist die Anzahl aller 4 Tupel von 41+30k bis 96996900 , die Teiler ab 23 erst haben.
Diese werden aus einer fertigen Datei eingelesen.

Primzahlen bis 80 Mio werden auch eingelesen.
--------------
Baller gerade an 665 herum. Nach 8 Stunden 10^665+ ( 2 000 000 000 000 ) fast abgeschlossen, ohne Fund. Denke heute Abend wirds bei 2-5 Billionen was sein.

Moderiert von Th69: Code-Tags hinzugefügt

Gammatester · Beiträge: 328 Erhaltene Danke: 101

pzktupel hat folgendes geschrieben :

Ok, es ist Freebasiccode, mit C++ habe ich es nicht so.
Anmerkung aber: Das ist ein Ergebnis nach Jahren der Tüftellei. Auch ist dieser unübersichtlich.

Hallo und willkommen im Forum. Ich habe es auch nicht so mit C++ allerdings auch nicht mit Basic. Ich würde allerdings wetten, daß Dein Programm keine Primzahlen(-vierlinge) ausgibt, sondern nur mögliche Kandidaten aussiebt, Ich weiß zwar nicht genau, was der letzte Stand im Programm von user profile icon

Mathematiker und user profile icon

Horst_H ist, aber bisher war der schon einfache Fermat-Test für die Kandidaten der Flaschenhals.

Ist der angegebene Code nur ein Ausschnitt? Was ich nicht glaube wegen der Dateiausgabe. Oder wird die Dateiausgabe in ein eigentliche Primzahl-Testprogramm gefüttert?

Gruß Gammatester

pzktupel · Hält's aus hier Beiträge: 129 Erhaltene Danke: 30

Hallo,

ja richtig, der gibt keine Primzahlen 4er aus, sondern Kandidaten Quadrupel die mittels PFGW ( das schnellste Fermattestprogramm ) getestet werden müssen.
Die Ausgabe in die Datei ist PFGW - tauglich gestaltet. Eine 660 stellige Zahl wird in 1/100 s getestet. Wäre sinnlos was anderes zu nehmen, gerade für hohe n. Das Programm, wer es kennt, hat 15 Jahre Entwicklung hinter sich.
Habs soweit, dass alle pfgw.logs nebenbei im Prozess in Abständen automatisch ausgelesen werden und bei 4-Tupel gibts ne Voiceausgabe "4 Tupel gefunden" :-)

Der Code ist der komplette Algorithmus.

Wegen n=665 : mittlerweile bald 3500 Mrd Offset fertig gesiebt und 2300 Mrd Offset abgesucht. Man sieht also den Fortschritt zum letzten Post - Zeitpunkt diesbezüglich.
Fang bald an den 4. Billionenblock zu sieben. 12h ca. 3000 Mrd. auf einem Phenom II X6 2.8 Ghz.

Gammatester · Beiträge: 328 Erhaltene Danke: 101

pzktupel hat folgendes geschrieben :

Hallo,

ja richtig, der gibt keine Primzahlen 4er aus, sondern Kandidaten Quadrupel die mittels PFGW ( das schnellste Fermattestprogramm ) getestet werden müssen.
Die Ausgabe in die Datei ist PFGW - tauglich gestaltet. Eine 660 stellige Zahl wird in 1/100 s getestet.

Danke für die Info. (Blödsinn der gestrichen wurde). Ich habe PFGW noch nie benutzt: Was wird den außer dem Fermattest noch verwendet? (MPArith mit BPSW braucht ca 400 ms für x)

Gruß Gammtester

pzktupel · Hält's aus hier Beiträge: 129 Erhaltene Danke: 30

Also das glaub ich jetz nicht mit 0,05 ms=0,0005s oder 2000 Stück pro Sekunde auf einem Kern. PFGW macht den Fermattest. 100 pro Sekunde. Intel doppelt so viele.

Bin da jetzt nicht im bilde. PFGW gibt aus, ob es sich um eine wahrscheinliche Primzahl handelt, gibt also aus ob 3^n mod n=3 ist oder nicht.

Wenn das 0.05ms braucht, was stellt den der dann fest bei einer Zahl ?

Gammatester · Beiträge: 328 Erhaltene Danke: 101

pzktupel hat folgendes geschrieben :

Also das glaub ich jetz nicht mit 0,05 ms=0,0005s o

Richtig. Habe auf die Schnelle die zwei Parameter für spsp(x,2) im TCalc-Rechner vertauscht, korrekt sind dann 120 ms. Mein Edit hat sich mit Deinem Beitrag überlappt.

pzktupel · Hält's aus hier Beiträge: 129 Erhaltene Danke: 30

Gammatester hat folgendes geschrieben :

pzktupel hat folgendes geschrieben :

Also das glaub ich jetz nicht mit 0,05 ms=0,0005s o

Richtig. Habe auf die Schnelle die zwei Parameter für spsp(x,2) im TCalc-Rechner vertauscht. Mein Edit hat sich mit Deinem Beitrag überlappt.

Also wäre PFGW 12-20 mal fixer (wegen intel vs AMD geschätzt) ? ( 1/0.4 und 1/0.01)

Wegen PFGW. Da gibt es nix schnellers. Jeder kennt Prime95 , genau diese Code ist dort enthalten.

Gammatester · Beiträge: 328 Erhaltene Danke: 101

pzktupel hat folgendes geschrieben :

Also wäre PFGW 40 mal fixer ? ( 1/0.4 und 1/0.01)

Richtig, aber umso interessanter wäre zu wissen, was PFGW wirklich macht, eine spsp(x,3) braucht auch ca 110 ms bei mir,

pzktupel · Hält's aus hier Beiträge: 129 Erhaltene Danke: 30

Gammatester hat folgendes geschrieben :

pzktupel hat folgendes geschrieben :

Also wäre PFGW 40 mal fixer ? ( 1/0.4 und 1/0.01)

Richtig, aber umso interessanter wäre zu wissen, was PFGW wirklich macht, eine spsp(x,3) braucht auch ca 110 ms bei mir,

PFGW gibt aus, ob es sich um eine wahrscheinliche Primzahl handelt oder zusammengesetzt, gibt also aus ob 3^n mod n=3 ist oder composite

Bsp.

10^ 665+2285465591911 is 3-PRP! (0.0190s+0.0001s)
10^ 665+2285465591911+2 is 3-PRP! (0.0194s+0.0043s)

Horst_H · Verfasst: Mo 04.09.17 18:35

Hallo,

nur sieben mit 300Mio/s ist ja schon recht schnell.
Sieben eines Zahlbereiches mit einer konstanten Anzahl an Primzahlen dauert auch nur eine konstante Zeit, egal wo ich da siebe.
Bei 30 Mio Siebprimzahlen sind es im Lazarusprogramm etwa 3,5 Sekunden für 460 Mio., also erheblich langsamer.
Aber weiter oben das Konsolenprogramm saust in 3 Sekunden durch 4e9 , aber die Übertragsbestimmung stimmt noch nicht, damit ich bei 10^1000 anfangen kann.

Gruß Horst

Mathematiker · Verfasst: Mo 04.09.17 18:57

Hallo,
darf ich noch einmal auf mein Problem www.entwickler-ecke.....php?p=708452#708452 zurückkommen.

Ich habe versucht den Absturz zu lokalisieren.
Konkret: Ist ein Zugriff aus dem 2.Thread auf das Programmformular; hier eine Ausgabe in die Listbox, überhaupt gestattet?
Ich vermute nicht und habe es jetzt herausgenommen. Scheinbar läuft es jetzt stabil. Den Quelltext habe ich aktualisiert.

Da ich mit mehrfachen Threads keine Ahnung habe, hoffe ich, ihr seht mir die vielleicht blöde Frage nach.

Danke
Steffen

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein

pzktupel · Hält's aus hier Beiträge: 129 Erhaltene Danke: 30

Da hab ich keinen Schimmer, was in der Konsole passiert

Anbei, nach unter 15h konnte ich die beast-number knacken UND wie der Teufel so will, auch noch das kleinste 5-Tupel !!!

n=666: 10^665+2969689524331 +d,d=-4,0,2,6,8 sind PRPs !!!

pzktupel · Hält's aus hier Beiträge: 129 Erhaltene Danke: 30

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:

procedure PrimSieben;
var
  i,p: NativeInt;
Begin
  fillchar(PrimSieb,SizeOf(PrimSieb),Ord(true));
  p := 2;
  repeat
    i := p*p;
    while i <= High(PrimSieb) do
    Begin
      PrimSieb[i] := false;
      inc(i,p);
    end;
    repeat
      inc(p);
    until PrimSieb[p]
  until (p*p) >High(PrimSieb);
end;

Ich habe mich mal eingelesen.
Warum nicht standard auf false lassen und Elemente auf True ?
P:=3 beginnen und i=p*p+2*P , und inc (i,2*p)
PrimeSieb[i]=True setzen

p=p+2
und dann prüfen, ob p Teiler wie 3,5,7 hat, aber selbst nicht 3,5,7 ist, dann zurück und p=p+2 wie bei 9,15,21, usw
IF p=p then PrimeSieb[p]=false

Das Auslesen der Primes in ein extra Feld und zwar alle ungeraden ab 3 + 2i,oder gleich ab 23+2i

Moderiert von Th69: Delphi-Tags hinzugefügt

Horst_H · Verfasst: Mo 04.09.17 20:00

Hallo,

das primsieben ist doch auf die simpelste Art, weil es die Laufzeit kaum berührt.
Bei 4e9 muss doch nur bis 63245 gesiebt werden.
Das "große" Sieb sucht 100Mio Primzahlen in 1,4 Sekunden, aber das wird ja auch nur einmal bei den zig Stunden Suche gebraucht.
Ich habe jetzt mal mit diesen Zahlen ab dem ersten Vielfachen der Primzahl nach Quadrupeln sieben lassen.
Jetzt 2,7 Sekunden.

@ user profile icon

Mathematiker:
Ich meine gelesen zu haben , dass man auf VCL-Sachen nur über synchronize oder siehe delphi Wiki zugreifen kann.

Gruß Horst

pzktupel · Hält's aus hier Beiträge: 129 Erhaltene Danke: 30

Nehme ( nur zur Information ) n=999, 10^998+...

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme