Wer findet den schnellsten Primzahlalgorithmus
- Ersteller Dizzy_Ti
- Erstellt am
Dizzy_Ti
Vice Admiral Special
Hi,
es sind alle Programmiersprachen erlaubt , die unter Windows laufen.
Bei der Prüfung von 1 bis 30000 braucht mein Algorithmus 6,529 Sekunden inklusive der grafischen Ausgabe aller Primzahlen in einem Memofeld. Die Programmiersprache ist bei mir c++.
es sind alle Programmiersprachen erlaubt , die unter Windows laufen.
Bei der Prüfung von 1 bis 30000 braucht mein Algorithmus 6,529 Sekunden inklusive der grafischen Ausgabe aller Primzahlen in einem Memofeld. Die Programmiersprache ist bei mir c++.
default-X
Grand Admiral Special
- Mitglied seit
- 11.11.2001
- Beiträge
- 4.805
- Renomée
- 76
quelle
Pi = 3,14... - Japaner errechnen 1,2 Billionen Nachkommastellen
Seit 1981 brachen Yasumasa Kanada und seine acht Kollegen von der Universität Tokio bereits drei mal ihren Rekord im Berechnen der Nachkommastellen der Zahl 'pi'. Der vierte Anlauf war wieder erfolgreich.
Eine Billion und 241 Milliarden Nachkommastellen wurden diesmal berechnet. Eine Arbeitszeit von fünf Jahren war nötig, um ein geeignetes Computerprogramm für einen Super-Computer zu schreiben.
Trotz des leistungsstarken Hitachi-Computers dauerte es 400 Stunden, bis der Computer die Berechnung abgeschlossen hatte.
pi/2 = 2/1 * 2/3 * 4/3 * 4/5 * 6/5 ...
muh schlag mich
Pi = 3,14... - Japaner errechnen 1,2 Billionen Nachkommastellen
Seit 1981 brachen Yasumasa Kanada und seine acht Kollegen von der Universität Tokio bereits drei mal ihren Rekord im Berechnen der Nachkommastellen der Zahl 'pi'. Der vierte Anlauf war wieder erfolgreich.
Eine Billion und 241 Milliarden Nachkommastellen wurden diesmal berechnet. Eine Arbeitszeit von fünf Jahren war nötig, um ein geeignetes Computerprogramm für einen Super-Computer zu schreiben.
Trotz des leistungsstarken Hitachi-Computers dauerte es 400 Stunden, bis der Computer die Berechnung abgeschlossen hatte.
pi/2 = 2/1 * 2/3 * 4/3 * 4/5 * 6/5 ...
muh schlag mich
Dizzy_Ti
Vice Admiral Special
@default-X
Klingt interessant. Eigentlich war es gedacht , das jeder selbst einen Algorithmus programmiert, so dass man sich über Optimierungen im Quelltext diskutiert werden kann.
Aber trotzdem danke für die Antwort
Klingt interessant. Eigentlich war es gedacht , das jeder selbst einen Algorithmus programmiert, so dass man sich über Optimierungen im Quelltext diskutiert werden kann.
Aber trotzdem danke für die Antwort
Dizzy_Ti
Vice Admiral Special
ne , mir ist keine Optimierung eingefallen.
Vielleicht kann ja Intel_Hasser noch was zu dem Thema sagen , wenn er den Thread entdeckt.
Vielleicht kann ja Intel_Hasser noch was zu dem Thema sagen , wenn er den Thread entdeckt.
Ich wurde gerufen? 
Primzahlen... hab ich auch schonmal was dazu gemacht (aber in Qbasic
- das "Optimieren" bestand darin, alle viel zu langsamen Funktionen gegen welche auszutauschen die in Qbasic schneller sind )
Die Haudrauf Methode wäre für jede ungerade Zahl zu testen, ob sie sich durch eine Zahl<=Wurzel der eigentlichen Zahl teilen lässt, also ungefähr so:
Die Kiste ist garnet mal sooo langsam, besser wäre wohl sowas wie das Sieb des Archimedes - das geht ungefähr so:
Wenn ich weis, dass x keine Primzahl ist kann ich sämtliche Vielfache von x auch ausschließen.
Wenn ich weis, dass x eine Primzahl ist gilt das natürlich auch
Damit würde man also die falschen Primzahlen nach und nach eliminieren, loht sich aber nur wenn man viel Ram hat und viele, große Primzahlen sucht.
PS n8
Primzahlen... hab ich auch schonmal was dazu gemacht (aber in Qbasic
- das "Optimieren" bestand darin, alle viel zu langsamen Funktionen gegen welche auszutauschen die in Qbasic schneller sind )Die Haudrauf Methode wäre für jede ungerade Zahl zu testen, ob sie sich durch eine Zahl<=Wurzel der eigentlichen Zahl teilen lässt, also ungefähr so:
Code:
int p=1234; // zu überprüfende Zahl
for(int i=3;i<=sqr(p);i+=2) {
if(p%i==0) {
cout << "Keine Primzahl"<<endl;
break;
}
}
if(i==sqr(p)) cout << "P ist eine Primzahl";Die Kiste ist garnet mal sooo langsam, besser wäre wohl sowas wie das Sieb des Archimedes - das geht ungefähr so:
Wenn ich weis, dass x keine Primzahl ist kann ich sämtliche Vielfache von x auch ausschließen.
Wenn ich weis, dass x eine Primzahl ist gilt das natürlich auch
Damit würde man also die falschen Primzahlen nach und nach eliminieren, loht sich aber nur wenn man viel Ram hat und viele, große Primzahlen sucht.
PS n8
mj
Technische Administration, Dinosaurier, ,
Ich spiel nicht mit.
Dizzy_Ti
Vice Admiral Special
@Intel
ok dann probier ich mal dein Prinzip. Bist du sicher das es nicht Sieb des Eratosthenes heißt und nicht Sieb des Eratosthenes
@ D'Espice
Könnte man das nicht mit Java hinkriegen , das es unter Windows und Linux läuft ? Ansonsten könntest du ja , wenn du Lust hast , eine Lösung in Assembler machen.
ok dann probier ich mal dein Prinzip. Bist du sicher das es nicht Sieb des Eratosthenes heißt und nicht Sieb des Eratosthenes
@ D'Espice
Könnte man das nicht mit Java hinkriegen , das es unter Windows und Linux läuft ? Ansonsten könntest du ja , wenn du Lust hast , eine Lösung in Assembler machen.
mj
Technische Administration, Dinosaurier, ,
Ich frage mich ernsthaft, wie man die beiden Worte "schnellsten" und "Java" in einem Zusammenhang verwenden kann
Weiterhin halte ich es für sehr sinnlos eine grafische Ausgabe zu machen aber gleichzeitig den schnellsten Algorithmus zu suchen... Grafische Ausgaben fressen Unmengen an Rechenzeit, wenn du diese Ausgabe weglässt kannst du dir wertvolle Sekunden sparen.
Weiterhin halte ich es für sehr sinnlos eine grafische Ausgabe zu machen aber gleichzeitig den schnellsten Algorithmus zu suchen... Grafische Ausgaben fressen Unmengen an Rechenzeit, wenn du diese Ausgabe weglässt kannst du dir wertvolle Sekunden sparen.
![:]](https://www.planet3dnow.de/vbulletin/images/smilies/rolleyes.gif "Augen rollen (sarkastisch) :]")
Dizzy_Ti
Vice Admiral Special
Original geschrieben von D'Espice
Ich frage mich ernsthaft, wie man die beiden Worte "schnellsten" und "Java" in einem Zusammenhang verwenden kann
Ich wollte dir nur eine Möglichkeit schaffen , einen Algorithmus beizutragen
Das Java nicht sonderlich schnell , weiss ich auch , weil ich das "Vergnügen" hatte in Java zu programmieren.
Ohne Ausgabe brauche ich für 30000 4,5 Sekunden. Ich habe die GUI Ausgabe für meinen INP (Informatik und Programmieren) Lehrer gemacht , da er dies gewünscht hat.
Zuletzt bearbeitet:
Devastators
Grand Admiral Special
Original geschrieben von intel_hasser
Die Kiste ist garnet mal sooo langsam, besser wäre wohl sowas wie das Sieb des Archimedes - das geht ungefähr so:
Wenn ich weis, dass x keine Primzahl ist kann ich sämtliche Vielfache von x auch ausschließen.
Wenn ich weis, dass x eine Primzahl ist gilt das natürlich auch
Du meinst Sieb des Erasthotenes von Archimedes?
Ist recht schnell und liefert anschliessend in einem Array alle Primzahlen bis zu einer Gewünschten Obergrenze.
mj
Technische Administration, Dinosaurier, ,
Ich habe mich der ganzen Sache jetzt mal angenommen und ein plattformübergreifendes Programm in ML geschrieben. Dieses lässt sich auf jeder Plattform mit OCaml übersetzen und ausführen.
Geschrieben an der Uni auf einer Ultra Sparc-60 und unoptimiert ausgeführt ergibt sich für das Berechnen aller Primzahlen zw. 0 und 30,000 eine Zeit von knapp 2s, der vollständige Programmcode sei der Vollständigkeit halber hier eingefügt.
Wer es selber ausprobieren möchte der soll sich OCaml installieren, die Datei prime.ml öffnen und anschließend folgendes eingeben:
findprime 30000 ;;
Wichtig ist das ;; an Ende mit anschließendem Enter, dann wird die Ausführung gestartet und eine Liste aller Primzahlen zurückgegeben. Um alle Primzahlen bis 40000 zu finden lautet der Befehl dann logischerweise
findprime 40000 ;;
Hier das gesamte Programm:
Sobald ich heute Nacht nach Hause komme, werde ich den Code optimiert auf dem Opteron laufen lassen... der müsste das extrem viel schneller schaffen.
Update:
Auf der Sparc habe ich jetzt eine Binary erzeugt und dann per time die Zeit gemessen. Um die ersten 30,000 Primzahlen zu ermitteln benötigt mein Algorithmus 1.955s (compiliert mit ocamlc)
Auf einem T-Bird 1000 waren die ersten 30,000 Zahlen innerhalb von 0.646s ermittelt (compiliert mit ocamlc) oder in 0.115s (compiliert mit ocamlopt).
Geschrieben an der Uni auf einer Ultra Sparc-60 und unoptimiert ausgeführt ergibt sich für das Berechnen aller Primzahlen zw. 0 und 30,000 eine Zeit von knapp 2s, der vollständige Programmcode sei der Vollständigkeit halber hier eingefügt.
Wer es selber ausprobieren möchte der soll sich OCaml installieren, die Datei prime.ml öffnen und anschließend folgendes eingeben:
findprime 30000 ;;
Wichtig ist das ;; an Ende mit anschließendem Enter, dann wird die Ausführung gestartet und eine Liste aller Primzahlen zurückgegeben. Um alle Primzahlen bis 40000 zu finden lautet der Befehl dann logischerweise
findprime 40000 ;;
Hier das gesamte Programm:
Code:
let rec embprime(x,y,z) = match (x,y,z) with
| (_,_,0) -> []
| (x,y,_) when y <= (int_of_float(sqrt(float_of_int x))+1) -> embprime(x, y+1, x mod y)
| (x,y,_) when y > (int_of_float(sqrt(float_of_int x))+1) -> [x] ;;
let rec prime(x) = embprime(x,2,1) ;;
let rec findprime_emb(l) = match l with
| (x::l) when l = [] -> prime(x)::[]
| (x::l) -> prime(x)::findprime_emb(l) ;;
let rec buildlist(p) = match p with
| p when p=1 -> [1]
| p when (p mod 2) = 0 -> buildlist(p-1)
| _ -> p::buildlist(p-1) ;;
let rec clearlist(list) = match list with
| x::l when x=[] -> clearlist(l)
| x::l when l=[] -> [x]
| x::l -> x::clearlist(l) ;;
let findprime x = clearlist(findprime_emb(buildlist x)) ;;Update:
Auf der Sparc habe ich jetzt eine Binary erzeugt und dann per time die Zeit gemessen. Um die ersten 30,000 Primzahlen zu ermitteln benötigt mein Algorithmus 1.955s (compiliert mit ocamlc)
Auf einem T-Bird 1000 waren die ersten 30,000 Zahlen innerhalb von 0.646s ermittelt (compiliert mit ocamlc) oder in 0.115s (compiliert mit ocamlopt).
mj
Technische Administration, Dinosaurier, ,
Wie jetzt, habt ihr alle aufgegeben und Interesse daran verloren oder was?
Ich hab momentan etwas wenig Zeit 
Für kleine Primzahlen müsste die Variante mit einfachdrauflosrechnen am schnellsten sein.
Wie wärs damit alle Primzahlen zwischen 16e9 und 17e9 zu ermitteln? Da wirds schon komplizierter, weil das Sieb des wieauchimmerdertyphies hier schon wieder schneller sein könnte (natürlich auch von der Implementierung abhängig).
Aber die Zahlen sind noch so klein, dass man sich nicht extra eine Lib für große Zahlen schreiben muss, da reicht ein long long int (64bit).
Für kleine Primzahlen müsste die Variante mit einfachdrauflosrechnen am schnellsten sein.
Wie wärs damit alle Primzahlen zwischen 16e9 und 17e9 zu ermitteln? Da wirds schon komplizierter, weil das Sieb des wieauchimmerdertyphies hier schon wieder schneller sein könnte (natürlich auch von der Implementierung abhängig).
Aber die Zahlen sind noch so klein, dass man sich nicht extra eine Lib für große Zahlen schreiben muss, da reicht ein long long int (64bit).
Hab jetzt mal auf die schnelle was zusammengehackt, der braucht (wenn ich es einfach mit g++ abc.cpp compiliere, also völlig unoptimiert) ca. 0.3s für die ersten 30000 Primzahlen.
Kann mir mal einer auf die schnelle sagen, wie ich die Zeit messen kann? Bin zu faul zum nachsehen
Kann mir mal einer auf die schnelle sagen, wie ich die Zeit messen kann? Bin zu faul zum nachsehen
Dizzy_Ti
Vice Admiral Special
mittlerweile 10 ms für die ersten 30000
Wie groß ist denn eine 30000. Primzahl? Manchmal lohnt es sich die Ergebnisse auch zu überprüfen, weil sonst öfters mal recht tolle Zeiten zustande kommen (vor allem wenn man sich die Ergebnisse nicht anzeigen lässt).
Die 30000. ist bei mir 350351.
PS Zeitmessung wird noch implementiert
PPS Bin gerade über eine sehr nette C++ IDE für Gnome gestolpert -> Anjuta
Die 30000. ist bei mir 350351.
PS Zeitmessung wird noch implementiert
PPS Bin gerade über eine sehr nette C++ IDE für Gnome gestolpert -> Anjuta
mj
Technische Administration, Dinosaurier, ,
Ab einen T-Bird 1400 zeigt mein Algorithmus beim Zeitmessen an: 0.000s
Es muss also weniger als 5/10000s sein denn sonst würde er auf 0.001s aufrunden.
Es muss also weniger als 5/10000s sein denn sonst würde er auf 0.001s aufrunden.
Ach so, ihr sucht einen bestimmten bereich nach Primzahlen ab - na das dauert natürlich net so lange.
Da muss ich noch was umändern, damit der bei mir auch einen bestimmten Bereich absucht.
Angesichts der Zeiten schlage ich vor den Bereich etwas auszudehnen, sagen wir auf 0 bis 1'000'000.
Da muss ich noch was umändern, damit der bei mir auch einen bestimmten Bereich absucht.
Angesichts der Zeiten schlage ich vor den Bereich etwas auszudehnen, sagen wir auf 0 bis 1'000'000.
mj
Technische Administration, Dinosaurier, ,
Dann hast du wieder das Problem, dass es nur mit speziellen Bibliotheken geht weil die Zahlen so hoch werden - ergo ist man auf bestimmte Programmiersprachen beschränkt. Ich bin dafür, das ganze so zu gestalten, dass es mit allen Sprachen ohne Verwendung spezieller Bibliotheken zu lösen ist.
Denn diese vermiesen einem wenn schlecht implementiert nur das Ergebnis und sowas soll schließlich ausgeschlossen werden.
Ich würde der Zeit halber jedoch vorschlagen alle Primzahlen zw. 0 und 80000 zu ermitteln. Weiterhin können wir ja ruhig auch einen zweiten Strang laufen lassen in dem die ersten 30000 Primzahlen ausgerechnet werden sollen.
Denn diese vermiesen einem wenn schlecht implementiert nur das Ergebnis und sowas soll schließlich ausgeschlossen werden.
Ich würde der Zeit halber jedoch vorschlagen alle Primzahlen zw. 0 und 80000 zu ermitteln. Weiterhin können wir ja ruhig auch einen zweiten Strang laufen lassen in dem die ersten 30000 Primzahlen ausgerechnet werden sollen.
Na 1000000 ist ja kein Problem, mit einem normalen 32bit Integer kommt man ja bis 2e9, mit einem long long int (den es in c++ ja auch gibt, 64bit Integer) kommt man bis 9e18... und das jeweils mit Vorzeichen.
PS schnell gehackter Algorithmus, für die ersten 30000 Primzahlen 0.2s
PPS keine Angst, so groß wie bei den Fibonacci Zahlen werden die Ergebnisse hier net
PS schnell gehackter Algorithmus, für die ersten 30000 Primzahlen 0.2s
PPS keine Angst, so groß wie bei den Fibonacci Zahlen werden die Ergebnisse hier net
mj
Technische Administration, Dinosaurier, ,
Normale Integer sind eigentlich nur bis knapp über 32000 definiert... und nicht alle Sprachen unterstützen long oder ähnliches.
ML streckt beispielsweise bereits bei den Primzahlen zw. 0 und 90000 alle viere von sich, ich hab's eben auf die Verwendung von floats umgeschrieben dann komm ich immerhin bis 130000 rauf aber dann ist Sense wg. Stack Overflow.
ML streckt beispielsweise bereits bei den Primzahlen zw. 0 und 90000 alle viere von sich, ich hab's eben auf die Verwendung von floats umgeschrieben dann komm ich immerhin bis 130000 rauf aber dann ist Sense wg. Stack Overflow.
