Sehr schneller Primzahl-Finder

[GTA-Place]

Auch euch will ich meinen Source nicht vorbehalten:

Delphi-Quellcode:

function Prim(Zahl: Cardinal): Boolean;  
var  
  Teiler: PCardinal;  
  Wurzel: Cardinal;  
begin  
  Result := True;    // Result = True  
  if not odd(Zahl) OR (Zahl <= 5) then    // Ist die Zahl nich ungerade oder kleiner als 5, dann  
  begin  
    if (Zahl <> 2) AND (Zahl <> 3) AND (Zahl <> 5) then    // Ist die Zahl nicht 2 und nicht 3 und nicht 5, dann  
      Result := False;    // Result = False  
    Exit;                 // Exit  
  end;  
  Teiler := @PrimS[0];    // Teiler = @PrimS[0]  
  Wurzel := Trunc(sqrt(Zahl));    // Wurzel aus der Zahl  
  while Teiler^ <= Wurzel do    // Solange Teiler^ <= Wurzel ist, mache  
  begin      
    if Zahl mod Teiler^ = 0 then    // Ist Zahl / Teiler^ = Rest 0, dann  
    begin  
      Result := False;    // Result = False  
      Break;    // Break  
    end;  
    Inc(Teiler);    // Teiler erhöhen um 1  
  end;  
end;

Delphi-Quellcode:

procedure TMainForm.StartButClick(Sender: TObject);  
var  
  Start, Ende: Real;  
  Z: PCardinal;  
  X, LPrim: Cardinal;  
  PrimF: TStringList;  
begin  
  try  
    Von := StrToInt(VonEdit.Text);    // Start  
    Bis := StrToInt(BisEdit.Text);    // Endwert  

 
    if Bis > 10 then  
      SetLength(PrimS, Trunc(0.4*Bis-(Bis/4)))    // Größe des Array: 0.4*Bis-(Bis/4)  
    else  
      SetLength(PrimS, 4);  

 
    LPrim := 0;    // Letze Prim = 0  
    Z := @PrimS[0];     // Gefundene Prims = 0  

 
    if (Von >= 0) AND (Bis >= 0) AND (Von < Bis) then    // Von >= 0; Bis >= 0; Von < Bis;  
    begin  
      Start := GetTickCount;    // Start-Zeit  

 
      for X := Von to Bis do    // Schleife: Startwert -> Endwert  
      begin  
        if Prim(X) then    // Funktion ausführen, wenn Prim dann  
        begin  
          Z^ := X;    // Prim in Array schreiben  
          Inc(Z);    // Z erhöhen um 1  
          LPrim := X;    // Letze Prim = X  
        end;  
        if X mod 20000 = 0 then    // Wenn X : 20.000 = Rest 0, dann  
        begin  
          Application.ProcessMessages;    // Anwendung aktualisieren  
          PrimLab.Caption := 'Aktuelle Primzahl: ' + IntToStr(LPrim);    // Akt. Primzahl anzeigen  
        end;  
      end;  

 
      Ende := GetTickCount;    // End-Zeit  
      DauerLab.Caption := 'Diese Überprüfung hat ' + FloatToStr((Ende - Start) / 1000) + ' Sekunden gedauert.';    // Dauer anzeigen  

 
      PrimLab.Caption := 'Speichern...';    // "Speichern..." anzeigen  

 
      Z := @PrimS[0];    // Z auf 0 stellen  
      PrimF := TStringList.Create;    // Stringlist erzeugen  

 
      for X := 0 to Length(PrimS)-1 do    // Von 0 bis Größe des Array  
      begin  
        if Z^ = 0 then    // Wenn Z^ = 0, dann  
          Break;    // Break  
        PrimF.Add(IntToStr(Z^));    // Prim in Stringlist schreiben  
        Inc(Z);    // Z erhöhen um 1  
      end;  

 
      PrimF.SaveToFile('Prim.txt');    // Stringlist speichern  
      PrimF.Free;    // Stringlist freigeben  

 
      PrimLab.Caption := 'Aktuelle Primzahl: ' + IntToStr(LPrim);    // Akt. Primzahl anzeigen  
    end  
    else  
      ShowMessage('Ungültige Eingabe(n)!');    // Bei falschen Eingaben, Nachricht anzeigen  
  except  
    ShowMessage('Es ist ein Fehler aufgetreten!');    // Wenn Fehler auftritt, Nachricht anzeigen  
  end;  
end;

Das Programm überprüft 10.000.000 Zahlen in erstaunlichen 6 Sekunden.
Und das Speichern geht so schnell, dass man "Speichern..." gar nicht sieht.

[negaH]

@Kara:

Wusst ich's doch gerade als Frau kann ich dich da nicht verstehen. Die Frauen die ich in meinem Leben glücklicherweise näher kennen lernen durfte verhielten sich da anders.

Das ich nun gerade DICH so anmache hat im Grunde nicht's mit dir persönlich zu tuen. Schau mal wir "leben" hier in einer Community. Das bedeutet vorrangig erstmal das nach Möglichkeit alle Mitglieder dieser Community sozusagen selber ohne "Hilfe" von Aussen, erziehen und regulieren, also demokratisch sozusagen.

In jeder solchen "Demokratie" ist Kritik erwünscht und eine freie öffentliche Diskussion eine Notwendigkeit.

Das ich nun DICH so persönlich kritisiert habe könnte man auch als Zurechtweisung, erzwingen von Respekt, oder auch nur als "Exempel statuieren" betrachten. Aus meiner persönlichen Sicht ging es mir priori aber nur darum dir zu sagen: "mit mir so nicht !". Es ist also nicht auf deine Person ansich zu beziehen, sondern eher ein Beispiel dafür WO alle anderen hier im Forum bei MIR die Grenzen zu ziehen sind. Und gerade weil ich eben keine Unterscheidung in solchen Dingen zwischen Mann und Frau mache, darf man meine Kritiken nicht persönlich betrachten.

EDIT:
Aber das sollte jetzt wirklich reichen, vergessen wir's einfach.

Gruß Hagen

[Phantom1]

Zitat von negaH:

und packt dies alles in eine einzigste Funktion, so dürfte ein Source rauskommen der zu deinem Source fast 1 zu 1 identisch ist.

Es verwundert mich eben schon weil ich damals definitiv im Netz keinen einzigsten Source finden konnte der dieses 8/30Comb Sieb implemntierte. Meine Referenz war ein PostScript von D.J.Bernstein, eine mathematiche Abhandlung über dieses Sieb.

Ich möchte hiermit nochmal darauf hinweisen, das ich wirklich nichts von deinem Code abgeschaut habe. Es steckt wirklich viel arbeit in meinem Code und ich werde ihn auch immer weiter optimieren, weil es mir ganz einfach spaß macht.
Anfangs hatte ich nur ein normales Sieb des Eratosthenes entwickelt und später mit einer einfachen Bitkomprimierung verbessert. Dann entdeckte ich folgende Internet-Seite: http://www.devalco.de/sieb_des_Ulam.htm und verbesserte daraufhin wieder mein Code, man braucht dazu nur logisches Denken (war relativ einfach). Vor kurzem las ich irgendwo im Internet das man den Speicher auch in kleinen Blöcken aufteilen kann (was für mich wesentlich komplizierter war als ich dachte, da hab ich echt das ganze Wochenende drann gesessen).

Es ist jedenfalls logisch, das es in unserem Code ähnlichkeiten gibt, da wir ja die gleichen strategien bzw methoden zur Berechnung der Primzahlen verwendet habe. Alles andere ist purer zufäll.

[negaH]

Zitat:

Es ist jedenfalls logisch, das es in unserem Code ähnlichkeiten gibt, da wir ja die gleichen strategien bzw methoden zur Berechnung der Primzahlen verwendet habe. Alles andere ist purer zufäll.

Nein, es war wirklich kein Vorwurf. Und selbst wenn du abgeschrieben hättest so heist das ja nur das du aus dem wissen anderer gelernt hast was ich grundsätzlich immer für gut empfinde.

Erstaunlich, und eben kein Zufall, ist aber der Punkt das man tatsächlich auf ähnlche Sourcen kommt.

In deinem Source sind mir ein par Dinge aufgefallen:
1.) du benutzt Fließkommaarithmetik, diese lässt sich beseitigen
2.) an einigen Stellen benutzt du Integer Arithmetik die sich idealerweise durch schnelle Shifts + Aditionen ersetzen lässt.

Du solltest jetzt versuchen auf Basis deines Source noch folgende Features einzuarbeiten:

1.) Berechnung Indexof(Primzahl)
2.) mit 1.) CountOfPrimes := IndexOf(Stop) - IndexOf(Start)
3.) zerlegung des Algos in zwei Teile -> a) Berechnung ob Primzahl ja/nein in Bit Array[] und b) daraus Berechnung der realen Primzahl. Somit benötigt man für 1.) und 2.) zu deren Berechnung nur noch Part a) und nicht mehr Part b)
4.) Initialisierung des Restesiebes mit beliebigem Startwert, statt immer mit 2 beginnend. Dadurch kann der Algo. bei beliebigen Zahlen beginnend anfangen zu scannen.
5.) eventuell das Sieb auf 2^64 erweitern,was aber schon wirklich schwieriger sein wird. Mein Source dazu liegt unfertig auf Halde

Gruß Hagen

[Phantom1]

Zitat von negaH:

2.) an einigen Stellen benutzt du Integer Arithmetik die sich idealerweise durch schnelle Shifts + Aditionen ersetzen lässt.

Ich wüsste nicht genau wie ich x div 30 vereinfachen könnte, wenn es x div 32 wäre könnte man ja einfach x shr 5 schreiben, aber bei x div 30 fällt mir irgendwie nichts ein

Ansonsten danke für die Tipps.

mfg
Phantom1

[negaH]

Ich rede ja auch nicht von "div 30" sondern "*30"

Delphi-Quellcode:

 PrimeBits:=PrimeLen*30; 
-->
 PrimeBits := (PrimeLen * 16 - PrimeLen) * 2;
-->
  asm
    LEA  EAX,[PrimeLen * 16 - PrimeLen]
    ADD  EAX,EAX 
  end;

Und "div 30" liese sich durch "*(1/30)" ersetzen. Allerdings sollte man so'nen Aufwand wirklich nur in den innersten Schleifen treiben.

Gruß hagen

[negaH]

Delphi-Quellcode:

 for i:=0 to Trunc(Sqrt(PrimeBits)/30) do  
    for j:=0 to 7 do  
      if PrimesLUT[i] and (1 shl j)=0 then begin  
        s:=STEMPEL[j];  
        Num:=i*30+s;  
        Num2:=Num*Num;  
        mbit:=Num2 mod 30;  
        m:=(Num2-mbit) div 30;  
        while m<PrimeLen do begin  
          PrimesLUT[m]:=PrimesLUT[m] or MODS[mbit];  
          Inc(m, i);  
          Inc(mbit, s);  
          if mbit>29 then begin  
            Dec(mbit, 30);  
            Inc(m);  
          end;  
        end;  
      end;

ersetze in Num := i*30+s -> Num := ic + s; und ic inkrementierst du in der i Schleife mit +30.
So gäbe es bestimmt noch einige Stellen die succesive auf dies Art und Weise beschleunigt werden können.

Gruß Hagen

[negaH]

 PrimesLUT[m]:=PrimesLUT[m] or MODS[mbit]; MODs[mBit] := 1 shl mBit;

der Shift dürfte auf heutigen Rechnern schneller ausgeführt werden als eine Lookup Tabelle im Speicher.

Gruß Hagen

[negaH]

Delphi-Quellcode:

 for k:=0 to MaxPrime div PrimeBits do begin  
    FillChar(Primes[0], PrimeLen, 0);  
    for i:=0 to Trunc(Sqrt((k+1)*PrimeBits)/30) do

Sqrt(k+1); was wäre wenn k von Anfang an schon von 0 bis Sqrt(MaxPrime div PrimeBits) laufen würde ?
Die Schleife I würde dann von 0 bis (k * PrimeBits) div 30 laufen, richtig ?
Ergo: in der äußeren Schleife j würde der Endwert durch den Compiler nur einmalig berechnet und in der Schleife j entfällt die langsamme Fließkommaarithmetik komplett und wird durch viel schnellere Integer Arithmetik ersetzt.
Natürlich kannst du hier auch wieder einige Mul's einsparen.

Schau dir mal meinen Source genauer an. Er macht ja exakt das gleiche wie der deinige, kommt aber ohne Fließkommazahlen aus und benutzt weniger Divisionen.

1.) Fließkomma weg
2.) Divisionen raus
3.) Multiplikationen durch Shift+Adds ersetzen

So sollte deine Optimierungsstrategie sein.

Gruß Hagen

[Phantom1]

Zitat von negaH:

Und "div 30" liese sich durch "*(1/30)" ersetzen. Allerdings sollte man so'nen Aufwand wirklich nur in den innersten Schleifen treiben.

Aber man müsste doch das Ergebnis wieder mit Trunc abrunden, was doch letztendlich wieder langsamer wäre, oder?

Zitat von negaH:

MODs[mBit] := 1 shl mBit;
der Shift dürfte auf heutigen Rechnern schneller ausgeführt werden als eine Lookup Tabelle im Speicher.

Das geht leider nicht, da ich hierbei nur die zahlen 7,11,13,17,19,23,29 in das jeweilige Bit(0-7) umrechne und setzte, alle anderen Zahlen werden nicht berücksichtigt.

Zitat von negaH:

was wäre wenn k von Anfang an schon von 0 bis Sqrt(MaxPrime div PrimeBits) laufen würde

PrimeBits ist die anzahl der zahlen in einem Teilarray (64KB=1966080 zahlen). Dieses teilarray wird solange durchlaufen bis maxprime erreicht wurde. Wenn ich k jetzt nur bis zur Wurzel berechne, werden nicht mehr alle Zahlen berechnet.

Zitat von negaH:

Schau dir mal meinen Source genauer an. Er macht ja exakt das gleiche wie der deinige, kommt aber ohne Fließkommazahlen aus und benutzt weniger Divisionen.

Deinen Source hab ich mir bis jetzt noch nicht genauer anschauen können, du scheinst doch einige sachen anders gelöst zu haben und da muss ich mich erstmal reinversetzten. Wenn ich mehr Zeit habe, schaue ich mir den Code mal genauer an.

Was mich jedoch noch interessieren würde, ist wie du die 2,5 sek auf einen P4 1,5GHz gemessen hast? Ich komme da mit einem wesentlich schnelleren CPU auf schlechtere Resultate. Oder hab ich beim messen was falsch gemacht?

Delphi-Quellcode:

procedure TForm1.Button3Click(Sender: TObject);
var counter: TCounter; i,j: Cardinal;
begin
  counter:=TCounter.Create(RealTime);

  i:=primes.IndexOf(1, True);
  j:=primes.IndexOf(500000000, False);

  for i:=i to j do
    primes[i];

  caption:=floattostr(counter.Stop);
  counter.Free;
end;

mfg
Phantom1

[negaH]

probier mal:

Delphi-Quellcode:

procedure TForm1.Button3Click(Sender: TObject); 
var counter: TCounter; i,j: Cardinal; 
begin 
  counter:=TCounter.Create(RealTime); 

  i:=primes.IndexOf(1, True); 
  j:=primes.IndexOf(500000000, False); 

//  for i:=i to j do 
//    primes[i]; 

  caption:=floattostr(counter.Stop); 
  counter.Free; 
end;

Die tatsächliche "Umrechnung" der Bitarrays[] mit Primes[i] ist irrelevant, da die Bitarrays[] intern schon alle Informationen welche Zahlen Primzahlen sind enthalten.

Benutzt du wie in deinem Beispiel .Indexof(5Mio) UND .Primes[i] so misst du die Laufzeit des Algos. ZWEIMAL !

Also entweder so:

Delphi-Quellcode:

  StartCounter;
  Primes.IndexOf(5Mio, False);
  StopCounter;

was absolut ausreichend ist da die Bitarrays[] intern nur eine andere Darstellung der Primzahlen sind.
Oder so:

Delphi-Quellcode:

  StartCounter;
  I := 0;
  while Primes[i] < 5000000 do Inc(I);
  StopCounter;

alles andere wäre sozusagen unfair da du zweimal die Laufzeit des Algos misst.

Gruß Hagen