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.

[Phantom1]

Achso ist das...

Ich habe beide möglichkeiten mal getestet:
Primes.IndexOf(500Mio, False); ergab eine Zeit von 798ms

Delphi-Quellcode:

I := 0;
  while Primes[i] < 500000000 do
    Inc(I);

ergab eine Zeit von 2869ms

mfg
Phantom1

[alzaimar]

@negaH: Zunächst erstmal finde ich deinen Vorwurf des Kopierens ziemlich peinlich, und deine Ausführungen auch. Da Du bekannte Verfahren einsetzt, könnte man Dir auch den Vorwurf machen. Denn eins ist klar: Du _hast_ abgekupfert. Deine Auslassungen über angeblich 'unqualifizierte' Poster, die sich über deinen peinlichen (einseitigen) Streit über schnelle Algos lustig machen, entsprechen nicht wirklich Deinen Fähigkeiten, oder? Ich meine, sie hat Recht: Sieht wirklich so aus wie Längenvergleich... Deine Behauptung, es gäbe keinen Sourcecode für das 8/30 comb Sieb, kann ich zwar nicht nachvollziehen, aber auch egal. Vielleicht schaust Du mal unter 'Sieve of Atkin'. Im Wiki. Da gibts dann auch den Code. Sieht schon sehr verdächtig nach deinem Code aus. Fragt sich, wer zuerst da war

Im übrigen habe ich an diversen Stellen versucht, den Code von Phantom1 schneller zu machen: Komischerweise klappt das nicht mit den Foatingpoint-Berechnungen. Ich habe mir Einen abgebrochen, aber die Performance bricht immer um ca. 30% ein, wenn man hier was drehen will. Dessenungeachtet wird der Algorithmus von Delphi (bis auf die Berechnungen) fast optimal (was die Anzahl der ASM-Befehle anbelangt) kompiliert, sodass der Delphi-Code mit reinem Assembler vergleichbar ist. Ich hatte das mit anderen Mitstreitern hier in der DP an anderer Stelle mal durchexerziert: Mein normaler Delphi-Code war genauso schnell, wie hochoptimierter Assembler: Aufs Verfahren kommt es eben immernoch primär an.

Dann habe ich die redundanten Berechnungen rausgenommen (k*Primelen, k*Primebits, i*30 etc.). Ergebnis: 30% Performance-EINBRUCH. Vielleicht bin ich ja ein Kaschperl und einfach zu blöd dazu, und Du bekommst es besser hin... Ich habe mir bei dieser Diskussion hier jedenfalls angewöhnt, erst alles zu testen, bevor ich das Maul aufreisse.

Was man imho an Phantom1's Code noch verbessen könnte, sind die Zugriffe auf die Bit-Arrays. Hier wäre ein inkrementierender Pointer besser als die indirekte Offsetaddressierung über ein Array. Ich scheitere an der inneren While-Schleife und dem inc (m,i).

[Phantom1]

Zitat von alzaimar:

Was man imho an Phantom1's Code noch verbessen könnte, sind die Zugriffe auf die Bit-Arrays. Hier wäre ein inkrementierender Pointer besser als die indirekte Offsetaddressierung über ein Array. Ich scheitere an der inneren While-Schleife und dem inc (m,i).

Wie ich bereits im anderen Forum sagte ist das kein problem, jedoch wird der Code dadurch etwas langsamer. Macht aber nix, es gibt noch andere möglichkeiten den Code zu optimieren

mfg
Phantom1

[negaH]

@alzaimar:

damals gabs wikipedia nach garnicht. Das einzigste was ich finden konnte, durch einen Tipp eines anderen Programmierers, war die mathematiche Abhandlung von D.J.Bernstein. Mein oben geposteter Source ist nunmehr die dritte Neuimplementierung, die erste habe ich wohl vor 8-10 Jahren programmiert.
Der Source den man jetzt im Wiki findet ist ein C Code und ein Sieb bis 2^63 wie es scheint. Er arbeitet nach der Atkin's Methode, das ist richtig, aber denoch muß man in solchen Zahlenbereichen natürlich auch ganz andere Algorithmen benutzen. Mein Sieb arbeitet wie in D.J.Bersteins PostScript nur bis 2^32. Denoch danke für den Tipp, denn nun habe ich sogar eine Referenzimplementierung um mein gescheitertes 2^64 Sieb neu zu überprüfen.

Klar, auch ich habe _abgekupfert_, und wie ich oben geschrieben habe, muß jegliche Inmplementation des gleichen mathematischen Verfahres auf kurz oder lang ähnliche Muster aufweisen. Allerdings war ich denoch sehr überrascht das sich die finalen Umsetzungen sich so gleichen wie ein Ei sich dem anderen Ei gleicht.
_abgekupfern_ ist aber immer zweischneidig zu betrachten. Ich zb. habe mit Hilfe der doch relativ komplizierten mathematischen Abhandlungen von Bernstein die Sourcen komplett neu und selber geschrieben. Somit habe ich mir mathematisches Wissen angeeignet und meine eigene Implementierung geschrieben. Man kann aber eben auch _abkupfern_ indem man einen existenten Fremdsource nimmt und diesen als den eigenen ausgibt. Leider scheint dies heutzutage eben keine Ausnahme von der Regel zu sein, sondern eben umgekehrt.

Bisher, und es wäre schön wenn du mir das Gegenteil beweisen könntes, kenne und kannte ich eben keine einzigste PASCAL/Delphi Implementierung dieses Siebes.


@Penis-Längen-Vergleich: Ich wollte dieses Thema eigentlich abhacken, aber nun nochmal.
Es ist doch ein menschliches Bedürfnis sein Können unter Beweis zu stellen. Im grunde habe ich es nicht nötig hier meine Sourcen und ergo auch Zeit zu investieren. Der einzigste Grund warum ich dies tue ist damit andere Programmierer aus meinen Erfahrungen lernen können. Dafür kann ich einen gewissen Respekt erwarten.
Wie das Thema dieses Threads schon andeutet -> "Sehr schneller Primzahl-Finder" mit der inhaltliche Angabe eines normalen Sieb des Erstothenes ist es sehr wohl gerechtfertig darauf hinzuweisen das dies wohl einer der langsamsten Tests überhaupt ist. Als Beweis setze ich mich hin, entpacke und suche meine alten Source um hier dann diesen zu posten. In diesem Moment sind sehr wohl Laufzeitvergleiche sinnvoll. Also was gibts dagegen einzuwenden, wenn man fundiert die erzielte Effizienz vergleicht ?

Ich habe nun bei solchen Kommentaren drei Möglichkeiten zu reagieren:
1.) ich ignoriere es und verändere somit rein garnichts im Bewusstsein der Menschen
2.) ich ziehe mich hier aus der DP zurück und behalte mein Wissen für mich.
Allerdings geht so auch Wissen verloren das ehrlich Antwortsuchende eben nicht erhalten können. Schlußendlich kenne ich meinen Wissens- und Erfahrungsstand sehr genau und das was ich für mich persönlich damit erreichen wollte habe ich auch erreichen können. Aus dieser Sichtweise könnte es mir egal sein ob ich mein wissen für mich behalte oder hier mit anderen teile.
3.) ich reagiere selbstbewusst, argumentiere und hinterfrage die Intention des Störenfriedes. Ich setze ihm ganz öffentlich Grenzen, Grenzen die er überschritten hat. Ich mache dies dann aus mehreren Gründen, eben um deutlich zu zeigen "mit mir nicht !", um anderen zu zeigen wo diese Grenzen liegen, um andere anzuregen es mir gleichzutuen und ihre sozusagen gesellschaftliche Verpflichtung eines vernünftigen und respektvollen Umganges durchzusetzen.
Das mache ich dann absichtlich deutlich überzogen, denn sollte ich es nicht machen, so würden eben gerade die ehrlichen Leute die wirklich auf der Suche nach Wissen sind darunter leiden.

Eine Unterstellung eines "Penis-Vergleiches" erachte ich also als eine persönliche Beleidigung. So eine Unterstellung impliziert gleichermaßen das mein Wertemaßstab in meinem persönlichem Umgang mit Menschen und/oder meine Bewertung meiner Mitmenschen durch mich, ein Maßstab ist der rein garnichts mit deren Charakteren, Fähigkeiten, Fertigkeiten und Leistungen zu tuen hat. Er impliziert das ich ein Mensch bin dessen einzigster Maßstab den er an Menschen anlegt ein Maßstab ist der aus Sexuellen Neigungen, der Leistung des Autos oder der Anzahl der Frauen wäre, sprich also oberflächlich.

Zitat:

Dann habe ich die redundanten Berechnungen rausgenommen (k*Primelen, k*Primebits, i*30 etc.). Ergebnis: 30% Performance-EINBRUCH. Vielleicht bin ich ja ein Kaschperl und einfach zu blöd dazu, und Du bekommst es besser hin... Ich habe mir bei dieser Diskussion hier jedenfalls angewöhnt, erst alles zu testen, bevor ich das Maul aufreisse.

Das ist auch eine gute Idee, es so zu handhaben.
Meine obigen Vorschläge der Optimierungen sind auch nicht als Fakten und funktioneerende Lösungen zu betrachten, sondern einfach nur Vorschläge wie ich an die Sache noch herangehen würde.
Das es aber schneller geht ist unbestritten, es muß schneller gehen. FLoatingpoints sind immer langsammer als Integer Berechnungen, dies ist nunmal fakt wenn man sich die CPU Zyklen der heutigen CPU's genauer unter die Lupe nimmt. Erschwerend kommt hinzu das ein gemischter Code aus Integer/Floating-POint Berechnungen, oder zusätzliche Zugriffe auf Lookup Tabellen nachweislich die Gesamtperformance auf Grund von WaitStates, Cachemisses etc.pp. auf modernen CPU's negativ beeinflußen. Dies sind keine Weisheiten sondern bekannte Tatsachen. Ergo: sind mein Optimierungsvorschläge sehr wohl fundiert. Und das es schneller gehen kann zeigt ja mein eigener Source.

Gruß Hagen

[negaH]

@Phantom1:

Zitat:

Primes.IndexOf(500Mio, False); ergab eine Zeit von 798ms

Delphi-Quellcode:

  while Primes[i] < 500000000 do 
    Inc(I);

ergab eine Zeit von 2869ms

Gut. Probiere nun mal folgendes aus:

Delphi-Quellcode:

  J := Primes.IndexOf(500000000);
  I := Primes.IndexOf(400000000);

  StartCounter;
  while I < J do
  begin
    Primes[I];
    Inc(I);
  end;
  StopCounter;

Mache also eine Ausschnittsberechnung.

Der obige Unterschied ist erklärbar weil die Erzeugung der Bitarrays[] getrennt von der realen Berechnung der Primzahlen abläuft. Man muß sich nun die Frage gefallen lassen: "für was benötigt man nun alle Primzahlen kleiner 2^32?"

Für die Kryptrographie sind diese Primzahlen viel zu klein.
Für die mathematische Statistik/Zahlentheorie benötigt man nur die Information wieviele Primzahlen in einem Bereich existieren, also CountOfPrimes(Start, Stop).
Um eine beliebige Zahl < 2^32 auf Primzahl zu testen findet man in meinem Source ein viel schnelleres Verfahren.

Es gibt also im Grunde eigentlich keine richtig nützliche Anwendung für die vollständig berechneten Primzahlen. Das Sieb ansich ist wohl am sinnvollsten für die Zahlentheorie, aber dort benötigt man eben nicht die reale Primzahl sondern nur die Anzahl der Primzahlen innerhalb gewisser Bereiche.


Gruß Hagen

[Phantom1]

Zitat von negaH:

Klar, auch ich habe _abgekupfert_, und wie ich oben geschrieben habe, muß jegliche Inmplementation des gleichen mathematischen Verfahres auf kurz oder lang ähnliche Muster aufweisen. Allerdings war ich denoch sehr überrascht das sich die finalen Umsetzungen sich so gleichen wie ein Ei sich dem anderen Ei gleicht.
_abgekupfern_ ist aber immer zweischneidig zu betrachten. Ich zb. habe mit Hilfe der doch relativ komplizierten mathematischen Abhandlungen von Bernstein die Sourcen komplett neu und selber geschrieben. Somit habe ich mir mathematisches Wissen angeeignet und meine eigene Implementierung geschrieben. Man kann aber eben auch _abkupfern_ indem man einen existenten Fremdsource nimmt und diesen als den eigenen ausgibt. Leider scheint dies heutzutage eben keine Ausnahme von der Regel zu sein, sondern eben umgekehrt.

Bisher, und es wäre schön wenn du mir das Gegenteil beweisen könntes, kenne und kannte ich eben keine einzigste PASCAL/Delphi Implementierung dieses Siebes.

Das finde ich jetzt aber übertrieben, man braucht doch keine mathematischen Abhandlungen zu lesen oder bereits existierende SourceCodes kennen um so ein Sieb zu programmieren. Wenn man weiß wie das normale Sieb des Eratosthenes funktioniert, ergibt sich der Rest doch wie von selbst mit etwas logischen Denken. Ich sollte dazu sagen das ich jetzt auch schon seit über 10 Jahren programmiere (Hobby) und in Mathe immer recht gut war. Für den 30er Stempel habe ich zb nur diese WebSeite gelesen und daraufhin in meinem Code implementiert, das ist keine große sache. Ähnlich war es bei der Aufteilung der Primzahlen in Blöcken, da gibt es eigentlich nur die eine möglichkeit von rein logischem her, dazu braucht man nichts weiter wissen.

mfg
Phantom1

[negaH]

Zitat:

Das finde ich jetzt aber übertrieben, man braucht doch keine mathematischen Abhandlungen zu lesen

Naja, das hängt denke ich vom Arbeitsstil des Programmierers ab. Ich persönlich bevorzuge eben solche Abhandlungen, und wie ich oben schon sagte fand ich damals im WEB leider nichts brauchbares. Danke übrigens für den Link.
Das die Herleitung eines solchen Siebes im Grunde trivial ist musste ich auch erstmal feststellen. Aber, dazu gehört eben immer eine Lernphase und ich habe aus dem PostScript von D.J.Bernstein mein Wissen gelernt. Wenn es dir also leicht fällt sowas ohne fremde Hilfe selber zu entwicklen, tja dann hast'e Glück gehabt und kannst dich freuen. Ich persönlich musste halt härter dafür arbeiten

Gruß Hagen

[alzaimar]

@negaH: Gut, das wir nun alle auf dem Boden der Sachlichkeit angekommen sind. Sämtliche sachfremden Themen sind abgehackt. Eine Kleinigkeit noch: "C'est le tone, qui fait la musique" (oder so ähnlich)

Deine Ausführungen zur Optimierung sind theoretisch völlig klar. Ich hatte mich, wie erwähnt, rangesetzt und die Floatingpoint-Arithmetik durch reine Integer ersetzt, sogar den kompilieren Assembler überprüft. Danach hätte es einfach schneller sein _müssen_, verdammt. Aber isses nicht. Allerdings sind Lookup-Tabellen schneller, auch wenn es theoretisch nicht sein kann. Mit bedingten Sprunganweisungen war der Code von Phantom1 ca. 40% langsamer, als mit den Lookuptabellen: Hier brächte höchstens eine Sprungtabelle mehr, aber das geht imho in Delphi nicht.

Nur so, zum Ärgern : Die relevanten Teile deines Codes sind doch in Assembler, da kann man nicht mehr von PASCAL-Implementierung sprechen, oder? Egal, nur so..

@Phantom1: Soweit ich das gemessen habe, bringt die Implementierung von Pointern sehr wohl etwas, weil:

Delphi-Quellcode:

Var p : PByte; 
...
p := @PrimeBits[0];
...
While Foo do begin
  p^:= Bar; 
  inc (p);
  end;

empirisch gesehen schneller ist als:

Delphi-Quellcode:

i := 0;
While Foo Do begin
  PrimeBits[i] := Bar;
  inc (i);
  End;
...

[Phantom1]

Zitat von negaH:

Wenn es dir also leicht fällt sowas ohne fremde Hilfe selber zu entwicklen, tja dann hast'e Glück gehabt und kannst dich freuen.

Nunja ganz so leicht war es nicht, ich hab schon wirklich viele Stnden dran gesessen. Vom schwierigkeitsgrad ist es schon recht hoch, ähnlich wie diesen Code den ich vor einiger Zeit mal geschrieben habe.

Zitat von alzaimar:

Soweit ich das gemessen habe, bringt die Implementierung von Pointern sehr wohl etwas

Normalerweise schon, aber leider nicht hier. Ich hab das eben nochmal ausprobiert und der Code wurde dadurch langsamer, keine Ahnung warum

mfg
Phantom1

[GTA-Place]

Ja, hab auch schon Pointer ausprobiert. Wird immer nur langsamer.