Primzahlen(Bench) seit Version 3.0 mit Quadcoreunterstützung!

.K.I.L.L.U.A.

.K.I.L.L.U.A.

Neuling
Thread Starter
Mitglied seit
20.09.2006
Beiträge
426
Ort
Dresden/Sachsen
Vor einiger Zeit habe ich ein Programm geschrieben, welches die Primzahlen von 2 bis [selbstbestimmbar] ausrechnet.

Dabei wurde ein von mir ausgedachter unglaublich ineffizienter Algorithmus verwendet :fresse:.

Das Programm testet einfach alle Zahlen bis n ob diese durch ihre Vorgänger teilbar sind.
D.h. bei der Zahl 10 muss 8 mal auf Teilbarkeit mit den Vorgängern geprüft werden (bzw. sollte ein Teiler gefunden werden wird natürlich zur nächsten Zahl übergegangen, da die Zahl keine Primzahl ist).
--> bei 1000 muss 998 mal geprüft werden (wenn Primzahl)
--> bei 1000000 muss 999998 mal geprüft werden (wenn Primzahl)

edit: der bench testet jetzt nur noch auf Teilbarkeit durch ungerade Zahlen, da ungerade Zahlen (jede Primzahl ist eine ungerade Zahl) nie durch gerade Zahlen teilbar sind.

Dieser Zusammenhang ist expotentionel wenn nicht sogar überexpotentionel.
Also hab ich mir gedacht, dass man das Programm doch ganz gut als Bench missbrauchen kann wenn man die benötigte Zeit misst.
Da nur ein Kern genutzt wird bleiben Dual/Quadcore-Systeme ansprechbar.

Hier mal ein paar Beispiele mit prim_3.0 (sys siehe sig):
n___________Zeit in s
100.000------3,33607
200.000-----11,08632

prim_3.0dw7.png


Sagt mir mal was ihr davon haltet.

.Net Framework 3.5 sollte installiert sein.
das kriegt ihr von hier: http://www.microsoft.com/downloads/...fd-ae52-4e35-b531-508d977d32a6&DisplayLang=de
oder hier:
das web-setup bei Mediafire http://www.mediafire.com/?gtaxsjijmey
oder hier:
den Installer komplett http://winfuture.de/downloadstart,1210202238,2059.html thx -mxp-

bei Rapidshare:
dotnetfx35.part1.rar
http://rapidshare.com/files/115886232/dotnetfx35.part1.rar.html

dotnetfx35.part2.rar
http://rapidshare.com/files/115892208/dotnetfx35.part2.rar.html

dotnetfx35.part3.rar
http://rapidshare.com/files/115892725/dotnetfx35.part3.rar.html

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

Die Versionen:

alt:
Code: 
Beide Programme laufen [U]doppelt so schnell wie prim2[/U] und geben die Primzahlen + die benötigte Zeit in die erzeugte output.txt aus. 

[B][U]prim4:[/U][/B] 
-Prüft zuerst alle ungeraden Zahlen z mit z= 3 + 4x / x Element N+ mit 0 / z<=n und gibt die Primzahlen + die 2 aus,
-dann werden alle ungeraden Zahlen z mit z=5 + 4y /y Element N+ mit 0 / z<=n geprüft und die Primzahlen ausgegeben.
|
v
nur zum rumprobieren (noch kein Multithreading implementiert) -> gibt die Zahlen nicht in der richtigen Reihenfolge aus

[B][U]prim 1.0:[/U][/B]
prüft einfach alle ungeraden Zahlen z mit z= 3 + 2v / v Element N+ mit 0 / z<=n und gibt die Primzahlen + die 2 aus.
|
v
gibt die zahlen in der richtigen Reihenfolge aus.

prim_2.0 -> unterstützt Dualcoreprozessoren
prim_3.0 -> unterstützt Dualcore- und Quadcoreprozessoren

prim_2.0 --->>> [url]http://www.mediafire.com/?vn5mnandnst[/url]   180kb

prim_3.0 --->>> [url]http://www.mediafire.com/?1s4wmr134gm[/url]   180kb

prim_3.1 --->>> [url]http://www.mediafire.com/?0mwilgipltc[/url] 181kb

prim_3.2 --->>> [url]http://www.mediafire.com/?cf98xd9iz3k[/url] 261.49 KB

neu:


prim_3.2 -> nutzt einen verbesserten Algorithmus (thx Hiradur für den Hinweis ... obwohl ich mir das auch schon überlegt hatte ;) ), unterstützt Dualcore- und Quadcoreprozessoren und legt eine Datei (alle_primzahlen_geordnet.txt) mit allen berechneten Primzahlen in der richtigen Reihenfolge an


Meine Bemühungen tragen nun endlich Früchte. Das hat mich ganz schön Nerven gekostet. Aber jetzt bin ich einfach nur froh es geschaft zu haben. :)

prim_3.2 nutzt 4 Threads zum Berechnen der Primzahlen. Und gibt diese in die Dateien output1.txt, output2.txt, output3.txt und output4.txt aus und legt eine Datei namens: alle_primzahlen_geordnet.txt an. In der ... wer hätte es gedacht ... allen berechneten Primzahlen in der richtigen Reihenfolge und die benötigte Zeit eingetragen sind.

->>> ist doppelt bzw. viermal (dualcore bzw. quadcore) so schnell wie prim 1.0 bzw. prim4
->>> ist schneller als prim_3.1 durch einen verbesserten Algorithmus


Die SDL.dll (wird mitgeliefert) muss im selben Ordner wie prim_3.2 sein oder im system32-Ordner.

n kann max. 4.294.967.295 sein ... für 5.000.000 hat mein rechner schon über 2h gebraucht :fresse: (da war aber noch kein multithreading implementiert)
Kann aber auch problemlos auf
[int64 unsinged] = 18.446.744.073.709.551.615 bzw.
[int128 unsinged] ≈ 3,40282*10^38
erhöht werden ... wenn der Arbeitsspeicher nicht ausgeht ;P (ab Version 3.0, da erst da ein Array implementiert ist)

Tipp: Für große n ist das Programm gut für Stabilitäts- und Temperaturtests zu gebrauchen, da alle Kerne zu 100 % ausgelastet werden :)

Viel Spass beim ausprobieren ^_^.


edit2:

prim_3.3 ist da !!!

Hab meinem Programm eine Benutzeroberfläche spendiert.
Leider konnte ich dann den Intel-compiler nicht mehr nutzen, der brachte aber auch keine Vorteile.
Aus unbekannten Gründen (wahscheinlich wegen der Benutzeroberfläche(Form-Projekt)) ist das Programm um den Faktor 11 langsamer als prim 3.2.
Die Threads werden jetzt per .Net-funktion initialisiert.

3_3i4v.png



Download:
 

Anhänge

  • prim 3.3.zip
    67,8 KB · Aufrufe: 77
Zuletzt bearbeitet:
Wenn Du diese Anzeige nicht sehen willst, registriere Dich und/oder logge Dich ein.
Na wird das dein eigenes superpi ^^

ist aber leider nicht ausführbar.....

Dieser Fehler tritt immer auf:
unbenanntcs4.bmp


und in cmd kann ich es auch nicht starten.


Ps: nennt man den Algorithmus nicht sieb des Erostratenes (oder so :P)
 
Zuletzt bearbeitet:
haste .Netframework 2.0 drauf ?

PS. wiki: Unter einem Algorithmus versteht man allgemein eine genau definierte Handlungsvorschrift zur Lösung eines Problems oder einer bestimmten Art von Problemen.
mit vs2008 in c
 
Zuletzt bearbeitet:
Kannst ja auf Quads optimieren in dem du mehrere Zahlen parallel berechnen lässt.
 
oha kein plan musich mal schauen ^^

kommt das per Windows update ?
 
habs mit der 2ten probiert beim mir startet es nicht?

Vllt können wir dir helfen wen wir wüssten mit was das gecodet wurde (sag jetzt bloß nicht java :P). Benutz uns; wenn wir den von der Sprache Ahnung haben; als menschliche Debugger^^



Oder geht das nur unter VISTA ? :d
 
Zuletzt bearbeitet:
hab in c(++) programmiert mit VS 2008
projekt:
c++
win32 consoleapplication
.Net Framework 2.0

#include <stdio.h>
#include <windows.h> -> für den timer

eigentlich nichts aufregendes

habs bei meinem bruder ausprobiert .. bei dem funzt es auch nicht
verdammt noch mal

Oder geht das nur unter VISTA ?
Zum Vergrößern anklicken....
glaub ich nicht, sollte überall laufen
 
Zuletzt bearbeitet:
prim geht nicht

aber prim2 nachdem ich .net framework 3.5 installierte habe
 
thx King Bill

dann liegt das am VS2008
es muss also .Net Framework 3.5 installiert sein

und die erste version ging nicht weil es die debug-version war prim2 ist die release version -> schneller
 
Zuletzt bearbeitet:
naja ich installiere immer die letzte (aktuellste) version da diese alle vorherrigen versionen beinhaltet
 
hier gibts auch noch die komplette version zum download, für leute wie mich die onlineinstaller nicht mögen:
klick

kannste ja vllt oben aufnehmen

100k: 14.85869
200k: 55.29739

c2d e6400@3,5
 
???

so ich hab mal den algorithmus geändert so das es nun statt 2 for-Schleifen 4 for-Schleifen gibt:

2 for-Schleifen für die geraden Zahlen
2 for-Schleifen für die ungeraden Zahlen

ich hab noch keine einteilung in threads vorgenommen aber das programm läuft jetzt plötzlich doppelt so schnell ab obwohl nur ein Thread genutzt wird ... kann mir das nicht erklären .. der Rechenaufwand müsste eigentlich der selbe sein.

edit: ich glaube ich habs verstanden -> der Compiler merkt, dass die geraden Zahlen nie Primzahlen sein können, da diese durch 2 Teilbar sind .. folglich lässt er die Hälfte der Zahlen weg

.. hab noch ne andere idee

so hab das Programm jetzt so verändert, dass es nur die ungeraden Zahlen überprüft .. und diese von zwei verschiedenen Schleifen(A,B) bearbeitet werden (später eine für thread1 und eine für thread2)
A-- 2 for schleifen bearbeiten 3,7,11, ...
B-- 2 for schleifen bearbeiten 5,9,13, ...

wundert euch nicht wenn am ende ein paar zahlen fehlen, diese wurden nur schon vorher ausgegeben, da die CPU-zeit zwischen den Prozessen A und B alterniert(willkürlich hin- und herspringt) -> d.h. nur die reihenfolge der Zahlen wurde verändert ... kann man zb mit n=100 sehr leicht sehen

prim3 war fehlerhaft -> gelöscht
 
Zuletzt bearbeitet:
dürfen wir (ich) den Quellcode anschauen. Da ich nicht grade eine leuchte in C bin könnte ich so mal nen Einblick bekommen.

PS: bei mir geht es nun auch ^^

Mit Prim3 bekomm ich bei einem T7200

100k:

200k:


hmm komisch macht das programm immer 2 durchläufe? Bei mir sieht es so aus als ob es zweimal die selbe Zahlenfolge berechnet?

vllt wäre es gut die Primzahlen in ein txt zu schreiben (kontrolle?).
 
Zuletzt bearbeitet:
So hab mir nochmal alles durch den Kopf gehen lassen :fresse:.

prim4 (wie prim3):
-Prüft zuerst alle ungeraden Zahlen z mit z= 3 + 4x / x Element N+ mit 0 / z<=n und gibt die Primzahlen + die 2 aus,
-dann werden alle ungeraden Zahlen z mit z=5 + 4y /y Element N+ mit 0 / z<=n geprüft und die Primzahlen ausgegeben.

(Vorher wurden einfach alle ungeraden Zahlen z mit z= 3 + 2v / v Element N+ mit 0 / z<=n geprüft und die Primzahlen + die 2 ausgegeben)

Die Primzahlen und die benötigte Zeit werden in eine Textdatei: output.txt (wird vom Programm erstellt) ausgegeben. Für Brokk

Vorteil:

-->Man kann später die 2 hintereinander ausgeführten Aufgaben auf 2 Threads aufteilen und somit gleichzeitig berechnen.
-->Bzw. können noch mehr Unterteilungen (beliebig viele) der ungeraden Zahlen vorgenommen werden um noch mehr Threads zu nutzen. -> sicherlich schneller ^_^

Nachteil:

-->Die Zahlen sind nicht der Größe nach geordnet ... und je mehr Unterteilungen desto mehr Unordnung.


PS:
hier stand müll ...

Brokk schrieb:
dürfen wir (ich) den Quellcode anschauen. Da ich nicht grade eine leuchte in C bin könnte ich so mal nen Einblick bekommen.
Zum Vergrößern anklicken....
Tut mir leid aber das möche ich nicht. (der Algorithmus ist ja eh schon aufgeschrieben ;) )
Einblicke kannst du hier kriegen: (bleib aber lieber erstmal beim wiki-book und schau dir dann das wiki-book für cpp (C++) an )

http://de.wikibooks.org/wiki/C-Programmierung
http://home.fhtw-berlin.de/~junghans/cref/index.html
http://www.henkessoft.de/C++/C++ Fo...hrittene.htm#1.1._Tutorials_zum_Einstieg_in_C

erster Post aktualisiert

Download:
 

Anhänge

  • prim4.zip
    4 KB · Aufrufe: 63
Zuletzt bearbeitet:
200.000 -> 18,49267s
100.000 -> 4,49311 s

System siehe Sig ;D

Edit

mit 2.78 GHz

500.000 : 106,75s
200.000 : 16,6s
100.000 : 4,1 s
 
Zuletzt bearbeitet:
mit meinem Dualcore (siehe sig) brauche ich für:

100.000 -> 3.29742 s
-> schneller

200.000 -> 11.35454 s
-> schneller

Grund müssen die unterschiedlichen Taktraten sein.

Die benötigte Zeit steht auch in der alle_primzahlen_geordnet.txt, damit ihr die nicht abtippen müsst :).
 
Zuletzt bearbeitet:
ok
aber kannst du mal schauen ob auch wirklich alle Kerne ausgelastet werden?

edit:

Um diese 3! Zeilen Code herauszufinden hab ich 2 Tage gebraucht:

#ifdef _WIN32
#undef main
#endif

ohne die ist der Code zwar auch i.o. aber der Linker hat nur Müll gebaut -_-
 
Zuletzt bearbeitet:
Der nutzt schon alle 4 Kerne nur ist die Berechnung wohl etwas "altmodisch" ;)
 
.K.I.L.L.U.A. schrieb:
--> bei 1000 muss 998 mal geprüft werden (wenn Primzahl)
--> bei 1000000 muss 999998 mal geprüft werden (wenn Primzahl)
Zum Vergrößern anklicken....

Habs jetzt nur überflogen, aber du kannst bereits bei n/2 aufhören zu teilen, da alle Zahlen > n/2 niemals mit einer natürlichen Zahl multipliziert n ergeben können.

.K.I.L.L.U.A. schrieb:
Leider weiß man nie welcher Thread als letztes fertig wird (da dies Abhängig von n ist) darum kann es passieren, dass in der Konsole die Meldung: Fertig kommt und danach noch Zahlen ausgegeben werden.
Wenn keine Zahlen mehr ausgegeben werden ist das Programm fertig --> das Drücken einer beliebigen Taste schließt dann das Programm korrekt.
Zum Vergrößern anklicken....

Ich gehe mal davon aus, dass es in c++ geschrieben ist. Da gibt es eine Funktion, mit der man auf Threads warten kann:
Code: 
WaitForMultipleObjects
 
Habs jetzt nur überflogen, aber du kannst bereits bei n/2 aufhören zu teilen, da alle Zahlen > n/2 niemals mit einer natürlichen Zahl multipliziert n ergeben können.

hab ich mir auch schon überlegt aber ich war mit dem threading beschäftigt

WaitForMultipleObjects

werd das mal testen THX
 
Zuletzt bearbeitet:
Anmelden, um zu antworten.
Hardwareluxx setzt keine externen Werbe- und Tracking-Cookies ein. Auf unserer Webseite finden Sie nur noch Cookies nach berechtigtem Interesse (Art. 6 Abs. 1 Satz 1 lit. f DSGVO) oder eigene funktionelle Cookies. Durch die Nutzung unserer Webseite erklären Sie sich damit einverstanden, dass wir diese Cookies setzen. Mehr Informationen und Möglichkeiten zur Einstellung unserer Cookies finden Sie in unserer Datenschutzerklärung.


Zurück
Oben Unten refresh