Primzahlen von 0 bis n

[Rudirabbit]

Hi !

@Hador: Wegen des Bool Array Ram Speicher Problems, hat du schon mit PACKED ARRAY getestet ?

[Amateurprofi]

Zitat:

Zitat von dino

ich habe mit meinem Programm innerhalb von eineinhalb stunden alle Prinzahlen von 1 bis 1Millionen gekriegt. wie lange braucht ihr?

meine im Beitrag weiter oben gezeigte Version braucht für 1..1000000 ca. 9 ms und für 1..1000000000 ca. 48 s.
Und das ist nicht besonders schnell.
negaH hat m.W. eine Routine die 14 s braucht für 1..2^32 ..... (aber die hat er sicherlich nicht in 1/2 h zusammengeflickt)

[dino]

wenn man die Programmierzeit mit dazuzählt liege ich garnicht mal so schlecht in der Zeit

[negaH]

Zitat:

Und das ist nicht besonders schnell.
negaH hat m.W. eine Routine die 14 s braucht für 1..2^32

Interessenshalber habe ich meinen Code eben auf meinem Laptop getestet. Damals ergaben sich die Zeiten auf einem Pentium 4 1.5Ghz 512MB und mein neues Laptop ist ein Intel Core Duo mit 2.16Ghz 1Gb, also mit 2 CPUs a 2.16 GHz und doppelt Speicher mit viel höherem Takt.

Komischerweise ergaben sich folgende Zeiten

Code:

 1 bis    1000000 =  0.03 sec
 1 bis 1000000000 = 12.70 sec
 1 bis 2^32-1     = 56.00 sec

also langsammer als auf meinem alten P4, egal. Komischerweise sind aber meine Berechnung von der Zahl Pi mit Millionen Stellen wiederum mehr als 4 mal schneller -> 1Mio Stellen in 3.5 Sekunden statt eben 13 Sekunden auf dem P4.

Die wichtige Frage ist, wie lange brauchen zb. eure Algorithmen um alle Primzahlen zwischen zb. 1000000000 bis 2000000000 zu berechnen ?

Code:

1000000000 bis 2000000000 = 17.54 sec

bei meinem Code, allerdings sollte ich erstmal überprüfen warum das Ding auf meinem Laptop so deutlich langsammer ist als auf meinem P4.

Denn gerade die Bereichberechnung der Primzahlen ist ein Indiz für die Effizenz des Algos. Im Falle des Siebes wie hier müssen nämlich alle Vorgängerprimzahlen ermittelt werden um überhaupt den gwünschten Ausschnittsbereich berechnen zu können.

Gruß Hagen

[negaH]

Hm, ich weis ist offtopic, aber könnte es sein das eine Zeitmessung basierend auf dem Time Stamp Counter -> RDTSC und QueryPerfoamnceCounter() auf einem Mehrprozessoren System falsche Werte liefert ?

Das wäre die einzigste Erklärung so auf die Schnelle.

Gruß Hagen

[alzaimar]

Ich würde an Eurer Stelle mal nach dem "Sieve Of Atkins" googeln. Recht flott, wie man sieht. Hier der Output eines Testprogramms:

Zitat:

Zitat von Eine Delphi-Implementierung des Sieve Of Atkins

266762506 primes up to 1000359390 in 1740 tics

[negaH]

guter Tipp Alzaimar :-) dumm ist nur das mein Code nach exakt diesem Sieb arbeitet ;)

zZ. macht mich aber der enorme negative Unterschied von einem P4 1.5Ghz zu einem Dual Core 2.16Ghz Rechner stuzig.

Gruß Hagen

[edit]

Das Messtechniker Sprichwort lautet "wenn du misst dann misst du Mist" !

Meine Zeitberechnungsroutinen basieren auf RDTSC und QueryPerformanceCounter()/Frequency(). Spaßenshalber nun die gleiche Funktion mal parallel mit GetTickCount() gemessen und siehe da

12756 ms mit meiner Messroutinen
4610 ms mit GetTickCount()

Ergo: RDTSC in Kombinaton mit QueryPerformanceCounter funktioniert auf Dual Cores nicht sauber.

Ein weiteres sehr komoische Verhalten ist das die Messungen mehrmals hintereinander total verrückte Abweichungen ergeben. Es scheint das Powermanagement das die CPUs dynamisch im Takt drosselt schuld zu sein. Jetz muß ich erstmal nach ne besseren Messroutine Ausschau halten. (von wegen meine DECMath routinen wären nur 4 mal schneller als auf einem P4, so wie es aussieht ist es 12 mal schneller).

[/edit]

[Hador]

Zitat:

Zitat von Rudirabbit

@Hador: Wegen des Bool Array Ram Speicher Problems, hat du schon mit PACKED ARRAY getestet ?

Hab ich gerade. Der Speicherverbrauch bleibt gleich, dafür wird jedoch das Programm langsamer.

Zitat:

Zitat von negaH

Hm, ich weis ist offtopic, aber könnte es sein das eine Zeitmessung basierend auf dem Time Stamp Counter -> RDTSC und QueryPerfoamnceCounter() auf einem Mehrprozessoren System falsche Werte liefert ?

Das wäre die einzigste Erklärung so auf die Schnelle.

Gruß Hagen

Du könntest doch einfach mal mit GetTickCount die Zeit messen. Es ist zwar nicht ganz genau - Ich mene das habe ich mal in einem deiner Beiträge gelesen ^^ - aber immerhin müsstest du einen ungefähren Wrt bekommen. So könntest du kontrollieren, ob dieser Wert grob von dem durch RDTSC ermittelten abweicht.

EDIT: Arr irgendwie hab ich deinen letzten Beitrag übersehen :gruebel:

Zitat:

Zitat von alzaimar

Ich würde an Eurer Stelle mal nach dem "Sieve Of Atkins" googeln. Recht flott, wie man sieht. Hier der Output eines Testprogramms:

Zitat:

Zitat von Eine Delphi-Implementierung des Sieve Of Atkins

266762506 primes up to 1000359390 in 1740 tics

Ich werde erstmal versuchen meinen jetzigen Algo noch etwas zu optimieren. Dann werde ich mir das SoA. aber auf alle Fälle mal anucken. Danke für den Hinweis.

[negaH]

Ja sorry das ich deinen Thread hijacked hab, ich hab hier einen neuen Thread angelegt http://www.delphipraxis.net/internal...=618629#618629

Und defakto ist es so das meine Messroutinen mit mindestens einem Faktor von 3 mal daneben liegen, allerdings eben auch stark abhängig ob die CPUs durch das ACPI gedrosselt werden (das konnte ich schon verifizieren da ich die CPUs auch manuell drosseln kann, per Hotkey).

Aber wir sollte das alles im obigen neuen Thread fortsetzen, sorry nochmals.

Gruß Hagen

[negaH]

so zurück zum Thema. Alzaimar hat dir ja schon einen Link auf seinen Source gegeben. Wenn du mein DEC, http://www.michael-puff.de/Developer...agen_Reddmann/ , runterlädst findest du in Unit Prime.pas meine Implementation des Siebes. Als Referenz für deine Test wohl ausreichend.

Kleiner Tipp noch: wenn du mit meinen Messroutinen aus dem DEC arbeitest und du hast einen Mehrprozessorenkern dann baue doch die 2. CPU vorher aus, ansonsten misst du Mist ;)

Gruß Hagen