Matroids Matheplanet Forum Index
Moderiert von Bilbo matph
Matroids Matheplanet Forum Index » Informatik » Sieb des Eratosthenes Algorithmus, Lösung
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Sieb des Eratosthenes Algorithmus, Lösung
Kajam
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2020
Mitteilungen: 264
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-09-12


Hallo,

kann mir jemand erklären, wie man die Lösung dieser Aufgabe verstehen soll? Wie liest man das?

Die Aufgabe lautet: Implementieren Sie den "Sieb des Eratosthenes" Algorithmus.

Lösung der Aufgabe:






Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2441
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-09-12


Der erste Teil der Programms siebt die Primzahlen und im zweiten Teil werden diese an die Konsole ausgegeben.

Was genau verstehst du denn nicht?


-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kajam
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2020
Mitteilungen: 264
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2020-09-12


Von wo bis wo geht der erste Teil des Programms? Und der zweite?

Vor allem verstehe ich nicht:

Was heißt denn "if (array[k]!=-1)" und "array[k]=1" sowie nochmal "array[t]=-1;" ???



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2441
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2020-09-12


Tipp:
Schlage die Operatoren in C/C++ nach.
(wikibooks oder beliebige Dokumentation)

Das bringt dir vermutlich mehr, als wenn es dir hier jemand im Einzelnen erklärt.


Ansonsten hilft es, solchen Code einfach mal selbst auszuprobieren und bspw. durch Ausgabe von Zwischenwerten zu analysieren.


-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 2372
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2020-09-12


Wenn deine Frage ist, was Arrays usw. sind, dann kann ich dem Einfältigen nur zustimmen.

Vielleicht ist dir aber auch nur nicht klar, dass in dem Array die Werte 1 bzw. -1 für "ist prim" bzw. "ist nicht prim" stehen sollen.
Das wäre vielleicht klarer, wenn der Autor bool statt int verwendet hätte.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kajam
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2020
Mitteilungen: 264
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2020-09-12


Was Arrays sind, ist mir schon klar.

Das mit dem "1" und "-1" spricht genau das an, was ich nicht verstehe.

Heißt das jetzt, dass z.B. beim "array[k]" alle "k´s" einfach Einsen sind? Egal, was ich für "k" einsetze? "k" geht in diesem Fall bis 120. Demnach sind alle k´s Primzahlen?

Aber das ergibt irgendwie keinen Sinn, wenn ich das zu verstehen versuche :/.

Ich versuche das gleich auszudrücken, was ich nicht verstehe.

Und "bool" haben wir noch nicht. Bekomme es erst nächste Woche oder so.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2441
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2020-09-12


2020-09-12 20:34 - Kajam in Beitrag No. 5 schreibt:

Heißt das jetzt, dass z.B. beim "array[k]" alle "k´s" einfach Einsen sind?

Das klingt aber nicht so, als wüsstest du, was Arrays sind?!?
a[k] greift auf das das k-te Element des Arrays zu. Mathematiker würden $a_k$ schreiben.


-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
AlphaSigma
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.11.2012
Mitteilungen: 223
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2020-09-12


Hallo Kajam,

die angebene Lösung ist in der Programmiersprache C verfasst.
C
int array[120];
definiert ein Feld mit 120 Werten, array[0] bis array[119]. Zu Beginn stehen da beliebige zufällige Integer-Wert darin. In der ersten for-Schleife wird array[i] auf -1 gesetzt, falls i keine Primzahl ist und auf 1, falls i eine Primzahl ist. Danach ist z.B. array[3] = 1 und array[4] = -1. In der zweiten for-Schleife wird geprüft, ob array[k] gleich 1 ist und nur dann "k ist eine Primzahl" ausgegeben.
C
if (array[k] != -1)
führt das folgende nur aus, wenn array[k] ungleich -1 ist.
C
if (t % k == 0)
prüft, ob t ohne Rest durch k teilbar ist (modulo-Operator)

Für eine Einführung in C siehe z.B.
C-Programmierung
oder
C-HowTo



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kajam
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2020
Mitteilungen: 264
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, vom Themenstarter, eingetragen 2020-09-12


Hallo AlphaSigma,

Danke für diese Erklärung. Also entscheidet das Programm selbst, ob eine Primzahl vorlegt oder nicht? Ich dachte, das muss ich dem Programm auch sagen. Jetzt ist das aber weitestgehend klarer geworden.

Und 1 heißt, dass es eine Primzahl ist, und -1, dass es keine ist, richtig? Ich versuche das irgendwo nachzuschlagen, werde nirgendwo fündig. Aber ich vertraue da euch mal :P.

Übrigens, ich programmiere in c++. Anscheinend ist das aber voll identisch?

Liebe Grüße
Kajam



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Ixx
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.04.2020
Mitteilungen: 188
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2020-09-12


2020-09-12 21:42 - Kajam in Beitrag No. 8 schreibt:
Also entscheidet das Programm selbst, ob eine Primzahl vorlegt oder nicht? Ich dachte, das muss ich dem Programm auch sagen.

Lies noch einmal nach, wie das Sieb des Eratosthenes funktioniert und versuche das mit der ersten for-Schleife in Verbindung zu bekommen.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2441
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, eingetragen 2020-09-12


Man sollte noch anmerken, dass die gezeigte "Lösung" nur eine ineffiziente Version des Siebes ist.
Die Musterlösung nutzt weder aus, dass man nur bis $\sqrt{N}$ sieben muss, noch dass man zum Markieren keine Teilbarkeit testen muss.

Man vergleiche mit folgendem Beispielcode:
C
int main()
{
    int N = 100;
    int P[N];
    int i,p,t;
    for (i = 0; i < N; ++i){
        P[i] = 1;
    }
    p = 2;
    while (p*p<N){
        for (t = 2*p; t < N; t += p){
            P[t] = 0;
        }
        p += 1;
        while (p*p<N && P[p]!=1){
            p += 1;
        }
    }
 
    for (i = 2; i < N; ++i){
        if (P[i]==1){
            printf("%d, ",i);
        }
    }
    return 0;
}
 



-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
thureduehrsen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 13.11.2007
Mitteilungen: 858
Aus: Kiel, Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, eingetragen 2020-09-12

\(\begingroup\)\(\newcommand{\id}{\operatorname{id}}\)
2020-09-12 22:10 - DerEinfaeltige in Beitrag No. 10 schreibt:
[...] dass die gezeigte "Lösung" nur eine ineffiziente Version des Siebes ist. [...]

Dazu lasse man sich dies hier auf der Zunge zergehen:

Wir haben ausgehend von der naiven Grundversion mit wenigen gezielten Überlegungen den Algorithmus für \(n=10^9\) um den Faktor 254.5 Millionen beschleunigt!

mfg
thureduehrsen
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Scynja
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.02.2011
Mitteilungen: 336
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, eingetragen 2020-09-12


2020-09-12 21:42 - Kajam in Beitrag No. 8 schreibt:

Übrigens, ich programmiere in c++. Anscheinend ist das aber voll identisch?


Hallo Kajam, C und C++ sind nicht identisch. C++ kann aber in der Regel auch C-Code ausführen.

Hier kannst du Unterschiede nachlesen:


Was ich nicht ganz verstehe ist, warum du bereits die Lösung zur Aufgabe hast. Wurde die Lösung denn nicht durchgesprochen?

[Die Antwort wurde vor Beitrag No.10 begonnen.]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
AlphaSigma
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.11.2012
Mitteilungen: 223
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, eingetragen 2020-09-12


Hallo Kajam,

"das Programm entscheidet selbst" ist evtl. etwas missverständlich. Der Programmierer prüft in der ersten (geschachtelten) for-Schleife für jedes k von 2 bis 119 für jedes t von k+1 bis 119, ob t ohne Rest durch k teilbar ist. Falls es das ist, wird array[t] auf -1 (für t ist keine Primzahl) gesetzt.
Das entspricht übrigens nicht dem Sieb des Erathostenes. Da würde man für jedes k prüfen, ob t durch k teilbar ist und für alle Vielfachen von k, d.h. für alle n*k array[n*k] auf -1 setzen.

Hier gibt es Implementierungen des Siebes in etlichen Programmiersprachen:
Sieve of Eratosthenes

C ist eine Untermenge von C++, aber C und C++ sind nicht das gleiche.
C++ ist ein Sammelsurium vieler Programmierparadigmen, u.a., aber nicht nur, objektorientierte Programmierung.

[Die Antwort wurde nach Beitrag No.9 begonnen.]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Scynja
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.02.2011
Mitteilungen: 336
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.14, eingetragen 2020-09-12





Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kajam
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2020
Mitteilungen: 264
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.15, vom Themenstarter, eingetragen 2020-09-12


Ok, ich will mich nicht überfordern. Ich glaube es reicht, wenn ich nur meine Lösung verstehe. Ich habe auch keine Ahnung, wie ich die anderen Codes mit meiner ersten For-Schleife in Verbindung  bekommen soll.

Ich weiß nicht, ob die Lösung besprochen wurde. Ich habe sie nur von der Seite des Instituts runtergeladen. Soweit habe ich sie jetzt verstanden... Das sollte doch reichen. Ich studiere Maschinenbau und muss nicht die krassesten Informatikskills, nur eben die ineffizienten Grundlagen können



[Die Antwort wurde nach Beitrag No.12 begonnen.]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
dietmar0609
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 29.06.2007
Mitteilungen: 2967
Aus: Oldenburg , Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.16, eingetragen 2020-09-12


DerEinfaeltige hat es bereits angedeutet: eine gute (effiziente und schnelle) Implementierung sollte ohne jede Division und Multiplikation auskommen.

Die einzige Rechenoperation sollte das Berechnen der sqrt(N) sein. Die macht man aber nur einmal.

Gruss Dietmar  

[Die Antwort wurde nach Beitrag No.14 begonnen.]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
AlphaSigma
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.11.2012
Mitteilungen: 223
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.17, eingetragen 2020-09-13


Hallo Kajam,

wenn du den Kurs machst um Programmieren zu lernen, solltest Du schon versuchen die Aufgaben selbständig zu lösen. Wenn du nur die Lösungen herunterlädst und nur versuchst sie nachzuvollziehen, wirst du später Schwierigkeiten haben eigene Programme zu schreiben.
Wenn du nur einmal sehen willst wie ein fertiges Programm aussieht, brauchst Du nicht an einem Kurs mit Übungen teilnehmen.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
pzktupel
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.09.2017
Mitteilungen: 1644
Aus: Thüringen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.18, eingetragen 2020-09-13


Der Link von thureduehrsen ist lesenswert.

Und dennoch, es geht mindestens noch 2 Stufen schneller.

1. Stufe: ermittel alle Primzahlen , die bis fed-Code einblenden
vorkommen und verwendte diese im Sieb

2. Stufe: Anwendung von sogenannten Stempeln, der erste sinnvolle ist 30.
Stempel/Räder , haben die Eigenschaft von p#. p# kann dabei sein 6,30,210,2310 und schließen Kleinstteiler aus.

3. Stufe: Reserviere ein Feld bis p# und prüfe nach dem Sieben, ob die Zahl MOD p# einen kleinen Teiler hat oder nicht....sonst ist sie prim.




-----------------
Pech in der Liebe , Glück im Verlieren !!!



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Scynja
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.02.2011
Mitteilungen: 336
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.19, eingetragen 2020-09-13


Ich habe ja tatsächlich versucht verschiedene Algorithmen nachzubauen, um es selbst einmal zu erleben.
Javascript
algo4 () {
      console.time('algo4')
      const endsqrt = Math.sqrt(this.end)
      const result = [false, false]
      for (let i = 2; i <= this.end; i++) {
        result[i] = true
      }
      for (let i = 1; i <= endsqrt; i++) {
        if (result[i] === true) {
          for (let j = 2 * i; j <= this.end; j += i) {
            result[j] = false
          }
        }
      }
      let count = 0
      for (let i = 1; i <= this.end; i++) {
        if (result[i]) {
          count++
        }
      }
      this.amount = count
      console.timeEnd('algo4')
    }

Soweit bin ich gekommen. 100 Millionen sind damit noch machbar, aber bei 10^9 steigt der Rechner aus und es dauert deutlich länger als eine Minute.

Was meinst du mit Stempeln? Man hat doch schon alle Primzahlen gesiebt, wenn man mit Primzahlen bis Wurzel(N) das Sieb anwendet oder nicht?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2441
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.20, eingetragen 2020-09-13


2020-09-13 16:23 - Scynja in Beitrag No. 19 schreibt:

Soweit bin ich gekommen. 100 Millionen sind damit noch machbar, aber bei 10^9 steigt der Rechner aus und es dauert deutlich länger als eine Minute.


Bei 10^9 kann in höheren Programmiersprachen auch der Speicherbedarf ein Problem werden.
(In Python ist er ein Problem und ich verwende daher numpy Arrays statt simpler Listen)

459.02s für die Primzahlen bis 10^9 mit folgendem Code:
Python
def primes(N):
    N = N//2
    L = np.ones((N+1,1),dtype=bool)
    p = 3
    while p*p<=2*N:
        for t in range(p//2+p,N+1,p):
            L[t] = 0
        p += 2
        while p*p<=2*N and not L[p//2]:
            p += 2
    P = [2*p+1 for p in range(N+1) if L[p]]
    P[0] = 2
    return P
 



-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Scynja
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.02.2011
Mitteilungen: 336
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.21, eingetragen 2020-09-13


Ich konnte das Ergebnis noch einmal um 30% verbessern, indem ich true und false vertauscht habe:
Javascript
algo5 () {
      console.time('algo5')
      const endsqrt = Math.sqrt(this.end)
      const result = [true, true]
      for (let i = 1; i <= endsqrt; i++) {
        if (!result[i]) {
          for (let j = 2 * i; j <= this.end; j += i) {
            result[j] = true
          }
        }
      }
      let count = 1
      for (let i = 3; i <= this.end; i += 2) {
        if (!result[i]) {
          count++
        }
      }
      this.amount = count
      console.timeEnd('algo5')
    }


100.000.000
braucht 94.487s

Der Speicher vom Browser ging zwischenzeitig hoch auf 3-4GB, bis er dann wieder sank. Vielleicht ist das noch eine 32-Bit Beschränkung. Der Browser ist auch nicht der beste Ort für rechenintensive Aufgaben.

Ich bin trotzdem enttäuscht. LINUX PC (3.2 GHz) schafft 10^9 in 66 bzw. 17 Sekunden laut dem Paper, während mein PC (3.0 GHz) für ein Zehntel der Menge 94 Sekunden braucht. Vielleicht hat er sogar auf 3.4+ GHz übertaktet...



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
thureduehrsen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 13.11.2007
Mitteilungen: 858
Aus: Kiel, Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.22, eingetragen 2020-09-13


Hallo Scynja,

2020-09-13 17:56 - Scynja in Beitrag No. 21 schreibt:
Der Browser ist auch nicht der beste Ort für rechenintensive Aufgaben.

Ich bin trotzdem enttäuscht. LINUX PC (3.2 GHz) schafft 10^9 in 66 bzw. 17 Sekunden laut dem Paper, während mein PC (3.0 GHz) für ein Zehntel der Menge 94 Sekunden braucht. Vielleicht hat er sogar auf 3.4+ GHz übertaktet...

Zum Einen ist der Browser, wie du selbst erkennst, nicht die beste Umgebung für rechenintensive Aufgaben, zum Anderen wissen wir nicht, wie der Rechner der Autoren genau ausgestattet ist.

Programmiere in C (oder sogar Assembler für die spezifische CPU, die du zur Verfügung hast), wenn du Ambitionen hast, Geschwindigkeitsrekorde aufzustellen!

Oh, und merke dir den Namen Fabrice Bellard -- ihm macht so schnell niemand etwas vor.

mfg
thureduehrsen



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Folgende Antworten hat der Fragesteller vermutlich noch nicht gesehen.
pzktupel
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.09.2017
Mitteilungen: 1644
Aus: Thüringen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.23, eingetragen 2020-09-13


Zum Thema Stempel:

Alle Primzahlen >3 haben die Form 6n+1 oder 6n+5, hier wäre der Stempel 6.
Man kann dies beliebig ausbauen. Ein Stempel von 30 bezieht sich auf Primzahlen der Form 30k+1,7,11,13,17,19,23,29.

Dies sind Zahlen, die keine Teiler von 2,3,5 besitzen.

Während 30=6*5 (Stempel 6), also 10 Zahlen betrachtet werden müssen , sind es bei 30 schon nur noch 8 Zahlen.

Nimmt man einen Stempel von 30, braucht man erst mit 7 anfangen zu sieben. 2,3,5 entfällt. Dabei wird beim Auslesen des Feldes allerdings
nur bei 30k+1,7,11,13,17,19,23,29 abgefragt, ob gestrichen oder nicht.

Ich hatte sogar mal ein Stempel im Stempel programmiert, der arbeitete folgend:

Starte ich im regulären Sieb für Primteiler 7 ab 21, so
nimmt er 21,35,49,63,... und streicht.

Hier fällt auf, dass 21,63,105, alle den Teiler von 3 haben. Diese kann man nochmals auslassen.

Man könnte also gleich mit der 7 im Feld so sieben, das die 3 als Teiler entfällt.
Der Sprung ist an 2 Stellen immer gleich 6*7.
 7+42n
35+42n

Das wäre hier schonmal 1,5fach schneller für Teiler 7 der im Feld verarbeitet wird.

usw....aber das führt zu weit erstmal.

Nachtrag:

Ich lese hier immer Speicherprobleme. Man könnte doch aber das lösen, indem man die Intervalle zerlegt,oder ? Das ist sowieso viel schneller.

Vor kurzen musste ich hier alle Primzahlen bis 100 Mrd berechnen und abspeichern. Das hatte sich nach 40min unter einem Kern erledigt..der PC war da durch.

Man kann in 10 MIO schritten arbeiten und der Einstiegspunkt für den nächsten 10Mio-Block ist ja leicht zu errechnen.



-----------------
Pech in der Liebe , Glück im Verlieren !!!



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Scynja
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.02.2011
Mitteilungen: 336
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.24, eingetragen 2020-09-13


Ich habe es in ein node.js-Skript umgewandelt.

3.122s für 100 Millionen. Also deutlich schneller. Dann wollte ich 10^9 ausprobieren, aber es kam zu "JavaScript heap out of memory".

Ein kurze Recherche hat ergeben, dass man da offenbar nichts machen kann. 🙁

@thureduehrsen, es geht mir keineswegs darum Geschwindigkeitsrekorde aufzustellen. Aber man sollte schon ein Gefühl für das System, wofür man entwickelt, haben. Mal sehen, ob ich mit Java weiterkomme. Leider ist da das Setup relativ aufwändig und an eine komfortable GUI brauche ich gar nicht erst denken.

Nachtrag:

Ich habe das Programm jetzt einmal in Java geschrieben. Dort kann ich ohne Probleme auch bis eine Milliarde gehen und bin in 8 Sekunden fertig.
Damit habe ich nicht gerechnet. Ich widme mich jetzt den Stempeln.

[Die Antwort wurde nach Beitrag No.22 begonnen.]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Scynja
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.02.2011
Mitteilungen: 336
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.25, eingetragen 2020-09-13


2020-09-13 18:54 - pzktupel in Beitrag No. 23 schreibt:

Ich lese hier immer Speicherprobleme. Man könnte doch aber das lösen, indem man die Intervalle zerlegt,oder ? Das ist sowieso viel schneller.

Vor kurzen musste ich hier alle Primzahlen bis 100 Mrd berechnen und abspeichern. Das hatte sich nach 40min unter einem Kern erledigt..der PC war da durch.

Man kann in 10 MIO schritten arbeiten und der Einstiegspunkt für den nächsten 10Mio-Block ist ja leicht zu errechnen.


Der verwendete Speicher bleibt doch gleich oder nicht? Ob ich nun 100 Arrays mit 10 Millionen Werten habe, oder ein Array mit 1 Milliarden Werten. NodeJS ist auf knappe 1,7GB limitiert, wenn ich das richtig gelesen habe. Warum glaubst du, dass es schneller geht, wenn man mit Intervallen arbeitet? Ich habe noch keine Möglichkeit gesehen, wie man effektiv mit Multithreading arbeiten kann. Die Primzahlen werden ja sukzessiv aufgebaut.


Ich habe mich jetzt an einer Implementierung mit Stempeln versucht.
Sie sieht fürchterlich aus, ist aber ein klein wenig (13%) schneller:

Without Stamp
count 50847534
8380
With Stamp
count 50847534
7288
Java
    private static void countPrimesWithStamp(final Long end) {
        long timeStart = System.nanoTime();
 
        final Double endsqrt = Math.sqrt(end);
        final boolean[] result = new boolean[end.intValue() + 1];
        // 1,7,11,13,17,19,23,29
 
        for (int i = 7; i <= endsqrt; i+=6) {
            filterPrimes(end, result, i);
            i += 4;
            filterPrimes(end, result, i);
            i += 2;
            filterPrimes(end, result, i);
            i += 4;
            filterPrimes(end, result, i);
            i += 2;
            filterPrimes(end, result, i);
            i += 4;
            filterPrimes(end, result, i);
            i += 6;
            filterPrimes(end, result, i);
            i += 2;
            filterPrimes(end, result, i);
        }
        // 2 3 5 7 11 13 17 19 23 29
        long count = 10L;
        long end30 = end - 30;
        for (int i = 30; i <= end30; i += 30) {
            if (!result[i + 1]) {
                count++;
            }
            if (!result[i + 7]) {
                count++;
            }
            if (!result[i + 11]) {
                count++;
            }
            if (!result[i + 13]) {
                count++;
            }
            if (!result[i + 17]) {
                count++;
            }
            if (!result[i + 19]) {
                count++;
            }
            if (!result[i + 23]) {
                count++;
            }
            if (!result[i + 29]) {
                count++;
            }
        }
 
        System.out.println("count " + count);
 
        long timeEnd = System.nanoTime();
        System.out.println(TimeUnit.NANOSECONDS.toMillis(timeEnd-timeStart));
    }
 
    private static void filterPrimes(Long end, boolean[] result, int i) {
        if (!result[i]) {
            for (int j = 2 * i; j <= end; j += i) {
                result[j] = true;
            }
        }
    }


Du hast noch etwas von einer zweiten Optimierungsstufe geschrieben:

"3. Stufe: Reserviere ein Feld bis p# und prüfe nach dem Sieben, ob die Zahl MOD p# einen kleinen Teiler hat oder nicht....sonst ist sie prim."

Den Punkt verstehe ich ehrlich gesagt noch nicht ganz. Aber der erwartete Zeitgewinn ist vermutlich nur marginal oder?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
pzktupel
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.09.2017
Mitteilungen: 1644
Aus: Thüringen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.26, eingetragen 2020-09-13


Die 3. Stufe kann man sich sparen, wenn man das Feld am Ende mit den 8 Zahlenkombinationen 30k+1,..29 ausliest.

Primzahlen kann man parallel sieben lassen.

Also wenn man 10 x 100 Mio einzeln siebt, kann das schneller sein, als 1 x 1000 Mio

Wie kann man das Parallel machen ?

1. Thread siebt von 0 - 100 Mio
2. Thread siebt von 100 - 200 Mio als Beispiel.

im ersten Thread verwenden wir alle Teiler bis 10000, im 2. bis 14140

Beide Felder haben 100 Mio im Umfang.

Während als Bsp im 1. Thread die Zahl 13 ab 39 gesiebt wird, passiert im 2. Thread für die P=13.

P- (100000000 MOD P) = X
IF X MOD 2 =0 THEN X+=P

Der Start wäre also bei 17, da 100000017 MOD 13=0 ...

Allgemein für P und X

FOR X=X TO 100000000 STEP 2*P

Im Auswerten, muss aber die Zelle bei Thread 2 mit 100 Mio wieder addiert werden.

3. Thread genauso ... P-(200 MIO MOD P)
__________________

Sehe ich das richtig, das im Sieb in i-Schritten gesiebt wird ?

Man setzt allegmein den Startwert auf ungerade und verdoppelt die Schrittweite (2i)

Ferner bietet sich an, wenn man schon i erhöht, durch 2-4 Abfragen
prüfen, ob i nicht durch 3,5,7,11 teilbar ist.

Am schnellsten ist aber Primteiler bis zur Obergrenze vorab zu berechnen und nur die Primzahlen für i nehmen.



-----------------
Pech in der Liebe , Glück im Verlieren !!!



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
pzktupel
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.09.2017
Mitteilungen: 1644
Aus: Thüringen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.27, eingetragen 2020-09-13


Weitere Möglichkeit zum Parallelisieren ist:

Berechne alle Primzahlen bis etwas über der Wurzel der Obergrenze.

1 Mrd -> 32000. Speichere alle Primteiler in ein Feld PZ, wo auch mehrere Thread daraus lesen dürfen.
PZ(1)=7,PZ(2)=11,...ermittel die Anzahl der Teiler !

Angenommen 4 Threads sieben jetzt los.

Erstelle ein Feld F, wo mehrere Threads zugreifen und sieben dürfen.

Z sei die Anzahl der Primteiler bis 32000 .

Thread 1: Nimmt Primteiler aus PZ wiefolgt.
FOR i=1 TO Z STEP 4
P=PZ(i)
Steiche im Feld F

Thread 2: Nimmt Primteiler aus PZ wiefolgt.
FOR i=2 TO Z STEP 4
P=PZ(i)
Steiche im Feld F

Thread 3: Nimmt Primteiler aus PZ wiefolgt.
FOR i=3 TO Z STEP 4
P=PZ(i)
Steiche im Feld F

Thread 4: Nimmt Primteiler aus PZ wiefolgt.
FOR i=4 TO Z STEP 4
P=PZ(i)
Steiche im Feld F

Werte im Hauptprogramm das gesiebte Feld aus.
Da Primzahlen in Folge in etwa gleich groß sind, sind die 4 Aufgaben ziemlich gleich auch fertig. Ich schreibe das immer aus Sicht von FreeBasic, da ich C nicht beherrsche.


-----------------
Pech in der Liebe , Glück im Verlieren !!!



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Scynja
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.02.2011
Mitteilungen: 336
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.28, eingetragen 2020-09-13


Also gut, nun auch mit Multithreading:

With Stamp
count 50847534
7291
Multithreading
count 50847534
3706

Dann habe ich noch einmal deinen Beitrag gelesen...

2020-09-13 21:28 - pzktupel in Beitrag No. 26 schreibt:
Sehe ich das richtig, das im Sieb in i-Schritten gesiebt wird ?

Man setzt allegmein den Startwert auf ungerade und verdoppelt die Schrittweite (2i)

Ferner bietet sich an, wenn man schon i erhöht, durch 2-4 Abfragen
prüfen, ob i nicht durch 3,5,7,11 teilbar ist.

Am schnellsten ist aber Primteiler bis zur Obergrenze vorab zu berechnen und nur die Primzahlen für i nehmen.


Ja, ich siebe tatsächlich in i-Schritten. Ich muss ja alle nicht-Primteiler markieren. Ich weiß nicht was teurer ist. In ein Array an Position j true zu schreiben, oder zu prüfen, ob j durch 3,5,7,11 teilbar ist. Das mit den der ungeraden Schrittweite stimmt.. ich besser mal nach.


Without Stamp
count 50847534
7936
With Stamp
count 50847534
4362
Multithreading
count 50847534
2475

Die Zeit hat sich noch einmal deutlich verkürzt. Interessanter Weise profitiert die Berechnung mit dem Stempel überdurchschnittlich. Und meine Multithreadimplementierung ist nicht optimal. 2,5 Sekunden sind ganz gut, wenn man das mit den Anfängen von gestern vergleicht.

Ich siebe jetzt mit 8 Zahlen gleichzeitig. Praktischerweise sind die ersten 8 Zahlen alle prim. Und die kommenden 30 sind auch schon ausgesiebt. Ich vermute, dass es später zu einem großen Overhead durch die Threads kommt. Insbesondere, wenn 7 erstellt werden und nur einer siebt.

Java
private void countPrimesWithStampAndMultithreading(final Long end) throws InterruptedException {
        long timeStart = System.nanoTime();
        final Double endsqrt = Math.sqrt(end);
        final boolean[] result = new boolean[end.intValue() + 1];
        // 1,7,11,13,17,19,23,29
        for (int i = 7; i <= endsqrt; i+=6) {
            final ExecutorService executor = Executors.newFixedThreadPool(8);
            executor.execute(new FilterPrimeThread(end, result, i));
            i += 4;
            executor.execute(new FilterPrimeThread(end, result, i));
            i += 2;
            executor.execute(new FilterPrimeThread(end, result, i));
            i += 4;
            executor.execute(new FilterPrimeThread(end, result, i));
            i += 2;
            executor.execute(new FilterPrimeThread(end, result, i));
            i += 4;
            executor.execute(new FilterPrimeThread(end, result, i));
            i += 6;
            executor.execute(new FilterPrimeThread(end, result, i));
            i += 2;
            executor.execute(new FilterPrimeThread(end, result, i));
            executor.shutdown();
            boolean finished = executor.awaitTermination(1, TimeUnit.MINUTES);
        }
        long count = NUMBER_OF_PRIMES_SMALLER_THAN_THIRTY;
        long end30 = end - 30;
        for (int i = 30; i <= end30; i += 30) {
            if (!result[i + 1]) {
                count++;
            }
            if (!result[i + 7]) {
                count++;
            }
            if (!result[i + 11]) {
                count++;
            }
            if (!result[i + 13]) {
                count++;
            }
            if (!result[i + 17]) {
                count++;
            }
            if (!result[i + 19]) {
                count++;
            }
            if (!result[i + 23]) {
                count++;
            }
            if (!result[i + 29]) {
                count++;
            }
        }
 
        System.out.println("count " + count);
 
        long timeEnd = System.nanoTime();
        System.out.println(TimeUnit.NANOSECONDS.toMillis(timeEnd-timeStart));
    }
 
    class FilterPrimeThread implements Runnable {
        private Long end;
        private boolean[] result;
        int i;
 
        public FilterPrimeThread(final Long end, final boolean[] result, final int i){
            this.end = end;
            this.result = result;
            this.i = i;
        }
        public void run() {
            if (!result[i]) {
                for (int j = 3 * i; j <= end; j += 2 * i) {
                    result[j] = true;
                }
            }
        }
    }

Besten Dank für die vielen Optimierungshinweise. Die von dir vorgeschlagenen Varianten zum Multithreading muss ich mir noch einmal in ruhiger Stunde vor Augen führen.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
pzktupel
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.09.2017
Mitteilungen: 1644
Aus: Thüringen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.29, eingetragen 2020-09-14


Du sollst nicht j prüfen ,sondern i

weiß aber nicht, ob das schon passiert....

Meinte nur, die Zahl als Bsp. i=7791 würd ich nicht durchs Sieb ziehen, da diese durch 7 geht.... oder i=1001 usw.

Irgendwann , weil es nötig war, speicherte ich alle Primzahlen bis 100 Mrd auf Platte. Bei Programmstart lese ich die nötigen Primzahlen von Platte wieder ein. In dem Fall bis 1000000 für PZ bis 10^12 nun wirklich kein Ding.


-----------------
Pech in der Liebe , Glück im Verlieren !!!



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]