  |
|
 Programmiersprachenkontest: Primzahlüberprüfung |
CDW 
eine Simulation
Dabei seit: 12.10.2002
Beiträge: 1.329
Herkunft: CreateRemoteThread
 |
|
| Programmiersprachenkontest: Primzahlüberprüfung |
|
Zmaster hat mich auf die Idee gebracht,einen Programiersprachenkontest zu veranstalten.Anstatt uns also zu streiten,welche Sprache die beste ist - lasset es uns beweisen 
(bitte keine Anmerkungen,á la "jede Sprach hat ihre Vorteile - das weiß ich ja auch 
)
Es geht darum,dass das Programm eine Zahl einliest und überprüft,ob es eine Primzahl ist (also teilbar durch sich selbst und eins) oder halt nicht.
Auszugeben sind die für die Überprüfung gebrauchte Zeit und das Ergebnis (wahr oder falsch - eventuell auch die Zahl,durch die es teilbar ist).
gepostet werden sollen: ein Link zum fertigkompiliertem Programm, eventuelle Anforderungen (OS,Javaversion,VBRUN version,was weiß ich)
ein Link zum Quelltext. Maximale Zahlgröße soll DWORD sein - damit dürfte man in den meisten Sprachen kein Problem haben und keine zusätzlichen Libs benötegen)
im Nachhinein soll eventuell eine Jury (oder auch wer einfach Lust hat) die Programme auf ihren Rechnern mit den gleichen Zahlen laufen lassen und die Zeit posten.
Ich denke an folgenden Programmaufbau:
Zahl einlesen, alle vorbereitungen zum Berechnen machen.
Zeit messen.
berechnen
Zeit messen.
Resultat und Zeit ausgeben
Da die Aufgabenstellug relativ einfach ist, kann jeder mitmachen... was haltet ihr davon?
|
|
23.02.2003 18:55 |
|
|
phlox81
Bote des Lichts und Moderator
Dabei seit: 19.10.2002
Beiträge: 3.028
Herkunft: Irgendwo im Nirgendwo
|
|
Wie stellst du dir das mit dem Zeit messen vor ?
Und wie groß ist dann die Zahl ?
Ansonsten, wär ich für c/c++ und Java dabei...
Devil
__________________
Intelligenz ist eine Illusion des Menschen
phlox81.de | codenode.de
|
|
|
23.02.2003 21:00 |
|
|
Zmaster
Junior Member
Dabei seit: 15.02.2003
Beiträge: 133
|
|
 primzahl |
|
Also die Idee finde ich auf jeden Fall gut.
Ich hätte nur eine Frage. Wie groß kann DWord werden?
Ist das mit long in Java vergleichbar?
Wegen den Zeitmessen: es muss halt im Quellcode enthalten sein.
Die Ausgabe erfolgt über ein Label.
Im Code kann das ja dann so aussehen:
| code: |
1:
2:
3:
4:
5:
6:
7:
|
function button_click()
{
anfangszeit = time();
mLabel.setCaption(meinePFunktion(mText.getCaption));
endzeit = time();
mZeit.setCaption(endzeit-anfangszeit);
} |
|
Ich bin dafür, dass keine Exe-Dateien gewertet werden. Es sollte immer der Quellcode hochgeladen werden.
Gruß
zmaster
|
|
|
23.02.2003 21:22 |
|
|
Rabenicht
Aufsteiger
Dabei seit: 18.01.2003
Beiträge: 84
Herkunft: Fehler in Zeile 23
|
|
Ich halte es für absurd, anzunehmen, daß eine Sprache "die beste" ist, nur weil sie bei einer bestimmten Aufgabe die Nase vorn hat.
Ich bezweifle weiter, daß die Methode, aus dem Programm heraus die Zeit zu messen, zu vergleichbaren Ergebnissen führt. Was ist z.B., wenn die Java Umgebung sich einfach etwas Zeit läßt, mit der Rückgabe der Systemzeit oder sie aus anderen Gründen ungenau wiedergibt? Ähnliche Fehlerquellen scheinen mir durchaus denkbar, daher würde ich zumindest vorschlagen, die Zeit extern zu messen.
Darüber hinaus gibt es mehrere Möglichkeiten, das Problem zu lösen. Wenn ein Programm also schneller ist, als ein anderes, dann war vielleicht einfach nur der Programmierer geschickter (ich sage nicht: besser!), so daß zumindest noch eine Art Pseudocode verabredet werden muß.
Alles in allem halte ich aber diesen Wettbewerb für absolut überflüssig. Denn hiermit ist eigentlich schon alles gesagt:
| Zitat: |
| (bitte keine Anmerkungen,á la "jede Sprach hat ihre Vorteile - das weiß ich ja auch ) |
__________________
java.sql.SQLException: [Micro$oft][ODBC Micro$oft Access Driver] Data type mismatch in criteria expression or general fuck off.
|
|
|
23.02.2003 21:59 |
|
|
Zmaster
Junior Member
Dabei seit: 15.02.2003
Beiträge: 133
|
|
 Laufzeit |
|
Das mit dem externen Zeitmessen stell ich mir schwierig vor.
Aber wenn du das eine Idee hast, wie man das realisieren kann, dann immer her damit.
Zur Geschwindigkeit sollte man daher vielleicht noch die Laufzeit angeben.
Die maximale Laufzeit bei einer wirklichen Primzahlen beträgt: n-1
Durch Optimierung können aber die Hälfte der Elemente eliminiert werden und damit die Laufzeit verkürzen.
Mal sehen wer die schnellste Laufzeit entwickelt.
zmaster
|
|
|
24.02.2003 09:45 |
|
|
CDW
eine Simulation
Dabei seit: 12.10.2002
Beiträge: 1.329
Herkunft: CreateRemoteThread
Themenstarter 
|
|
schlägt ihr dann vor, dass man ein Algo hat, den es umzusetzen gibt? Mit dem Zeitmessen hab ich auch schon gemerkt: ich kann rdtsc nutzen und die Zeit SEHR genau ablesen, nutze ich dagegen die win interne timeGetTime (ganuigkeit 1 ms) kommen schon leichte Abweichungen...
|
|
|
24.02.2003 11:42 |
|
|
Zmaster
Junior Member
Dabei seit: 15.02.2003
Beiträge: 133
|
|
| verraten |
|
@Compuholic:
Du bist gemein!
Das du alles verraten musst. Ich habe gestern abend im Bett rausbekommen, dass es reicht bis zur Quadratwurzel alle Elemente zu überprüfen.
Heute früh unter der Dusche habe ich noch eine zweite Möglichkeit gefunden, um nochmehr zu optimieren.
Zur Zeit liegt meine Laufzeit bei sqrt(n)/3 (natürlich so, dass nicht zu viele Kontrollstrukturen drinne sind)!
Ich tippe, dass Java die langsamste Sprache ist.
Dann kommt Visual Basic.
Ganz vorne wird C++ liegen. Würde ich vermuten.
zmaster
|
|
|
24.02.2003 17:20 |
|
|
CDW
eine Simulation
Dabei seit: 12.10.2002
Beiträge: 1.329
Herkunft: CreateRemoteThread
Themenstarter
|
|
zur Zeitmessung: Extern wäre wohl noch ungenauer-man denke dabei z.B an Java oder VB oder auch C++ mit MFC - jemand macht die Gui damit, dann wird also auch die Zeit zum Laden/schließen der Gui mitberechnet.Außerdem,da alle Programme intern trotzdem die WinAPi aufrufen, sollten sich die Fehler in Grenzen halten:
| Zitat: |
| wenn die Java Umgebung sich einfach etwas Zeit läßt, mit der Rückgabe der Systemzeit |
Ja das stimmt, aber gleicht sich der Fehlern nich etwas aus, da man die Zeit nochmal messen muss (beispiel: am Anfang messen: Java lässt sich 5 ms Zeit,am ende messen - Java lässt sich wieder 5 ms Zeit
)
Also, ich hab momentan ein billigverfahren (Bruteforce *g*)
und zur Primzahlüberprüfung von:
2147483647
brauche ich 27901 ms (also etwa 28 Sekunden)
übrigens ist es sehr lehrreich,da man verschiedene Methoden ausprobieren kann und sieht/lernt, welche Technik schneller ist.
Eine Nichtprimzahl überprüfen ist etwas blöd - denn je nach dem, wo man anfängt (ob man "runter" oder "raufzählt" bekommt man eine andere Zeit)
Hm, Wurzel/3 ? wie kann das sein? Obwohl ich ja eher einfach drauflos teile (bis zur Hälfte der gesuchten Zahl)
PS: ich würde C noch vor C++ setzen, obwohl, je nach compiler und Datenstruktur (aber bei dieser Aufgabe braucht ja keiner eine komplexe Datenstruktur) LX hat noch angedeutet, man könnte so was wie Zahlencache machen, aber IMHO ist es zuviel overhead (zu oft muss dann auf den Speicherzugegriffen werden)
EDIT: vielleicht sollte ich wirklich mal mit der Wurzel ausprobieren und der zusätzliche Overhead lohnt sich doch...
PS: der große nachteil der HHL besteht darin, dass jede Variable im Speicher zu liegen hat und die Ergebnisse somit jedesmal vom register in den Speicher und zurück wandern müssen - obwohl es bei den neuen CPUs nicht mehr so viel ausmachen dürfte (und ich weiß auch nicht,ob inzwischen die ganz neuen Compiler VC++7.0 oder IntelCompiler es nicht doch mittlerweile beherrschen)
Dieser Beitrag wurde 3 mal editiert, zum letzten Mal von CDW: 24.02.2003 18:08.
|
|
|
24.02.2003 17:54 |
|
|
LX
El Comandante en Jefe
Dabei seit: 25.11.2001
Beiträge: 5.372
Herkunft: Berliner Bronx
|
|
Die minimale Anzahl Vergleiche liegt bei der Anzahl der Primzahlen kleiner oder gleich der Quadratwurzel der zu prüfenden Zahl. Würde man jetzt mehrere Läufe mit recht hohen Zahlen starten, und bei jedem Lauf nur die Primzahlen im Cache prüfen lassen bzw. neue Zahlen dem Cache hinzufügen, dann wäre diese Lösung auf Dauer die schnellere sein. Prüft man allerdings nur eine einzelne Zahl, dann ist das Zeitverschwendung.
Ich habe BTW heute morgen mal eine Lösung in C versucht. Allerdings merke ich gerade, wie wenig ich das kann... denn bei der Zeitmessung hapert's bei mir
)
__________________
JS-Games.de - Misled Scripting Skills Gone Mad | Meine Filmkritiken | Urban Photography
Kommt mal in den IRC-Channel: irc.eu.freenode.net | Port 6667 | #blackboard
"Ever tried. Ever failed. No matter.
Try again. Fail again. Fail better."
- Samuel Beckett
|
|
|
24.02.2003 18:08 |
|
|
phlox81
Bote des Lichts und Moderator
Dabei seit: 19.10.2002
Beiträge: 3.028
Herkunft: Irgendwo im Nirgendwo
|
|
Wie wäre es wenn wir die ersten 1000 Primzahlen berechnen, und diese in einem Array speichern ?
So wäre dann auch rechenzeit stärker spürbar.
Devil
__________________
Intelligenz ist eine Illusion des Menschen
phlox81.de | codenode.de
|
|
|
24.02.2003 20:27 |
|
|
CDW
eine Simulation
Dabei seit: 12.10.2002
Beiträge: 1.329
Herkunft: CreateRemoteThread
Themenstarter
|
|
Zmaster: was ist bei dir denn für Ausgabe gemeint (Zeit: 0,25 ms oder 0,25 sek ? )Subjektiv kann ich das irgendwie nicht unterscheiden
Wobei die WinAPI nur mit genauigkeit von 1ms misst (bei NT muss man das vorher noch einstellen, sonst hat man genauigkeit von 5 ms) Und ich also k.A hab,wie ich das genauer messen kann (naja,außer mit rdtsc)
So wie ich das verstanden habe, teilst du ja den "Teiler" durch 3 und wenn er sich nicht teilen lässt, addirst du 2 hinzu.IMHO ist es für die CPU mehr Aufwand, als direkt durch die Zahl zu teilen,jedenfalls in den höheren Werte-bereichen...
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von CDW: 24.02.2003 21:33.
|
|
|
24.02.2003 21:26 |
|
|
Zmaster
Junior Member
Dabei seit: 15.02.2003
Beiträge: 133
|
|
| zeit |
|
Ich habe angenommen, dass es Milisekunden sind, aber jetzt wo ich das Programm nochmal gestartet habe, und ne halbe sekunde warten musste, habe ich mich auch gewundert.
Ich dachte Timer ist in ms, aber da habe ich mich geirrt.
Es ist in Sekunden. Es gibt zwar dann immer noch Dezimalzahlen aus, dass man trotzdem auch in ms das Ergebnis angeben könnte, aber es sind Sekunden.
Mein Fehler!
Danke für den Hinweis CDW!
zmaster
|
|
|
24.02.2003 21:38 |
|
|
LX
El Comandante en Jefe
Dabei seit: 25.11.2001
Beiträge: 5.372
Herkunft: Berliner Bronx
|
|
|
|
24.02.2003 22:13 |
|
|
CDW
eine Simulation
Dabei seit: 12.10.2002
Beiträge: 1.329
Herkunft: CreateRemoteThread
Themenstarter
|
|
Zmaster: jetz ist die Welt wieder in Ordnung für mich
- weil ich mir schon dachte, wie es sein kann, dass VB genausoschnell wie asm ist und hatte schon vor, komplett auf C umzusteigen
: nein, es hat einen ernsthaften Hintergrund,dass ich mich gewundert hat: nach deinem Verfahren untersuchst du etwa nur 1 drittel der Zahlen weniger als ich, jedoch hast du den zusätzlichen Aufwand mit Division/Vergleich, gerade aber in solchen alogs lässt sich der Vorteil von asm ausspielen: Höhere Sprachen benutzen Variablen, die im Speicher angelegt sind, wenn man also etwas berechnet, dann wird die Variable aus dem Speicher ins Register geholt, berechntet und dann zurückgeschrieben - das fällt bei Kleinigkeiten nicht mehr auf, da es inzwieschen recht schnell geht, aber bei tausendfachen Berechnungen ist es schon ein unterschied, da Speicherzugriff jedesmal Zeit kostet.Wenn man es aber "manuell" so gestaltet, dass die Variablen in Registern bleiben (sind 6 benutzbare),spart man sich den "Speichertransfer".
Ansonsten ein logisches Verfahren.
@Compuholic: mein Code könnte sichrerlich noch ein paar Optimierungsrunden vertragen (noch einiges überflüssig/verbesserungsfähig), ansonsten hatte ich vor einiger Zeit auch mal versucht das Verfahren zum Wurzelziehen zu realisiern, habe dann aber auf dem asm-board gelesen, dass es langsammer ist, als wenn man es der CPU/FPU überlässt,da inzwischen auf Prozessoren Hilfstabellen usw implementiert sein sollten, die intern dafür benutzt werden, ich glaube, es steht dazu auch was in Assembler-Gepackt(J.Rohde)
Was mich viel Zeit gekostet hat, ist der "Fehler" der FPU - sie liest DWORD Werte als signed ein und hatte deshalb ab einem bestimmten Wert nur noch minuszahlen eingelesen.Ich habe die ganze Doku abgegrast und nichts dazu gefunden,wie man dieses Verhalten steuern/ändern kann, also habe ich kurzer hand ein QD genommen und mit DWORD PTR drauf zugegriffen.
|
|
|
25.02.2003 18:23 |
|
|
Misel
Hüter des Kitkat
Dabei seit: 02.11.2002
Beiträge: 1.203
Herkunft: live://home.berlin.d
e
|
|
bin gerade im Newsletter über diesen Thread gestolpert und eben auf'm Klo ist mir noch eine Optimierungsmethode eingefallen, basierend auf der Primzahlenzerlegung. Die Idee hatte ich, als ich mir nochmal zmasters Kommentar zu den durch 3 teilbaren Zahlen durch den Kopf gehen hab lassen.
Zahlen, die keine Primzahlen sind, lassen sich als Faktoren mehrerer Primzahlen darstellen. Man nutzt das zum Beispiel um den kleinste gemeinsame Vielfache zweier Zahlen zu finden.
Man muss bei einer Zahl nur noch prüfen, ob diese durch eine der bereits gefundenen Primzahlen teilbar ist. Ich wage sogar zu behaupten, dass das die geringste Zahlenmenge ist, die man prüfen muss. Allerdings fehlt mir das Können und die Muße das zu beweisen.
Ich bin sicher schon hunderte anderer kluger Köpfe sind darauf gekommen, aber hier im Thread stand es IMHO noch nicht so explizit drin. Deshalb wollte ich es wenigstens erwähnt wissen.
__________________
LAUFT! Ich spiele KILLERSPIELE!
|
|
|
11.02.2007 14:57 |
|
|
|
|
|
 |
|
laufzeit