Der Kiebartkamm - Siebverfahren Primzahlen

29.10.2021, 10:48

reinkie

Der Kiebartkamm - Siebverfahren Primzahlen

Dieses Siebverfahren wurde von mir entwickelt,
um möglichst schnell innerhalb eines gegebenen Bereiches (Grenze) Primzahlen zu finden.
Es ersetzt das Sieb des Eratosthenes und ist deutlich effizienter.

Beschreibung:
Man markiert (streicht) die 1 als Nichtprim (alle anderen Zahlen des Bereichs sind vorläufig Prim, außer sie werden gestrichen)

Streiche(1)
FOR P1 = 2 To Wurzel(Grenze)
IF IstDiesEineNochprimzahl(P1) Then
FOR P2 = P1 + 1 To Grenze
IF IstDiesEineNochprimzahl(P2)
Ergebnis = P1 * P2
IF Ergebnis > Grenze Then Exit For (Verlasse die innere Schleife)
Streiche(P1*P2)
END IF
NEXT P2
END IF
NEXT P1

Wenn dieses durchgelaufen ist, enthält dein Speicher (Bits oder Bytes) die Primzahlen und noch Quadratzahlen. Diese werden ebenfalls von der Wurzel(Grenze) beginnend gestrichen.

FOR P1 = Wurzel(Grenze) TO 2 STEP -1
IF IstDiesEineNochprimzahl(P1) Then Streiche(P1*P1)
NEXT P1

Ich bin bewusst in der ersten Schleife bei 2 gestartet, um das Streichen zu erklären. Anmerkung: Meine realisierte Lösung startet bei 7 (Siehe www.kiebart.de) Erstes gestrichene Produkt 7*11

Folgende Produkte werden gestrichen, wenn die erste Schleife bei 2 startet und die "Quadratschleife" bei 2 endet.
2*3, 2*4, 2*5, 2*6(wird nicht gestrichen, da 6 durch 2*3 schon gestrichen wurde), 2*7, 2*9, 2*11 usw.
Im 2. Durchlauf P1 = 3 werden folgende Produkte gestrichen:
3*4, 3*5, 3*7, 3*9, 3*11, 3*12, 3*13 usw.
P1 = 4 streicht
4*5, 4*7, 4*9, 4*11, 4*13, 4*16 usw.

Die entstehende Menge enthält alle Primzahlen des Bereichs, aber noch Quadratzahlen!

Diese werden in einer abwärtslaufenden Schleife ebenfalls gestrichen.

Anmerkung von mir: Es gibt kein anderes effizienteres Verfahren (Sieb), welches jede Nicht-Primzahl genau einmal streicht.

31.10.2021, 13:07

Malcang

Auf diesen Beitrag antworten »

RE: Der Kiebartkamm - Siebverfahren Primzahlen

Zitat:

Original von reinkie
Anmerkung von mir: Es gibt kein anderes effizienteres Verfahren (Sieb), welches jede Nicht-Primzahl genau einmal streicht.

Gibt es zu dieser Anmerkung eine fundierte Grundlage?
Ich wage nämlich zu bezweifeln, dass dein Verfahren eine Chance gegen das Sieb von Atkin hat.
Außerdem: Was verstehst du unter Effizienz?
Und wo wir dabei sind: Schlägt dein Verfahren das Sieb des Eratosthenes denn zumindest bezüglich Komplexität?

31.10.2021, 13:17

Malcang

Auf diesen Beitrag antworten »

Ich muss ein weiteres Mal einhaken, auch wenn es nicht zu dem hier besprochenen Thema gehört.
Du Schreibst auf deiner Seite

Zitat:

Im Internet fand ich eine Organisation www.mersenne.org, die auf der ganzen Welt Computerkapazität suchte, um weitere Mersenneprimzahlen zu finden. Da die besonders großen Exemplare für Verschlüsselungsmechanismen wertvoll sind, sind hier auch Preise von über 100 Tausend Dollar Finderlohn ausgesetzt. So sind Tausende von Computern auch jetzt, wenn Sie diesen Text lesen, damit beschäftigt, neue Mersenneprimzahlen zu finden.

Erstens sind die Preise nicht im 100.000$-Bereich, sondern bei schlappen 5.000$ oder weniger.
Zweitens -und das ist der wichtige Punkt- werden die "besonders großen" Exemplare gerade nicht für Verschlüsselungen eingesetzt. Das wäre ziemlich daneben, denn der Schlüssel liegt ja auf mersenne.org für jeden einsehbar, was eine darauf basierende Verschlüsselung ad absurdum führen würde.
Firmen unterhalten eigene Server mit riesigen Primzahlen, die sie für ihre Verschlüsselungen benutzen. Die dort befindlichen Primzahlen sind natürlich keine Mersenne-Primzahlen, sondern einfach "Primzahlen". Je weniger "Muster" sich in dieser Primzahl findet, desto besser.

31.10.2021, 14:40

HAL 9000

Auf diesen Beitrag antworten »

guter Einwand

Zitat:

Original von ichwarneu
Ich wage nämlich zu bezweifeln, dass dein Verfahren eine Chance gegen das Sieb von Atkin hat.

Kiebartkamm und diese winzige Variation hin oder her, es bleibt bei der Komplexität $\begin{eqnarray*} O(N\log\log N) \end{eqnarray*}$ des Eratosthenes-Siebs. Und das wird von den $\begin{eqnarray*} O(N) \end{eqnarray*}$ des Atkins-Siebes dann ganz sicher auf lange Sicht geschlagen. Wie groß $\begin{eqnarray*} N \end{eqnarray*}$ in einer realen Implementierung sein muss, damit sich dieser Langfristvorteil auch bei diesem konkreten endlichen $\begin{eqnarray*} N \end{eqnarray*}$ durchsetzt, bliebe zu untersuchen.

05.11.2021, 07:34

reinkie

Auf diesen Beitrag antworten »

Ich war einige Zeit und bin auch noch einige Zeit wegen einem Verdacht auf Schlaganfall außer Fecht gesetzt. Ich hoffe, ich bekomme noch einige Resultate in den nächsten Jahren hin. Ich finde das alles sehr spannend.

Meine Info mit den >100.000 Dollar stammt aus dem Netz und ich kann mir vorstellen, dass noch größere Summen ausgelobt werden für die Bereiche, in denen ich mich zur Zeit bewege. 300 Mio Stellen. Es ist eine Art Sieb (Nicht der Kiebartkamm!), welches Mersennezahlen siebt, indem es Teiler findet. Siehe anderer Thread. Ist natürlich zeitintensiver. Aber in meiner Datenbank sind schon über 33% der Mersennezahlen (mit einer Primzahl als 2er-Potenz) im Bereich von 2^1.000.000.000 bis 2^2.000.000.000 "ausgesiebt" worden. GIMPS betrachtet diesen Bereich noch nicht.

Richtig viel ist beim nächsten großen Milestone zu erwarten: 150.000 US-Dollar für eine verifizierte Primzahl mit mindestens 100 Millionen Stellen, ausgelobt von der Electronic Frontier Foundation.

Dies ist nicht bei GIMPS zu erreichen, weil dort das Geld irgendwie verteilt wird.

Das Sieb von Atkins werde ich programmieren und mit dem Kiebartkamm vergleichen. Es ist ja definitiv schneller als Eratosthenes. Zur Berechnung der Laufzeitkomplexität des Kiebartkamms fehlen mir die mathematischen Grundlagen. Ich werde allerdings ebenfalls meinen Nachhilfelehrer in Mathe und Physik zu diesem Thema befragen.
Ich werde weiterhin den Kiebartkamm und einen optimierten Eratosthenes in diesem Thread als VB.Net - Programm veröffentlichen.

Vielen, vielen Dank für eure bisherigen Anregungen.

05.11.2021, 09:11

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von reinkie
Es ist ja definitiv schneller als Eratosthenes.

Aufgrund der effizienten Speicherung der potentiellen Primzahlen ist er gemäß meinen Messungen ein bisschen schneller.

Das von dir propagierte "er ist schneller, weil er vorher nachschaut, ob der Siebeintrag auch wirklich upgedatet werden muss" ist nur dann zutreffend, wenn dieses Update signifikant mehr Zeit in Anspruch nimmt als das vorherige Nachschauen. In Single-Thread-Programmen kann ich das meiner Erfahrung nach nicht bestätigen.

In Multithread-Versionen dieses Algorithmus sieht es jedoch ein wenig anders aus: Um die Datenkonsistenz zu wahren zwischen den verschiedenen Threads, welche alle parallel dasselbe Sieb updaten wollen, muss die Update-Elementaroperation "AND-Maskierung eines Array-Bytes" unterbrechungsfrei ablaufen. Das ist bei einem gewöhnlichen C/C++Konstrukt "sieb[index] &= ~mask" nicht gewährleistet - die implementiert der Compiler meist als "Lesen in Register - maskieren - zurückschreiben", was in der Multithreading-Variante fatal ist: Wenn zwei Threads zufällig gerade auf dasselbe Byte zugreifen wollen, kann das schiefgehen - und es geht in der Realitat tatsächlich irgendwann schief (kann ich bestätigen). Daher verwende ich in dem Programm für diese Elementaroperation die speziell dafür vorgesehene Prozedur "_InterlockedAnd8" (MS Visual Studio), welche threadsicher ist. Aber die ist eine Nuance langsamer als die "unsichere" Variante.

Zitat:

Original von reinkie
Zur Berechnung der Laufzeitkomplexität des Kiebartkamms fehlen mir die mathematischen Grundlagen.

Wie gesagt, da sehe ich keine substanziellen Unterschiede zu Eratosthenes: D.h., deine Kiebartkamm-Methode mag vielleicht nur den $\begin{eqnarray*} k \end{eqnarray*}$ -fachen Aufwand des originalen Eratosthenes-Siebs haben, aber dieses $\begin{eqnarray*} 0<k<1 \end{eqnarray*}$ ist eher eine Konstante denn ein Wert $\begin{eqnarray*} k=k(N)\to 0 \end{eqnarray*}$ für $\begin{eqnarray*} N\to\infty \end{eqnarray*}$ . Somit bleibt es wie gesagt beim Aufwand $\begin{eqnarray*} O\left(N\log\log N\right) \end{eqnarray*}$ .

05.11.2021, 14:30

reinkie

Auf diesen Beitrag antworten »

Hallo HAL 9000,
es geht bei dem Kiebartkamm nicht um die effiziente Speicherung der Primzahlen.
Das Verfahren ist ein anderes gegenüber dem Eratosthenes.
In der äußeren Schleife durchläufst du die gesetzten Bits (NochPrim) und in der inneren Schleife die ebenfalls die gesetzten Bits (NochPrim), aber wichtig!!! ab dem nächsten Bit!
Also die erste Streichung ist nicht 7*7 sondern 7*11
7*11, 7*13, 7*17, 7*19, 7*23, 7*29, 7*31, 7*37, 7*41, 7*43, 7*47 und jetzt eben auch 7*49
usw.
Beim 2. äußeren Durchlauf (11) streichst du also zuerst 11*13, 11*17, 11*19, 11*23 .... aber auch 11*49 usw.
Die Quadrate der Primzahlen lasse ich also erstmal stehen.

Die äußere Schleife läuft bis zur Wurzel(Bereichsgrenze).

Wenn die äußere Schleife beendet ist, enthält dein Primzahlspeicher also noch Quadratzahlen.

Diese werden in einer 2.Schleife beginnend bei der Wurzel(Bereichsgrenze) bis zur 7 wieder für alle gesetzten Bits gestrichen.

Da und das ist ganz wichtig, bei dem Verfahren Kiebartkamm KEIN Bit 2mal getroffen wird,
kannst du statt mit OR/AND auch mit ADD oder SUB (Je nach Bedeutung der 0 oder 1) arbeiten.
Außerdem triffst du auch keine Lücke in den Modulo-30-Zahlen: 1, 7, 11, 13, 17, 19, 23, 29

Ich werde in 1-2 Tagen Zeit finden, diesen Code hier getestet und von mir für gut befunden, in VB.NET codiert, zu veröffentlichen. Eratosthenes + Kiebartkamm
Eratosthenes streicht bei mir allerdings als erstes die 49 und dann immer +14 weiter... und trifft während des weiteren Verfahrens auch viele Zahlen, die gar keine Primzahlen sein können, weil für diese keine Bits existieren.
Ich denke, dass die wenigen Multiplikationen des Kiebartkamms gegenüber den vielen Additionen des Eratosthenes zu diesem Zeitvorteil kommen. Durch einige kleine Arrays konnte ich die Multiplikationen minimieren/optimieren...
In Atkins muss ich mich noch (etwas) einarbeiten.

05.11.2021, 15:02

HAL 9000

Auf diesen Beitrag antworten »

Naja, es kommt womöglich drauf an, wie effizient du die Auswahl der Faktoren in

7*11, 7*13, 7*17, 7*19, 7*23, 7*29, 7*31, 7*37, 7*41, 7*43, 7*47

organisierst: Wenn du "weiter hinten", wo die Primzahlen dünner gesät sind, dann gleich mal ganze Nullbytes des Siebs (mit 8 Primzahlkandidaten, die schon erkannt keine Primzahlen sind) in einem Rutsch übergehen kannst, dann könnte ich mir einen Geschwindigkeitsgewinn vorstellen. Ansonsten sehe ich nicht, dass dein Verfahren weniger Operationen (wenn ich Nachschauen und Updaten als gleichwertig ansehe) aufweist als Eratosthenes.

Zitat:

Original von reinkie
kannst du statt mit OR/AND auch mit ADD oder SUB (Je nach Bedeutung der 0 oder 1) arbeiten.

Bringt nichts: Die Prozessoren kommen mit OR/AND genauso schnell zurecht wie mit ADD oder SUB. Und das erwähnte Zugriffsproblem besteht bei ADD/SUB genauso.

EDIT1: Noch eine Verständnisfrage zu deinem Verfahren: Nach dem ersten Durchlauf streichst du also auch noch alle Primzahlpotenzen $\begin{eqnarray*} p^{2k} \end{eqnarray*}$ mit $\begin{eqnarray*} p\geq 7 \end{eqnarray*}$ sowie $\begin{eqnarray*} k\geq 1 \end{eqnarray*}$ ? Weil so wie ich dein Verfahren oben verstanden habe, bleiben ja nicht nur die $\begin{eqnarray*} p^2 \end{eqnarray*}$ stehen, sondern auch $\begin{eqnarray*} p^4, p^6, \ldots \end{eqnarray*}$ , soweit sie noch ins Sieb passen.

EDIT2: Ich versuche immer noch zu verstehen, welche Zahlen denn GENAU übrig bleiben nach dem ersten Schritt deines Verfahrens. Wenn ich das richtig zusammengepuzzelt habe sind das alle Zahlen $\begin{eqnarray*} p^{2^k} \end{eqnarray*}$ für $\begin{eqnarray*} k=0,1,2,\ldots \end{eqnarray*}$ mit $\begin{eqnarray*} p \end{eqnarray*}$ prim. Alle anderen sollten rausfallen - selbst das von mir oben angenommene $\begin{eqnarray*} p^6 \end{eqnarray*}$ fällt doch noch raus, und zwar beim Streichen der Vielfachen von $\begin{eqnarray*} p^2 \end{eqnarray*}$ . Idee!

05.11.2021, 17:15

Finn_

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Daher verwende ich in dem Programm für diese Elementaroperation die speziell dafür vorgesehene Prozedur "_InterlockedAnd8" (MS Visual Studio), welche threadsicher ist.

[attach]53919[/attach]

Zur Nutzung atomarer Operationen existieren mittlerweile portable Schnittstellen, siehe stdatomic.h (C), atomic (C++), std::sync::atomic (Rust).

05.11.2021, 17:35

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Finn_
Zur Nutzung atomarer Operationen existieren mittlerweile portable Schnittstellen, siehe stdatomic.h (C)

Blöd nur, dasss Visual Studio 2019 zwar <atomic> für C++ kennt, den File "stdatomic.h" für die C-Unterstützung jedoch nicht. Augenzwinkern

----------------------------------------

Zitat:

Original von HAL 9000
Wenn du "weiter hinten", wo die Primzahlen dünner gesät sind, dann gleich mal ganze Nullbytes des Siebs (mit 8 Primzahlkandidaten, die schon erkannt keine Primzahlen sind) in einem Rutsch übergehen kannst, dann könnte ich mir einen Geschwindigkeitsgewinn vorstellen.

Bringt tatsächlich ganz schön was, fast Verdopplung der Performance.

Leider aber ist der Algorithmus schlecht entflechtbar in punkto Umwandlung in Multithreading:

D.h., der originale Eratosthenes mit 8 Threads bringt auf meinem Vierkerner dann immer noch die doppelte Performance wie der Single-Thread-Kiebart.

06.11.2021, 06:25

reinkie

Auf diesen Beitrag antworten »

Hallo HAL 9000. Bei diesem Einwand (Multithreading) gib ich dir vollkommen recht.
Eratosthenes lässt sich spitzenmäßig in mehrere (zig) Threads aufteilen.

06.11.2021, 06:54

reinkie

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000

EDIT1: Noch eine Verständnisfrage zu deinem Verfahren: Nach dem ersten Durchlauf streichst du also auch noch alle Primzahlpotenzen $\begin{eqnarray*} p^{2k} \end{eqnarray*}$ mit $\begin{eqnarray*} p\geq 7 \end{eqnarray*}$ sowie $\begin{eqnarray*} k\geq 1 \end{eqnarray*}$ ? Weil so wie ich dein Verfahren oben verstanden habe, bleiben ja nicht nur die $\begin{eqnarray*} p^2 \end{eqnarray*}$ stehen, sondern auch $\begin{eqnarray*} p^4, p^6, \ldots \end{eqnarray*}$ , soweit sie noch ins Sieb passen.

EDIT2: Ich versuche immer noch zu verstehen, welche Zahlen denn GENAU übrig bleiben nach dem ersten Schritt deines Verfahrens. Wenn ich das richtig zusammengepuzzelt habe sind das alle Zahlen $\begin{eqnarray*} p^{2^k} \end{eqnarray*}$ für $\begin{eqnarray*} k=0,1,2,\ldots \end{eqnarray*}$ mit $\begin{eqnarray*} p \end{eqnarray*}$ prim. Alle anderen sollten rausfallen - selbst das von mir oben angenommene $\begin{eqnarray*} p^6 \end{eqnarray*}$ fällt doch noch raus, und zwar beim Streichen der Vielfachen von $\begin{eqnarray*} p^2 \end{eqnarray*}$ . Idee!

Du brauchst nur von Wurzel(Grenze) bis 7 runter zählen und bei allen Bits, die noch auf Prim stehen, deren Quadrate streichen. Da ist auch 49^2 und 49^4 dabei.
Wenn das Streichen der Quadrate aufsteigend erfolgen würde, würde zwar 7^2 gestrichen werden, nicht aber 49^2
Tschuldigung für die späte Antwort.

Mit Atkins werde ich mich noch beschäftigen.

Danke, HAL 9000, dass du dir die Mühe gemacht hast, die Effizienz des Kiebartkamms nachzuvollziehen. Ob das Verfahren im Multithreading irgendwie möglich ist, damit werde ich mich noch beschäftigen. Momentan sieht es für mich nicht so aus.

Habt ihr vielleicht eine Formel für mich für das Laufzeitverhalten, damit ich Eratosthenes, Atkins und Kiebart vergleichen kann? Bei Eratosthenes und Atkins finde ich ja diese Formeln im Netz.

06.11.2021, 07:17

reinkie

Auf diesen Beitrag antworten »

Guten Morgen HAL 9000 und alle anderen Interessierten.

Im KK.EXE ist auch eine Art "Mersenneprimzahl-Sieb" programmiert.
Ich habe es im Matheboard unter dem Thread "Mersenneprimzahlen finden (Teilertest)" beschrieben. Ich suche immer noch nach effizienten Verbesserungen.

Bitte schaut auch mal da rein.

06.11.2021, 10:33

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von reinkie
Du brauchst nur von Wurzel(Grenze) bis 7 runter zählen und bei allen Bits, die noch auf Prim stehen, deren Quadrate streichen.

Ist schon klar. Meine Gedanken bezogen sich ja darauf, welche Zahlen das genau sind, die da gestrichen werden. Und das scheinen tatsächlich jene Potenzen $\begin{eqnarray*} p^{2^k} \end{eqnarray*}$ mit $\begin{eqnarray*} k\geq 1 \end{eqnarray*}$ zu sein.

Zitat:

Original von reinkie
Danke, HAL 9000, dass du dir die Mühe gemacht hast, die Effizienz des Kiebartkamms nachzuvollziehen.

Ja, allerdings sehe ich den entscheidenden Geschwindigkeitsschub wie gesagt darin, dass die Primzahlen "hinten" so dünn gesät sind, dass man beim Streichen sehr oft Kiebartkamm-Bytes in Gänze übergehen kann, weil sie Null sind: D.h., die zeitraubenden 8 Einzelbitüberprüfungen entfallen dann. Nach meinen Messungen ist DAS der entscheidende Beschleuniger.

Zitat:

Original von reinkie
Eratosthenes lässt sich spitzenmäßig in mehrere (zig) Threads aufteilen.

Ich hab mir auch Gedanken zur Parallelisierung deines Verfahrens gemacht: Es geht schon, aber anders:

Wenn man den zu untersuchenden Streichbereich für die Vielfachen ein- und dieselbe Primzahl $\begin{eqnarray*} p \end{eqnarray*}$ (bzw. in deinem Verfahren sind es die $\begin{eqnarray*} p^{2^k} \end{eqnarray*}$ ) geeignet aufteilt (muss nicht gleichmäßig sein, sondern vielleicht auch "intelligent", weil hinten ja weniger gestrichen wird), dann könnten die Einzelthreads diese Bereiche parallel bearbeiten. Dein Prinzip, dass jede Nichtprimzahl nur genau einmal gestrichen wird, ist dann zwar nicht mehr gewahrt, aber die Mehrfachstreichungen dürften sich in überschaubaren Grenzen halten.

Was nicht geht ist, dass verschiedene Threads parallel für verschiedene $\begin{eqnarray*} p \end{eqnarray*}$ streichen - da fallen dann wirklich einige Zahlen durch die Siebmaschen...

Neue Frage »

Antworten »

Der Kiebartkamm - Siebverfahren Primzahlen

Verwandte Themen