Sehr schneller Primzahl-Finder

[Nicodius]

ho viele Verschlüsselungsysteme bauen wie Luckie es sagt auf Primzahlen auf!

[Luckie]

Zitat:

Zitat von Luckie

In der Kryptologie spielen sie eine große Rolle zum Beispiel.

Zitat:

Zitat von Nicodius

ho viele Verschlüsselungsysteme bauen wie Luckie es sagt auf Primzahlen auf!

Hat das jetzt einen tiefern Sinn, dass du eine Stunde später das nachplapperst, was ich schon gesagt habe, ohne dem schon gesagten weiters hinzuzufügen?

[sakura]

Zitat:

Zitat von MagicAndre1981

Ich habe einfach die dsk und cfg - Datei gelöscht und schon konnte ich es öffnen. :-D

Ich werde das mal an die Borländer durchreichen :roll: Ist schon seltsam wie man so auf Bugs stößt...

...:cat:...

[sakura]

Zitat:

Zitat von Nicodius

wäre super qürdest du den code erklären sakura .. :)

Nicht wirklich gerne, suche mal im Internet nach dem Namen des Algorithmus: Sieb des Eratosthenes, der wird oft genug erklärt ;-)

...:cat:...

[Phantom1]

Ich habe eben auch nochmal einen neuen Code nach dem SIEB DES ERATOSTHENES geschrieben:

für 10 Mio testzahlen braucht mein Code etwa 0,65 Sekunden (ohne speichern)

Delphi-Quellcode:

procedure SavePrimes(MaxPrime: Cardinal; const FileName: String = '');    
var
  isPrime: Array of Boolean;
  Wurzel, i, j: Cardinal;
  SL: TStringList;
begin
  SetLength(isPrime, MaxPrime+1);
  FillChar(isPrime[2], Length(isPrime)-2, 1);
  Wurzel:=Trunc(Sqrt(MaxPrime));
  for i:=2 to Wurzel do
    if isPrime[i] then begin
      j:=i*2;
      while j<=MaxPrime do begin
        isPrime[j]:=False;
        Inc(j, i);
      end;
    end;

  if FileName<>'' then begin
    SL:=TStringList.Create;
    for i:=2 To MaxPrime do
      if isPrime[i] then
        SL.Add(IntToStr(i));
    SL.SaveToFile(FileName);
    SL.Free;
  end;
end;

[negaH]

:) ist alles relativ. Mein Primzahl Sieb erzeugt alle Primzahlen < 2^32 in 13 Sekunden auf einem P4 1,5MHz und erzeugt sogar noch eine Lookup Table von 630 Mb auf Platte. Das sind also 203.280.221 Primzahlen bis 4.294.967.296 in 13 Sekunden.

Wesentlich ist dabei was ganz anderes: Angenommen du sollst alle Primzahlen zwischen 1.000.000 und 2.000.000 berechnen dann würde dein Verfahren auch die Primzahlen < 1.000.000 berechnen müssen. Ein 8/30 Comb Sieb wie ich es benutze kann aber direkt diese Primzahlen berechnen.

Mal als Vergleich: alle Primes bis 10Mio auf einem P4 mit 1.5GHz werden in 60 Millisekunden berechnet.

Das Problem mit Eratosthenes ist das der Algorithmus enorm viel Speicher verbraucht wenn man bis 2^32 berechnen möchte. Das ist meistens so viel Speicher das der Algorithmus auf heutigen Rechnern inpraktikabel ist. Desweiteren muß der Algorithmus immer alle Primes von 2 angefangen berechnen umdie Nachfolgerprimes berechnen zu können. Eine Ausschnittsberechnung wie beim 8/30 Comb Sieve ist damit nicht möglich. Das Sieb selber verbraucht ca. 256Kb an Speicher.

Gruß Hagen

[dizzy]

Zitat:

Zitat von negaH

in 13 Sekunden auf einem P4 1,5MHz

Das is ne Leistung :mrgreen:

[gordon freeman]

Zitat:

Zitat von negaH

(...) Eine Ausschnittsberechnung wie beim 8/30 Comb Sieve (...)

Wo bekomme ich denn 'nen Code für so'n Comb Sieve? hab ma gegoogelt, aber nix gefunden....

thx, gordon

[negaH]

Gute Frage, ich weis das es im WEB Erklärungen zum Sieb gibt, aber wo kann ich dir auch nicht mehr sagen.Es handelt sich bei dem Algorithmus um ein Sieb das mit den Quadratischen Resten zu den kleinen Primzahlen bis 2^16 arbeitet. Es arbeitet also mit Modularen Ringen -> modulo. Dabei schreitet das Sieb die Zahlen in Schritten von 30 ab und führt dazu 8 Subsiebe zu den ersten Primzahlen mit deren quadratischen Resten mit. Dies ermöglicht es in 8 Bits 30 Zahlen zu speichern und erklärt so den geringen und linearen Speicherbedarf des Siebes. Da man eine Tabelle mit den Quadaratischen Resten direkt zu einem gewählten Startwert initialisieren kann, ist es nun auch möglich mit beliebigen Zahlenbereichen die Berechnungen zu beginnen.

Ich habe mal meinen Source angehngen. Er dient als Anschauung und darf nur mit meiner vorherigen Zustimmung weiterverbreitet werden.

Nun noch einige Erklärungen zum Source.

Die Basis stellt das Object TSmallPrimeSieve dar das immer über die Funktion "Primes" angesprochen werden sollte. Damit ist dieses Object und seine Daten global für die Anwendung verfügbar. Man kann aber auch eigene lokale Kopien erzeugen was aber dann bedeutet das durch die nötigen Neuberechnungen Performance verloren geht.

TSmallPrimeSieve enthält nun einige wichtige Methoden:

.Property Prime[Index]: Cardinal;
gibt die Primzahl mit Index zurück. Die Zahl 2 hat Index 0, 3 hat Index 1, 5 hat Index 2, 7 hat Index 4 usw. usw.

.IndexOf(Value: Cardinal): Cardinal;
berechnet zur Zahl deren Index als Primzahl. Falls Value selber keine Primzahl ist wird auf die vorhergehende oder nachfolgende Primzahl der Index berechnet (abhängig vom Parameter LowerBound).

.Count(LowerBound, UpperBound: Cardinal): Cardinal;
berechnet die Anzahl von Primzahlen die sich zwischen LowerBound und UpperBound befinden aus. Diese Methode berechnet intern nicht die realen Primzahlen was sie sogar noch schneller macht.

.BuildCache(const FileName: String; Bound: Cardinal);
erzeugt einen Lookup Tabelle in einer Datei die alle Primzahlen bis Bound enthält. Wird Bound auf MaxCardinal gesetzt (sprich alle Zahlen im maximalen Zahlenbereich des Siebes) so wird diese Datei ca. 630 Mb groß sein.

.LoadCache(const FileName);
Mit dieser Methode kann nun das Sieb so eingestellt werden das es eine Lookuptabelle benutzen kann. Damit werden random Zugriffe über .Count() / .Prime[] / IndexOf() usw. nochmals beschleunigt. Werden alerdings die Primzahlen/Berechnungen linear sequentiell benötigt dann lohnt ein Cache sich nicht. Die dynamische Berechnung der Primzahlen ist dann schneller als das Nachladen aus dem Cache.

Nun einige Beispiele:

Delphi-Quellcode:

  WriteLn( Primes.Count(10000000, 20000000) );  // Anzahl der Primzahlen zwischen 10-20 Mio berechnen
  
  I := Primes.IndexOf(10000000, False);                // Index der ersten Primzahl > 10 Mio berechnen
  J := Primes.IndexOf(20000000, True);                 // Index der letzten Primzahl < 20 Mio berechnen

  for I := I to J do                                  // Ausgabe der Primzahlen zwischen > 10Mio bis < 20Mio
    WriteLn( Primes[I] );

[KLS]

Also mein Primzahlenrechner braucht für den bereich 0-2.000.000.000 ganze 58,5s und ~121MB RAM.

Mein rechner hat 1GB ram und ist mit einem P4 (3GHz) ausgestattet.