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 |
|
|
|
LX
El Comandante en Jefe
Dabei seit: 25.11.2001
Beiträge: 5.372
Herkunft: Berliner Bronx
|
|
| Zitat: |
Original von LX
Die minimale Anzahl Vergleiche liegt bei der Anzahl der Primzahlen kleiner oder gleich der Quadratwurzel der zu prüfenden Zahl. |
Ich denke, das ist sinngemäß das, was du damit ausdrücken wolltest
__________________
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
|
|
|
11.02.2007 15:01 |
|
|
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 |
|
|
|
LX
El Comandante en Jefe
Dabei seit: 25.11.2001
Beiträge: 5.372
Herkunft: Berliner Bronx
|
|
|
|
24.02.2003 22:13 |
|
|
|
antilooppe2
Junior Member
Dabei seit: 28.11.2002
Beiträge: 125
Herkunft: Nicht Da nicht hier abschon irgendwo
|
|
| RE: laufzeit |
|
| Zitat: |
Original von Zmaster
Man könnte meinen, dass einige von euch noch nie was von Laufzeit gehört haben (ich meine speziell LX).
Also ich habe es hinbekommen, dass es nun mit sqrt(n)/3 funktioniert.
Ihr wärd aber sicherlich auch drauf gekommen. Warum muss ich eine Zahl durch 9 teilen, wenn ich es schon mit 3 getan habe?
Von 3 aufeinander folgenden Zahlen sind immer mind. eine davon durch 2 teilbar und eine durch 3.
Es bleibt immer ein Element übrig, was nicht durch 3 und 2 teilbar ist. Dieses Element ist zu Primzahlen-Check zu verwenden.
Also ich habe es wie gesagt erstmal mit VBasic gemacht und war auch sehr enttäuscht. Es ging viel zu schnell.
Er zeigte mir fast immer 0,03 Millisekunden an (bei 2147483647).
Dann habe es 100mal wiederholen lassen und es kamen die theoretischen 3 MSekunden aus (Durchschnitt war meist bei 2,5 ms).
zmaster
@Devil81: is ne idee! lohnt sich auch erst bei 2000 Primzahlen!
EDIT: Das Ergebnis wird nach 100 Durchläufen in Sekunden angegeben!
Das Ergebnis also *10 und ihr habt in ms raus, wielange es pro Durchlauf gedauert hat! |
ich hab mal dein programm getestet mit 1234567876543212 und bekomme immer nen error (runtime error '6') xD vieleicht mache ich ja was flasch
ich versuche gerade diesen kontest im info unterricht zu bringen weil fakultäts berechnung ist langweilig xD
__________________
Frage: Was ist ein FTP-Server?
Antwort: Es antwortet LG Braunschweig, Urteil vom 21.7.2003:
FTP-Server sind Systeme, in denen gecrackte, also nach Überwindung des Vervielfältigungsschutzes kopierte, Software geladen ist
|
|
|
12.02.2007 08:56 |
|
|
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 |
|
|
|
|
 |
|
laufzeit