+- LabVIEWForum.de (https://www.labviewforum.de)
+-- Forum: LabVIEW (/Forum-LabVIEW)
+--- Forum: LabVIEW Code Beispiele (/Forum-LabVIEW-Code-Beispiele)
+--- Thema: Primzahlen finden (/Thread-Primzahlen-finden)
Primzahlen finden - BNT - 06.09.2011 15:22
Liebe LabVIEW Fans
Im Rahmen der Betreuung von Schülerpraktikanten lasse ich die Praktikanten zum Einstieg in LabVIEW immer die Primzahlen berechnen.
Aufgabe: Finde alle Primzahlen <= Maximum.
Eingabe: Maximum
Ausgabe:
- Anzahl der gefundenen Primzahlen
- Array mit den gefundenen Primzahlen
- Zeit in Sekunden, die zur Berechnung nötig waren.
Die Aufgabe stelle ich hiermit auch einmal in dieses Forum. Wer findet den schnellten Algorithmus im Sinne Ausführungszeit.
(Eine Array-Konstante mit den Primzahlen zurückgeben, gilt nicht!)
Mein Vergleichsrechner: Dell D830, Intel Core 2 Duo T7700@2.4GHz 3,5 GB RAM, Win XP SP 3, LabVIEW 2011
Es gilt folgende Vorgabe eines Schülerpraktikanten zu schlagen:
Maximum = 1000000
Zeit gemittelt über 100 VI-Aufrufe:
- Mean=833ms
- Std.Dev.=13ms
- Maximum=894ms
- Minimum= 814ms
[attachment=35696]
Viel Spaß beim Programmieren. Dem Sieger gebührt Ruhm und Ehre.
Ich werde nach einer angemessesen Zeit die Lösung meines Praktikanten hier einstellen.
Gruß Holger
RE: Primzahlen finden - GerdW - 06.09.2011 15:47
Hallo BNT,
nur bis 1Mio? Das ist nicht dein Ernst...
Anbei ein PDF mit Messwerten über einen weiten Bereich (x-Achse gibt Maximum in 2^x an, 20 entspricht in etwa deiner 1Mio). Ist schon was älter, der Core2 ist ein T5400 mit 1.6GHz. Und sind nicht meine schnellsten Algorithmen
1Mio auf meinem aktuellen Core2Quad benötigen 11.5ms zum Rechnen (hauptsächlich zum Initialisieren der nötigen Datenstrukturen) und mit Ausgabe in ein Array ~50ms:
[attachment=35765]
RE: Primzahlen finden - GerdW - 08.09.2011 12:34
Hallo BNT,
kurzes Update (i5-2410M-2.3GHz):
Code:
Test: Prime_Generator, Bitarray
number min mean max result
100000 0,000656 0,000698 0,000795 9592
1000000 0,006362 0,006469 0,006619 78498(min/mean/max in Sekunden, result = Anzahl der Primes)
RE: Primzahlen finden - BNT - 08.09.2011 15:03
Hallo GerdW
Das ist ein tolles Ergebnis.
Ich möchte darauf hinweisen, dass es sich bei dem Code, den ich zeigen werde, um denjenigen eines Schülerpraktikanten der Oberstufe handlet. Das Resultat hat er nach drei Stunden erreicht, LabVIEW lernen inklusive!
Ich möchte also allen LabVIEW Fans - auch den Anfängern - Mut machen[/i], zu versuchen, selbst eine Lösung zu finden. Die Laufzeit-Performanz ist bei einem solchen Algorithmus natürlich wesentlich.
Aber auch Lösungen mit wenigen Strukturen können interessant sein, weil sie vermutlich leicht zu verstehen und leicht zu warten sind. Verschiedene Lösungen geben auch Einblick in die Datenflussverarbeitung von LabVIEW. Also welche Programmierstrukturen sind effizient und welche nicht so sehr.
Ich habe die Metrik des VIs angehängt.
Gruß Holger
RE: Primzahlen finden - Y-P - 08.09.2011 15:28
Bitte nicht wundern. Ich habe das PDF durch ein JPG ersetzt. Ist einfacher zu handhaben.
Gruß Markus
(06.09.2011 15:47 )GerdW schrieb: Anbei ein PDF mit Messwerten über einen weiten Bereich (x-Achse gibt Maximum in 2^x an, 20 entspricht in etwa deiner 1Mio). Ist schon was älter, der Core2 ist ein T5400 mit 1.6GHz. Und sind nicht meine schnellsten Algorithmen
RE: Primzahlen finden - jg - 09.09.2011 09:04
OK, mit GerdW kann ich nicht mithalten. Gehe ich recht in der Annahme, dass dein Algorithmus kein Trial-and-Error Test ist?!
Ich biete bei 1 Mio bei einem "Trial and Error"-Test mit etwas Knoff-Hoff:
Testsystem i7 unter Win7 /
Bei expliziter Parallelisierung auf 2 Cores ca . 360 ms, ohne Parallisierung ca. 385 ms.
Testsystem Athlon X2 5050e (nicht gerade der Schnellste) unter WinXP /
Bei expliziter Parallelisierung auf 2 Cores ca . 700 ms, ohne Parallisierung ca. 985 ms.
Gruß, Jens
RE: Primzahlen finden - GerdW - 09.09.2011 09:23
Hallo Jens,
nee, Trial&Error isses nicht, eher das gute alte Sieb!
RE: Primzahlen finden - jg - 09.09.2011 09:32
(09.09.2011 09:23 )GerdW schrieb: Hallo Jens,Aha, dann muss ich nochmal zurück ans Reissbrett.
nee, Trial&Error isses nicht, eher das gute alte Sieb!
RE: Primzahlen finden - Lucki - 09.09.2011 14:25
1990 habe ich mal bei einem Preisausschreiben um das gleiche Problem bei einer PC-Zeitschrift mitgemacht und dafür ein Paket "Power-Basic deutsch" gewonnen. Es steht seitdem unbenutzt auf dem Dachbodenregal und verstaubt.
Ich hatte es glaube ich so gemacht:
Eine Zahl N ist auf Primzahl zu untersuchen. Der Test für alle Zahlen <N wurde schon gemacht, das Array der bisher gefundenen Primzahlen liegt vor. Wenn N keine Primzahl ist und es werden Primfaktoren gefunden, dann muß einer der gefundenen Primfaktoren kleiner als SQRT(N) sein.
Man muß also die Zahl N durch die bisher gefunden Primzahlen im Bereich 2..SQRT(N) zu teilen versuchen. Wenn der Rest niemals Null ist, ist N eine neue Primzahl. Sowie ein Rest Null ist, wird die Suche abgebrochen werden und die nächste ungerade Zahl getestet.
So ungefähr, und vielleicht mit noch eine paar zusätzlichen Tricks, damit es so schnell wir möglich geht.
Mir diesem Hinweis sollte es doch möglich sein, es mit Gerd aufzunehmen!
RE: Primzahlen finden - GerdW - 09.09.2011 14:35
Hallo Lucki,
Zitat:So ungefähr, und vielleicht mit noch eine paar zusätzlichen Tricks, damit es so schnell wir möglich geht. Mir diesem Hinweis sollte es doch möglich sein, es mit Gerd aufzunehmen!Nichts für ungut, aber das bezweifel ich! Die Q&R-Funktion (oder auch die Divide) sind dafür einfach zu langsam. Mit einem Sieb ist man da immer schneller - man muss nur genügend Speicher reservieren können. Wobei das heute auch kein großes Problem mehr darstellt: um alle Zahlen bis 2^32 zu sieben, benötigt man "nur" ~137MB für eine Routine "mittlerer" Geschwindigkeit. (Wenn's wirklich schnell sein soll, wären 2GB am Stück und ein 64bit-OS/LV nötig.)
1990 habe ich auch angefangen, an Primzahl-Algorithmen zu feilen. In den letzten 2 Jahrzehnten hat sich da einiges getan