cybton.com
Über uns | Jobs | Werbung | Sitemap | AGB | Impressum | Hilfe ?
 Kostenlos anmelden)
Forum
Aktuellste Beiträge
Forenregeln

Community
BB-Codes
Tags
Chat
Suche (Web)
Wer ist online?
Top-User

Basar


Statistik
Mitglieder gesamt: 68137
Mitglieder online: 4
Gäste online: 4
mehr...

Anzeige
Forum » Forum: Softwareprogrammierung » Thread: Primzahlengenerator

Thread: Primzahlengenerator

Seite 1 von 41234

15.07.2008 15:35 Uhr

 

Status: offline
Ich habe gestern in C einen kleinen Primzahlengenerator geschrieben.
Wer sich dafür interessiert, kann ihn sich hier runterladen: http://home.arcor.de/snatter/Progs/Primzahlen/

Eine kleine Auflistung der Dateien:
Primzahlen.bin => Ausführbare Datei für Linux (32bit)
Primzahlen.cpp => Quellcode (C, sollte aber mit einem C++ Compiler kompiliert werden, wegen bool)
Primzahlen.exe => Ausführbare Datei für Windows (32bit)

Dank Funatiker, der mir heute den Tipp mit der Wurzel gab, konnte ich die Performance drastisch erhöhen.
So hat es bei mir gestern von 0 bis 250.000 etwa 19 Sekunden gedauert und jetzt dauert es von 0 bis 10.000.000 gerade mal ca. 20 Sekunden.

Falls jemand noch andere Ideen hat es zu optimieren nur her damit :).
Die eigentliche Berechnung der Primzahlen findet in Zeile 119 bis 134 statt. In Zeile 109 -117 werden ein paar Fälle abgefangen damit der Algorithmus keine Fehler produziert. Alles davor ist nur Ein und Ausgabe (Konfiguration).

Eines ist jedoch an dem Programm merkwürdig, nämlich dass es auf Intel CPUs deutlich schneller zu laufen scheint. So ist mein Laptop mit Intel Core Duo 1,6Ghz bei diesem Programm um etwa 1,5 schneller als mein AMD 64 X2 mit 3Ghz.
Ich habe ein bisschen mit den Compilerparametern rumgespielt aber keine der Einstellungen scheint wirklich etwas daran zu ändern. Bei andere Software ist aber die AMD CPU in der Regel weit überlegen nur eben nicht bei meinem Primzahlengenerator.
15.07.2008 15:55 Uhr

 

brott
Administrator
Status: offline
Wow, das Ding ist wirklich flott  :glad: 

Verbesserungsvorschlag:
Bei Bildschirmausgabe benötigen 1-10.000.000 Zahlen bei mir um die 58 Sekunden - ohne Ausgabe nur 12 Sekunden!
Ein ähnlicher (wenn auch nicht so gravierender) Unterschied ist auch beim Dateischreiben vorhanden: 17,5 Sekunden.

Verbesserung: Schreibs nicht direkt nach der Berechnung in die Datei/Auf dem Bildschirm, sondern sammle erst alle Zahlen in einem Array und schreib dieses dann danach komplett auf einmal weg! Am besten Bufferst du die Ausgabe dann gleich noch.

Viele Grüße,
Benno
15.07.2008 19:56 Uhr

 

Status: offline
Zitat:
...sondern sammle erst alle Zahlen in einem Array...

Uhhh... Das kann sehr blöd ausgehen, wenn jemand nur wenig Arbeitsspeicher hat, und die zu berechnenden Zahlen hoch eingestellt sind! Vielleicht sollte der Buffer alle x Sekunden in die Datei geschrieben werden... Ist nur so ein Vorschlag. Ja ich weiß, da kommen nicht viel KByte zusammen, aber wenn man sich das zur Gewohnheit macht, dann hat man später bei größeren Projekten einige Probleme ;)
___________________________
Dieser Beitrag entstand durch hirnloses Herumtippen auf der Tastatur.
Jeglicher Sinn und Zusammenhang darin wäre rein zufällig und nicht beabsichtigt.
15.07.2008 20:30 Uhr

 

brott
Administrator
Status: offline
Ob die Zahlen in der Konsole ausgegeben werden oder in einem Array gespeichert sind, dürfte doch Speichertechnisch fast egal sein?

Außerdem ist es ja nur ein reines Zahlenarray. Pro Zahl sind es 4 Byte, sprich bei 1.000.000 Primzahlen (und soviele muss man erstmal finden  :wink:  ) wären erst etwa 4 MB im RAM belegt. Aktuelle Systeme müssten da einiges aushalten.
15.07.2008 20:36 Uhr

 

Status: offline
Ich mache es bei solchen Zeitkritischen anwendungen immer so:
Ich schreibe die Ausgabe in ein Array (wurde ja schon gesagt) und starte einen parallelen Thread, der die Daten ausliest und auf den Bildschirm bringt... Zwar braucht der Ausgabethread manchmal etwas mehr Zeit als der Berechungsthread aber das macht ja nix.
___________________________
Lasst uns Cybton wieder groß machen! Yes We Can!
15.07.2008 22:24 Uhr

 

Status: offline
Also fprintf ist so weit ich weis sowieso standardmäßig gepuffert oder irre ich mich da? So, dass die Dateiausgabe kaum schneller werden würde. Mag sein, dass der Puffer jedoch nicht wirklich groß ist.

Printf ist in dem Fall nur teils gepuffert, es wird nicht jedes Zeichen einzeln ausgegeben sondern nur jede Zeile, da bei jedem \n der Puffer geleert wird.
Jedoch will ich, dass die Ausgabe zeilenweise geschieht und wüsste nicht wie man das am geschicktesten macht. Wenn ich nun ein Ganzzahlen Array nehme da die Ergebnisse sammele und dann jede Zahl ausgebe, habe ich im Endeeffekt die selbe ungepufferte Ausgabe. Wenn ich das jedoch in einem großen String sammele müsste ich die Zahlen immer erst in Strings umwandeln und ich bin mir nicht ganz sicher, wie printf dann reagiert wenn da \n drin sind.

Zitat:
Ich schreibe die Ausgabe in ein Array (wurde ja schon gesagt) und starte einen parallelen Thread, der die Daten ausliest und auf den Bildschirm bringt... Zwar braucht der Ausgabethread manchmal etwas mehr Zeit als der Berechungsthread aber das macht ja nix.

Joa habe sowieso mit dem Gedanken gespielt, das Programm in Threads zu zerlegen, so könnte jede zweite Zahl die getestet wird von einem Thread und die anderen Zahlen von dem anderen Thread berechnet werden (bisher läuft es auch auf Multicoresystemen nur auf einem). Das Problem ist ich weis jedoch nicht genau wie man Threads nutzt, da ich mich damit bisher recht wenig beschäftigt habe.

Zitat:
Uhhh... Das kann sehr blöd ausgehen, wenn jemand nur wenig Arbeitsspeicher hat, und die zu berechnenden Zahlen hoch eingestellt sind! Vielleicht sollte der Buffer alle x Sekunden in die Datei geschrieben werden...

Wenn dann würde das Array sowieso eine Maximalgröße besitzen (die nicht so groß ist, dass es zu Problem führen sollte), denn wenn ich hier einen dynamischen Puffer nutzen würde, könnte es durch das ständige Ändern der Größe unter Umständen dazu führen, dass das Programm im nachhinein sogar langsamer werden würde. Und wenn würde das eher bei kleineren Zahlen zum Problem werden, denn je höher die Zahlen, desto langsamer das Programm, da viel mehr getestet wird und desto schneller läuft der Puffer voll. Eine Zeitgesteuerte Ausgabe wäre hier sowieso das sinnvollste, die jede Sekunde (oder beim erreichen des Maximums) den Puffer leert.

Zitat:
Ob die Zahlen in der Konsole ausgegeben werden oder in einem Array gespeichert sind, dürfte doch Speichertechnisch fast egal sein?

Falsch, da die Konsole eine feste Größe besitzt, nämlich 80 Spalten und wenn ich mich nicht irre in dem Fall ca. 250 Zeilen. Bei einem Array kann man jedoch unzählige Zeilen nutzen und man könnte innerhalb einer Sekunde zick Tausend solcher Zeilen füllen, wobei die Größe dennoch recht klein ist, man kann ja mal die Dateiausgabe starten und schauen wie groß das etwa wird.

Naja wenn mir mal langweilig ist, schau ich mal ob ich es schaffe die Ausgabe zu puffern und vielleicht das Programm in Threads zu zerlegen.

Gerade weil die Ausgabe das Programm so verlangsamt habe ich ja die Möglichkeit bereitgestellt die Konsolenausgabe zu deaktivieren.

Aber weis vielleicht einer wieso das Programm auf Intel CPUs im Gegensatz zu AMD CPUs soo viel schneller läuft? Meines Wissen waren die AMD CPUs ja gerade beim Teilen recht flott verglichen zu den Intel CPUs.

Edit: Ursprünglich wollte ich das ganze ja mit unsigned long long machen, da diese eine größere Genauigkeit bieten (über 32bit). Jedoch alles was ich auch versuchte schienen diese nur eine Genauigkeit von 32 bit genauso wie unsigned long zu haben. Könnte das ggf. daran liegen, dass mein Betriebssystem nur mit 32bit umgehen kann? Und ich das auf einem 64 Bit System kompilieren müsste, damit ich die höhere Genauigkeit (ggf. 64 bit, je nach Kompiler) erreichen kann.
2 mal bearbeitet
15.07.2008 23:36 Uhr

 

Status: offline
Am besten wäre es wirklich drei Threads zu nemen. Einen, der die Zahlen berechnet und in ein Array / Liste schreibt und einen, der für die Ausgabe in der Konsole ausgibt. Der dritte wäre dann für die Ausgabe in die Datei zuständig. So erreichst du bei Mehrkernprozessoren eine hohe Performance ohne allzugroßen Programmieraufwand.

Weiterhin habe ich noch einen weiteren Verbesserungsvorschlag der zu einem Geschwindigkeitsvorteil führen dürfte:
Bisher teilst du in deinem Programm durch alle ungereaden Zahlen < max_factor. also beispielsweise durch 5 und dann irgendwann durch 15. Eine Zahl die aber nicht durch 5 teilbar ist, wird auch niemals durch 15 teilbar sein, da ein vielfaches von 15 genauso ein vielfaches von 5 ist.
Es ist somit nur notwendig durch alle Primzahlen < max_factor zu teilen. Um das zu realisieren bräuchtest du wieder ein Array / Liste in der du die bisher gefundenen Primzahlen abspeicherst, um sie durchlaufen zu können. Dieses Array kannst du dann auch für den Ausgabethread auf dem Bildschirm und die Datei verwenden.
16.07.2008 00:16 Uhr

 

Status: offline
Parn genau das habe ich mir auch schon gedacht, habe mit Funatiker sogar darüber gesprochen, aber mir bisher keine Gedanken über die Umsetzung gemacht. Das mit dem Array wäre jedoch eine nette Lösung.

Das einzigste Problem, dass sich hierbei jedoch stellt ist, dass das nur so lange funktioniert so lange man von 0 anfängt, heisst alle Primzahlen berechnen lässt, fängt man erst ab 10.000 an geht das leider nicht mehr.
16.07.2008 10:24 Uhr

 

Status: offline
Ein Problem ist dabei, dass sobald du Threads oder Prozesse verwendest, es aus ist mit der Windowsversion (oder Linuxversion, je nach Präferenz.)

Jedoch hat dein Program ein Problem: Mit diesem simplen Algorithmus stößt du sehr schnell an seine Grenzen. Das Problem ist, dass diese Grenzen einen praktischen Nutzen ausschließen. (z.B. für Kryptographie.)

Vielleicht interessieren dich ja andere Algorithmen für wirklich große Primzahlen. Die wären auch anspruchsvoller und damit interessanter zu implementieren.
___________________________
"Etre fort pour être utile" - Georges Hébert
16.07.2008 12:26 Uhr

 

Status: offline
Das mit dem Multithreading ist so eine Sache. Viel interessanter ist die Frage, ob es klug ist, unabhängig von der unteren Grenze sämtliche Primzahlen, die kleiner als die zu untersuchende Zahl sind, zu kennen, um anhand der Primfaktoren zu entscheiden, ob eine Zahl eine Primzahl ist.
Seite 1 von 41234
Ähnliche Threads Forum Ähnlichkeitsgrad
 Spieleprogrammierung - und kein Einstieg Softwareprogrammierung 1
 [C++]Allegro Installieren unter WinXP mit Visual C++ als Entwicklungsumgebung Softwareprogrammierung 1
 Asp.net Buch C# Website & Webprogrammierung 1
 c++ compiler Softwareprogrammierung 1
 Dateicontainer für HTML-Games-Server Softwareprogrammierung 1
 [Vermutlich gelöst] FTP mit C? Softwareprogrammierung 1
 MinGW "g++: installation problem, cannot exec `cc1plus': No such file or directory" Softwareprogrammierung 1
nach obennach oben

Copyright © 2008 cybton-network

Google
Partner: #Musik - Dein Internetradio - nexem. - .wir machen news - Your-Book.net - Dein kostenloses Gästebuch
ANEXIA - PHP Entwicklung - Dockers - s.Oliver Schuhe - Think Schuhe - der eigene Weg - Dorfen - Paul Green Schuhe - Bequeme Geox - Web-Entwicklung