👩‍🎤 🤠 👵🏻 Milliarden einfacher Zahlen schneller heraussieben als Wikipedia 👩🏼‍🔧 🤲🏾 😜

( Abbildung Quelle )

Es ist bekannt, dass das Sieb des Eratosthenes (RE) einer der ältesten Algorithmen ist, die lange vor der Erfindung der Computer erschienen sind. Daher könnte man denken, dass dieser Algorithmus im Laufe der Jahrhunderte auf und ab untersucht wurde und nichts hinzugefügt werden kann. Wenn Sie sich Wikipedia ansehen, gibt es ein Meer von Verweisen auf maßgebliche Quellen, in denen Sie leicht ertrinken können. Daher war ich überrascht, als ich neulich versehentlich entdeckte, dass die Option , die auf Wikipedia als optimal dargestellt wird, erheblich optimiert werden kann.

Es war so. In einer Diskussion eines Artikels über funktionale Programmierung (FP) stellte er eine Frage : Wie schreibe ich RE in diesem Paradigma? Ich habe mehr als nur geringe Kenntnisse über AF und wage es nicht, die Antworten zu beurteilen, aber andere Diskussionsteilnehmer lehnten einige der vorgeschlagenen Lösungen sofort ab, was darauf hinweist, dass anstelle der theoretischen Komplexität

$O (n \ log \ log n)$ (1)

Die vorgeschlagene Implementierung wird rechenintensiv sein

$O (n ^ 2 / \ log n)$ (2)

und dass Sie bei dieser Komplexität nicht warten können, wenn beispielsweise 10 Millionen Nummern gesiebt werden. Ich wurde interessiert und versuchte, die optimale Version gemäß Wikipedia mit der üblichen prozeduralen Programmierung zu implementieren. In Delphi-7 habe ich den folgenden Code erhalten:

Listing 1

program EratosthenesSieve; // Sieve of Eratosthenes {$APPTYPE CONSOLE} uses SysUtils, DateUtils,Math; const version ='1.0.1d1'; N = 1000000000; // number of primes var sieve : array [2..N] of boolean; // false if prime t0, t1,dt : TDateTime; O,C : Extended; procedure init; var i : integer; begin for i:=2 to n do sieve [i] := false; end; //init procedure calc (start : integer); var prime, i : integer; breakLoop, exitProc : Boolean; begin prime := start; exitProc := false; repeat // find next prime prime := prime+1; while (prime<N) and sieve[prime] do inc (prime); i:= sqr(prime); // delete if i<= N then begin breakLoop := false; repeat if i<= N then begin sieve [i] := true; inc (i,prime); end else // if i<= N breakLoop := true; until breakLoop; end else // if prime+prime<= N exitProc := true; until exitProc; end; //calc procedure print; var i :integer; found : integer; begin found := 0; for i:=2 to N do if not sieve [i] then begin // write (i,', '); inc(found); end; writeln; writeln ('Found ',found,' primes.'); end; // begin // program body writeln ('Sieve of Eratosthenes version ', version); writeln('N= ',N); init; t0 := now; writeln('Program started ',DateTimeToStr(t0)); t0 := now; calc (1); t1 := now; writeln('Program finished ',DateTimeToStr(t1)); dt := SecondSpan(t1,t0); writeln ('Time is ',FloatToStr(dt),' sec.'); O := N* ln(ln(N)); C := dt/O; writeln ('O(N ln ln N)= ',O,' C=',C); O := sqr(N)/ln(N); C := dt/O; writeln ('O(N*N/ln N)= ',O,' C=',C); print; writeln ('Press Enter to stop...'); readln; end.

RE wird durch das Boolesche Siebarray mit inversen Werten dargestellt. Wenn die Zahl eine Primzahl ist, wird sie als falsch angezeigt, wodurch die Anzahl der Negationsoperationen (nicht) während des Siebens verringert wird. Das Programm enthält drei Verfahren: Initialisierung des RE-Init, Berechnungen (Durchsuchen und Durchstreichen von Zahlen im RE) - Berechnen und Drucken der als Ergebnis gefundenen Primzahlen - Drucken und Zählen der Anzahl der gefundenen Zahlen. Ich werde besonders auf die auskommentierte Ausgabe von Primzahlen im Druckverfahren hinweisen: Zum Testen bei N = 1000 wird der Kommentar entfernt.

Hier in der Berechnungsprozedur verwende ich die Wikipedia-Empfehlung: Löschen Sie für die nächste Primzahl i Zahlen aus dem RE

$i ^ 2, i ^ 2 + i, i ^ 2 + 2i, ...$

Dieses Programm hat in 17,6 Sekunden eine Milliarde Zahlen durchgesehen. auf meinem PC (3,4 GHz Intel Core i7 CPU).
Nachdem ich dieses Programm erstellt hatte, erinnerte ich mich plötzlich an die bekannten Eigenschaften von geraden und ungeraden Zahlen .

Lemma 1. 1) ungerade + ungerade = gerade; 2) ungerade + gerade = ungerade; 3) gerade + gerade = gerade.

Beweis

1)

$(2n + 1) + (2m + 1) = 2n + 2m + 2$ teilbar durch 2. TCD.
2)

$(2n + 1) + (2m) = 2n + 2m + 1$ ohne Rest nicht durch 2 teilbar. Chtd.
3)

$(2n) + (2m) = 2n + 2m$ teilbar durch 2. TCD.

Lemma 2. Das Quadrat einer ungeraden Zahl ist eine ungerade Zahl.
Beweis.

$(2n + 1) ^ {2} = 4n ^ {2} + 4n + 1$ ohne Rest nicht durch 2 teilbar. Chtd.

Bemerkung. Eine Primzahl größer als 2 ist ungerade.

Daher können Sie nur ungerade Zahlen löschen:

$i ^ 2, i ^ 2 + 2i, i ^ 2 + 4i, ...$ (3)

Aber zuerst müssen Sie alle geraden Zahlen streichen. Dies erfolgt durch eine modifizierte Initialisierungsinitialisierungsprozedur.

Listing 2:

 program EratosthenesSieve; // Sieve of Eratosthenes {$APPTYPE CONSOLE} uses SysUtils, DateUtils,Math; const version ='1.0.1d1'; N = 1000000000; // number of primes var sieve : array [2..N] of boolean; // false if prime t0, t1,dt : TDateTime; O,C : Extended; procedure init; var i : integer; begin for i:=2 to n do sieve [i] := not odd(i); end; //init procedure calc (start : integer); var prime,prime2, i : integer; breakLoop, exitProc : Boolean; begin prime := start; exitProc := false; repeat // find next prime prime := prime+1; while (prime<N) and sieve[prime] do inc (prime); // i:= prime*prime; i:= sqr(prime); prime2 := prime+prime; // delete if i<= N then begin breakLoop := false; repeat if i<= N then begin sieve [i] := true; inc (i,prime2); end else // if i<= N breakLoop := true; until breakLoop; end else // if prime+prime<= N exitProc := true; until exitProc; sieve [2] := false; end; //calc procedure print; var i :integer; found : integer; begin found := 0; for i:=2 to N do if not sieve [i] then begin // write (i,', '); inc(found); end; writeln; writeln ('Found ',found,' primes.'); end; // begin // program body writeln ('Sieve of Eratosthenes version ', version); writeln('N= ',N); init; t0 := now; writeln('Program started ',DateTimeToStr(t0)); t0 := now; calc (2); t1 := now; writeln('Program finished ',DateTimeToStr(t1)); dt := SecondSpan(t1,t0); writeln ('Time is ',FloatToStr(dt),' sec.'); O := N* ln(ln(N)); C := dt/O; writeln ('O(N ln ln N)= ',O,' C=',C); O := sqr(N)/ln(N); C := dt/O; writeln ('O(N*N/ln N)= ',O,' C=',C); print; writeln ('Press Enter to stop...'); readln; end.

Dieses Programm arbeitete 9,9 Sekunden lang. - Fast doppelt so schnell.

Um die Entsprechung des Echtzeit-Programmbetriebs mit der Theorie zu beurteilen, schlug ich dies vor

$dt = C * O,$

$dt$ - gemessene Betriebszeit;

$C$ - konstant mit der Dimension der Zeit;

$O$ - theoretische Bewertung.

Von hier aus berechnet

$C$ zu bewerten (1) und (2). Für

$N = 10 ^ 6$ und weniger

$dt$ nahe Null. Deshalb bringe ich die Daten auf das erste Programm für große

$N.$

$N$	(1)	(2)
$10 ^ 7$	$1.69 \ cdot 10 ^ {- 9}$	$2.74 \ cdot 10 ^ {- 9}$
$10 ^ 8$	$5.14 \ cdot 10 ^ {- 9}$	$1.47 \ cdot 10 ^ {- 8}$
$10 ^ 9$	$5.80 \ cdot 10 ^ {- 9}$	$1.29 \ cdot 10 ^ {- 7}$

Wie wir sehen, liegt die Schätzung (1) viel näher an den tatsächlichen Ergebnissen. Für das zweite Programm wird ein ähnliches Bild beobachtet. Ich bezweifle sehr, dass ich Amerika mithilfe der Sequenz (3) entdeckt habe, und ich werde sehr dankbar sein für die Verknüpfung mit der Arbeit, in der dieser Ansatz angewendet wurde. Höchstwahrscheinlich sind die Wikipedia-Autoren selbst in einem Meer von Informationen über den elektronischen Krieg ertrunken und haben diese Arbeit verpasst.

PS Für den Wikipedia-Algorithmus mit "linearer Laufzeit" siehe

Milliarden einfacher Zahlen schneller heraussieben als Wikipedia

More articles: