BlackBoard (http://www.black-board.net/index.php)
- Design, Programmierung & Entwicklung (http://www.black-board.net/board.php?boardid=55)
-- Programmieren (http://www.black-board.net/board.php?boardid=4)
--- Programmiersprachenkontest: Primzahlüberprüfung (http://www.black-board.net/thread.php?threadid=10588)

Geschrieben von CDW am 23.02.2003 um 18:55:

  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 Augenzwinkern (bitte keine Anmerkungen,á la "jede Sprach hat ihre Vorteile - das weiß ich ja auch smile )
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?


Geschrieben von phlox81 am 23.02.2003 um 21:00:

 

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


Geschrieben von Zmaster am 23.02.2003 um 21:22:

Fragezeichen 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


Geschrieben von Rabenicht am 23.02.2003 um 21:59:

 

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 )


Geschrieben von Zmaster am 24.02.2003 um 09:45:

Achtung 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


Geschrieben von Compuholic am 24.02.2003 um 10:32:

 

Ich fände es schon interessant. Jetzt nicht aus dem Aspekt heraus, wer den besten Algorithmus hat, sondern einfach mal um den Geschwindigkeitsunterschied der verschiedenen Programmiersprachen zu testen.

So würde ich gerne mal sehen welchen Geschwindigkeitsvorteil ASM vor C hat (auch Java wäre bestimmt interessant smile ). Wichtig wäre dafür nur, das wir alle das gleiche Verfahren benutzen.

@Zmaster: nicht nur die Hälfte der Elemente fliegt raus. Sondern es reicht bis zur Quadratwurzel der Zahl zu testen.


Geschrieben von CDW am 24.02.2003 um 11:42:

 

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...


Geschrieben von Zmaster am 24.02.2003 um 17:20:

Achtung verraten

@Compuholic:
Du bist gemein! Augenzwinkern
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


Geschrieben von LX am 24.02.2003 um 17:49:

Achtung RE: verraten

Zitat:
Original von Zmaster
Zur Zeit liegt meine Laufzeit bei sqrt(n)/3 (natürlich so, dass nicht zu viele Kontrollstrukturen drinne sind)!
Wenn du nur bis zu einem Drittel der Wurzel prüfst, dann wirst du mächtig auf die Nase fallen, oder wie willst du prüfen, ob 25, 49 oder 81 z.B. Primzahlen sind? *g


Geschrieben von CDW am 24.02.2003 um 17:54:

 

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 smile )
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)


Geschrieben von LX am 24.02.2003 um 18:08:

Achtung

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 smile )


Geschrieben von CDW am 24.02.2003 um 19:45:

 

LX: die minimale Anzahl liegt noch weiter drunter:
bei diesem Verfahren.
Zahl:49
Wurzel:7
brauchst du zwar 7 Durchläufe:
49/2;49/3;49/4;49/5;49/6;49/7;
aber du kannst getrost nach dem 49/2; alle geraden Zahlen überspringen Augenzwinkern also für mich: sqrt(n)/2
Übrigens hat sich der Mehraufwand für die Wurzel gelohnt:
für die obengenannte Zahl brauch ich nur noch 1 ms(ohne überspringen der geraden Zahlen ganze 2-3ms): somit stellt das den Sinn des Kontests bzw die Durchführbarkeit in Frage, da der Zeitunterschied mikrieg klein ist.
Naja,ich stelle mein momentanes Ergenbiss zur Verfügung:
es ist die EXE,sowie der Source und alle anderen, zum Compilen nötigen Projektdateien (5.45KB)
Compiliert:MASM32 (ML.EXE, Version 6.14.8444)
Sprache:ASM
OS:Win , getestet auf win2k, müsste aber auf jedem laufen. Hat eine GUI *g*
http://www.cdw.de.vu/Prim.zip


Geschrieben von phlox81 am 24.02.2003 um 20:27:

 

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


Geschrieben von Zmaster am 24.02.2003 um 21:13:

verrückt laufzeit

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!


Geschrieben von CDW am 24.02.2003 um 21:26:

 

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 Augenzwinkern 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...


Geschrieben von Zmaster am 24.02.2003 um 21:38:

  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


Geschrieben von LX am 24.02.2003 um 22:13:

Achtung 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.
Und ich hab das Gefühl, du solltest meinen letzten Beitrag nochmal durchlesen Augenzwinkern

Zitat:
von mir:
Die minimale Anzahl Vergleiche liegt bei der Anzahl der Primzahlen kleiner oder gleich der Quadratwurzel der zu prüfenden Zahl.


Von der Anzahl her reichen in der Theorie weit weniger als sqrt(n)/3 Berechnungen, allerdings ging ich davon aus, du willst nur durch Werte kleiner als sqrt(n)/3 dividieren.


Geschrieben von Compuholic am 25.02.2003 um 16:35:

 

@CDW:

ich könnt den Kopf gegen die Tastatur hauen. Als ich mir Dein Programm angesehen habe, habe ich gesehen das Du fsqrt zum Ziehen der Quadratwurzel benutzt. Ich Idiot fang großartig an das Teil nach Newton zu berechnen *g*

Wen es interessiert:
code: 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:

CalcSqrt    PROC    lInput : DWORD

    LOCAL   LastStep : DWORD
    LOCAL   Result : DWORD

    mov     LastStep, 0
    mov     ecx, 10                     ;# 10 Iterationsschritte
    finit                               ;# FPU initialisieren
    fild    lInput                      ;# Ausgangszahl auf ST(0) pushen
    fstp    LastStep                    ;# Iterationzwischenspeicher mit ST(0) initialisieren
    
    itnext:
    fld     LastStep                    ;# Quadratwurzel nach dem Newton-Verfahren berechnen
    fild    lInput
    fdiv    st(0), st(1)
    fadd    st(0), st(1)
    fmul    sqrtdata1
    fstp    LastStep
    fstp    Result
    loop    itnext

    fld     LastStep                    ;# Ergebnis in ST(0) laden
    fistp   Result                      ;# ST(0) in Integer konvertieren und speichern
    mov     eax, Result                 ;# Ergebnis in eax und zurückspringen
    ret
    
CalcSqrt ENDP


Eine andere Sache. Die Primzahlberechnung würde sich da viel effizienter mit MMX bzw. SSE lösen lassen. Wenn Die Zahl 32-Bit breit ist kann man in den 64-Bit Registern immer 2 Tests gleichzeitig durchführen. Daher meine Frage: Hast Du schon mal ein bisschen mit diesen Funktionen herumgespielt? Ich habe 2 Hauptprobleme:

MMX arbeitet nur mit Ganzzahlen und es fehlt ein "div" Befehl. SSE kann mit Floats arbeiten. Da Problem hier lieht darin: Wie konvertiere ich die Ganzzahl in eine Fließkommazahl und packe sie ins High-Order DWORD?


Geschrieben von CDW am 25.02.2003 um 18:23:

 

Zmaster: jetz ist die Welt wieder in Ordnung für mich Augenzwinkern - weil ich mir schon dachte, wie es sein kann, dass VB genausoschnell wie asm ist und hatte schon vor, komplett auf C umzusteigen smile : 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.


Geschrieben von Misel am 11.02.2007 um 14:57:

 

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.


Forensoftware: Burning Board 2.3.6, entwickelt von WoltLab GmbH