AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

Primzahlen von 0 bis n

Ein Thema von Hador · begonnen am 28. Sep 2006 · letzter Beitrag vom 29. Sep 2006
Antwort Antwort
Seite 3 von 4     123 4   
Rudirabbit

Registriert seit: 27. Sep 2006
111 Beiträge
 
#21

Re: Primzahlen von 0 bis n

  Alt 29. Sep 2006, 19:53
Hi !

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

Registriert seit: 17. Nov 2005
Ort: Hamburg
1.039 Beiträge
 
Delphi XE2 Professional
 
#22

Re: Primzahlen von 0 bis n

  Alt 29. Sep 2006, 20:06
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)
Gruß, Klaus
Die Titanic wurde von Profis gebaut,
die Arche Noah von einem Amateur.
... Und dieser Beitrag vom Amateurprofi....
  Mit Zitat antworten Zitat
dino

Registriert seit: 15. Jul 2006
Ort: Bad Münstereifel
627 Beiträge
 
Delphi 5 Professional
 
#23

Re: Primzahlen von 0 bis n

  Alt 29. Sep 2006, 20:09
wenn man die Programmierzeit mit dazuzählt liege ich garnicht mal so schlecht in der Zeit
  Mit Zitat antworten Zitat
Benutzerbild von negaH
negaH

Registriert seit: 25. Jun 2003
Ort: Thüringen
2.950 Beiträge
 
#24

Re: Primzahlen von 0 bis n

  Alt 29. Sep 2006, 20:54
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
  Mit Zitat antworten Zitat
Benutzerbild von negaH
negaH

Registriert seit: 25. Jun 2003
Ort: Thüringen
2.950 Beiträge
 
#25

Re: Primzahlen von 0 bis n

  Alt 29. Sep 2006, 20:57
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
  Mit Zitat antworten Zitat
alzaimar
(Moderator)

Registriert seit: 6. Mai 2005
Ort: Berlin
4.956 Beiträge
 
Delphi 2007 Enterprise
 
#26

Re: Primzahlen von 0 bis n

  Alt 29. Sep 2006, 21:04
Ich würde an Eurer Stelle mal nach dem "Sieve Of Atkins" googeln. Recht flott, wie man sieht. Hier der Output eines Testprogramms:
Zitat von Eine Delphi-Implementierung des Sieve Of Atkins:
266762506 primes up to 1000359390 in 1740 tics
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
Benutzerbild von negaH
negaH

Registriert seit: 25. Jun 2003
Ort: Thüringen
2.950 Beiträge
 
#27

Re: Primzahlen von 0 bis n

  Alt 29. Sep 2006, 21:17
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]
  Mit Zitat antworten Zitat
Benutzerbild von Hador
Hador

Registriert seit: 11. Dez 2004
Ort: Recke
682 Beiträge
 
Turbo Delphi für Win32
 
#28

Re: Primzahlen von 0 bis n

  Alt 29. Sep 2006, 21:41
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 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

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 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.
Lars Kiesow
http://www.larskiesow.de

Computer gehorchen deinen Befehlen, nicht deinen Absichten.
  Mit Zitat antworten Zitat
Benutzerbild von negaH
negaH

Registriert seit: 25. Jun 2003
Ort: Thüringen
2.950 Beiträge
 
#29

Re: Primzahlen von 0 bis n

  Alt 29. Sep 2006, 21:49
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
  Mit Zitat antworten Zitat
Benutzerbild von negaH
negaH

Registriert seit: 25. Jun 2003
Ort: Thüringen
2.950 Beiträge
 
#30

Re: Primzahlen von 0 bis n

  Alt 29. Sep 2006, 21:54
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
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 02:23 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz