µit - September

  • Servus hi,


    bin dabei, mir zu überlegen, ob ich miteinsteig - müsste nur wissen, ob Abgabe am Freitag oder am 27.9. ist ;)


    lg~markus

  • So! :D


    Da ich diese Woche Urlaub habe, habe ich mir viel Zeit genommen und mich auch mal mit dem September-Wettbewerb beschäftigt.
    Nach einigen (sehr vielen) Stunden ist jetzt eine lauffähige Version entstanden. Leider noch sehr langsam und sehr groß. Aber ich werde noch daran feilen.


    Walle bekommt die Files per PN.



    Gruß funkey

  • Ich bitte nochmal alle Teilnehmer, auch wenn es keine aktueller Version gibt als die >>>GEPOSTETE<<< mir die VErsion als >>PN<< zuschicken.


    Einfach die beiden au3`s


    Danke.
    Walle

    Flensburg ist wie Payback - wenn man 18 Punkte hat bekommt man ein Fahrrad.

  • Zitat von Waluev

    4. Abgabe
    Die Lösungen werden bitte in einem mit Passwort geschützten Archiv (*.rar oder *.zip), sobald man fertig ist gepostet. Das PW schickt ihr dann bitte per PN an mich.
    Zwischen einer Stunde vor und einer Stunde nach dem Abgabetermin wird das Passwort dann bitte unter den jeweiligen Beitrag hinzugefügt (damit sich dann jeder andere auch die Skripte anschauen kann) und nicht in einem neuen Post geliefert um die Übersicht zu waren.


    Zitat von Waluev

    Ich bitte nochmal alle Teilnehmer, auch wenn es keine aktueller Version gibt als die >>>GEPOSTETE<<< mir die VErsion als >>PN<< zuschicken.


    Einfach die beiden au3`s


    Danke.
    Walle


    Ist das mit der PN nur diesmal so?

  • So,
    Dann mache ich mal meine finale Abgabe.


    Size:
    598 Bytes (ja, ich habe noch 9 sinnlose Bytes gefunden :D)
    Laufzeit beim kurzen Skript (nicht gewertet):
    Average: 0.7583 sec.
    Minimum: 0.7412 sec.
    Maximum: 0.8235 sec.
    (so schnell war mein schnelles Skript als ich gesagt habe "Es geht nicht mehr schneller" ;)).


    Speed:
    Average: 0.0759 sec.
    Minimum: 0.0715 sec.
    Maximum: 0.0830 sec.
    (alle Zeiten minus ein paar Prozent bei Waluev)
    Größe dieses Skriptes (nicht gewertet): 2693 Bytes


    Auf geht's zum letzten Optimieren!
    Bin gespannt auf eure Tricks :).


    Edit: Passwort: wassport


    peethebee

  • So, Abgabetermin ist rum.
    Auch wenn ich nicht auf dem Podest lande, hier meine SpeedVariante (ca. 0,12 sec).

  • Dann poste ich auch mal meine beiden letzten Versionen.
    Ich bin mir nicht sicher, ob diese Scripte auch für beliebig lange Zahlen funktionieren...


    myBigInt_Size:


    myBigInt_speed:


    Passwort für meine anderen, hochgeladenen Versionen: ävSVZmnhZ93GWQ3!


    lgE

  • Meine beiden Scripte:


    Size:


    Speed:

  • Hi,
    ich bin gerade am Ausprobieren der Versionen von Euch. Bei eukalyptus ist mir aber sofort ein Fehler aufgefallen:
    Durch Verwendung des kurzen Strings in der Schleife bei ADD spart er schön Zeit ;) ... aber der Speicherüberlauf geht verloren. Außerdem ist die Länge des Ergebnisstrings nicht passend.
    Laßt mal in allen Euren Skripts folgende Aufgabe durchlaufen:
    $BigInt_1 = _StringRepeat('9', 180)
    $BigInt_2 = _StringRepeat('9', 90)


    ConsoleWrite(_BigInt_Add($BigInt_1, $BigInt_2) & @CRLF)Das Ergebnis muß 181 Stellen haben mit Überlauf bis zur ersten Position.

    Code
    1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000999999999999999999999999999999999999999999999999999999999999999999999999999999999999999998


    Für die MUL gilt das analog. Das Ergebnis bei eukalyptus ist nur 222 Stellen lang. 180 9en mal 90 9en müssen aber logischerweise 180 +90 ==> also 270 Stellen werden.

    Code
    999999999999999999999999999999999999999999999999999999999999999999999999999999999999999998999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001


    Ich denke mal, da wird der Benchmarktest nicht allen Erfordernissen im geforderten Zahlenbereich bis 200 Stellen Länge gerecht.


    Edit


    Ich habe die vorangestellte Aufgabe mit den Versionen von eukalyptus, peethebee, Oscar und mir getestet. Außer bei eukalyptus wird überall das richtige Ergebnis geliefert.
    @eukal: Na, wohl doch etwas überoptimiert? :whistling:

  • Na logisch hab ich überoptimiert :P - hab ich aber gesagt, daß mein Script fehlerhaft laufen würde, wenn die Zahlen zb. 99999999... hätten!


    dann hier noch meine vorletzte Version vom 9 September (mit der geht der Bugfix-Test)
    Average: 0.0385 sec.
    Minimum: 0.0336 sec.
    Maximum: 0.0448 sec.



    Ich versuch mal meine Multiplikation zu erklären, anhand 456*123:


    Oscar: Guter Trick mit Int() gleich 18 stellige Zahlen zu berechnen! :thumbsup:


    lgE

  • eukalyptus: Naja, ich fand den Trick eigentlich nicht so bedeutend. Die maximale Stellenzahl bei der Addition mit "64 Bit Signed Int" halt. Bei der Multiplikation entsprechend 9 Stellen.


    Aber kommen wir zur Erklärung meiner Funktionen.
    Bei _BigInt_Add wird zunächst festgestellt welche der beiden Zahlen größer ist und ggf. in einem Ringtausch ausgetauscht, um diese dann für die For...Next-Schleife zu verwenden. Anschließend werden beide Zahlen in 18stellige "Häppchen" aufgeteilt, die dann jeweils addiert werden. Der Übertrag wird bei der nächsten Addition dazuaddiert. Das ist wohl soweit verständlich (hoffe ich).



    Bei _BigInt_Mul wird es etwas komplizierter, weil ich von der "Schulmethode" doch etwas abweiche. Zunächst werden die beiden Zahlen in 9stellige "Häppchen" aufgeteilt. Wobei das Ganze von Rechts nach Links vor sich geht. Das heißt, Array[0] enthält eine variable Anzahl an Stellen mit 1...9 Stellen. Alle anderen Array-Elemente sind 9stellig. Im Nachfolgenden nenne ich sie mal Blöcke. Zur besseren Unterscheidung der beiden Zahlen verwende ich außerdem zwei verschiedene Farben (ich hoffe dadurch wird das verständlicher).


    Dann gehe ich so vor, dass der letzte 9er-Block der zweiten Zahl mit dem letzten 9er-Block der ersten Zahl multipliziert wird. Vom Ergebnis dieser Multiplikation werden die letzten 9 Stellen in eine temporäre Stringvariable abgelegt, die vorderen Stellen gehen als Übertrag in die nächste Multiplikation ein. Es folgt die Multiplikation des letzten 9er-Blocks der zweiten Zahl mit dem vorletzten 9er-Block der ersten Zahl. Der temporären Stringvariablen werden wieder die letzen 9 Stellen der Multiplikation hinzugefügt, allerdings werden diese immer links hinzugefügt also nicht einfach angehängt. So geht es weiter bis der letzte 9er-Block der zweiten Zahl mit allen Blöcken der ersten Zahl multipliziert wurde.


    Die temporäre Stringvariable entspricht nun dem Multiplikationsergebnis der gesamten ersten Zahl mit dem letzten Block der zweiten Zahl. Dieses "Zwischenergebnis" addiere ich nun, mit Hilfe von _BigIntAdd, zu der Ausgabevariable dazu.
    Anschließend geht es mit dem vorletzten Block der zweiten Zahl weiter. Dieser wird ebenfalls mit allen Blöcken der ersten Zahl multipliziert, es wird wieder eine temporäre Stringvariable erstellt und diese wird wieder der Ausgabevariablen hinzuaddiert. Allerdings werden der temporären Stringvariablen vorher noch 9 Nullen angehängt, sodass das Zwischenergebnis weiter eingerückt wird (Stellenwertigkeit).
    Das geht dann so weiter, bis schließlich der erste Block der zweiten Zahl mit allen Blöcken der ersten Zahl multipliziert wurde.


    Ich muss feststellen, dass es beinahe schwerer ist, das zu erklären als es zu programmieren. ;)

  • Oscar: Doch! Den Trick hast nur du benutzt.
    Autoit kann 18 stellige Zahlen berechnen (64Bit), doch Stringzahlen gehen nur bis 14 stellen!?!
    $String_a="999999999999999999"
    $String_b="999999999999999999"
    $Int_a=999999999999999999
    $Int_b=999999999999999999
    MsgBox(0,"Int",$Int_a + $Int_b) ; = 1999999999999999998
    MsgBox(0,"String",$String_a + $String_b) ; = 2e+018
    MsgBox(0,"Int(String)",Int($String_a) + Int($String_b)) ; = 1999999999999999998

    Zumindest Bugfix, Funkey und ich haben "nur" mit 14 Stellen gerechnet...
    Und pro Rechenschritt gleich 4 Stellen mehr zu verarbeiten bringt doch enorm viel Zeitersparnis.


    Edit (zu meiner Erklärung oben): theoretisch sollte meine Multiplikation 140000-stellige Zahlen schaffen, bevor ein Arraywert die 64Bit Grenze sprengt. Allerdings benötigt das Multiplizieren von zwei 20000-stelligen Zahlen schon 70 Sekunden, somit sollte man sich beim Berechnen von viel größeren Zahlen einen Rasierapparat bereitlegen ;)

  • So nun auch erstmal stateme(a?)nt von mir^^


    Also erstmal freu ich mich über die aktive Teilnahme und die zahlreichen erklärungen zu den Skripten hier im Nachhinein.
    Da ich am Wochenende meinen PC neu gemacht habe und jetzt auch viel bessere Hardware habe, werden die Benchs jetzt im Wert noch niedriger ausfallen.



    Allerdings brauche ich noch ein paar Tage bis ich meinen PC soweit fit hab, dass alles läuft (Vista = viele Probleme bevor alles läuft ;) [und nein pee, ich will trotzdem kein Linux :-P])


    Ich setze die Deadline zur Auswertung auf den 4.10.2008, aber ich denke ich schaffs schon eher.



    Ich bitte auch wirklich nochmal alle Leute, die mir ihr Sktipt noch nicht per PN geschickt haben, das zu tun.



    Walle

    Flensburg ist wie Payback - wenn man 18 Punkte hat bekommt man ein Fahrrad.

  • Hallo!



    Da Waluev im Moment keine Zeit hat, mache ich mal die vorläufige Auswertung für den September. Ich hoffe, ihr vertraut mir ;).


    Waluev hat mir ein Paket mit den Skripten geschickt, ich hoffe, dass die alle aktuell waren, wenn nicht, dann bitte melden :).



    Zu den Skripten:



    azunai:


    Speed: Nicht zu bewerten, Tests laufen nicht durch wegen des langsamen, wenn nicht untauglichen Ansatzes


    Size: 453 Bytes (aber nicht gewertet, da der Ansatz leider nicht funktoiniert, siehe spätere Posts)


    Kommentar: Der Ansatz ist spaßig, es wird eine Textdatei geschrieben, die gerade so viele Zeichen enthält wie das Ergebnis dezimal wert ist. Ich kann es im Moment nicht widerlegen, bitte daher um mehr Input, aber die Idee funktioniert nur, wenn auch folgendes Konstrukt funktioniert:

    Zitat

    For $i=1234567891234567891123123123123213 to 12345678912345678911231231231232131 Next

    Das wiederum würde aber bedeuten, dass AutoIt intern eine BigInt-Bibliothek hätte und dann wäre es Unsinn die nicht nach außen nutzbar zu machen. Der Code liefert aber keine Fehlermeldung. Kann jemand zur Klärung beitragen?



    BugFix:


    Speed:


    Average: 0.1337 sec. (1337 :D)


    Minimum: 0.1247 sec.


    Maximum: 0.1403 sec.


    Size: 2139 Bytes


    Kommentar: Size-Skript nicht platzoptimiert (Leerzeichen, Tabs, ...). Skriptfunktion hat BugFix schon selbst erklärt.



    eukalyptus:


    Speed:


    Average: 0.0454 sec.


    Minimum: 0.0420 sec.


    Maximum: 0.0499 sec.


    Size: 590 Bytes


    Kommentar: Skript schon erklärt.



    funkey:


    Speed:


    Average: 0.0740 sec.


    Minimum: 0.0698 sec.


    Maximum: 0.0771 sec.


    Size: 1400 Bytes


    Kommentar:



    goliath:


    Speed:


    Average: 0.9993 sec.


    Minimum: 0.9920 sec.


    Maximum: 1.0078 sec.


    Size: 1943 Bytes


    Kommentar:



    GtaSpider:


    Speed:


    Average: 1.0548 sec.


    Minimum: 1.0388 sec.


    Maximum: 1.0785 sec.


    Size: 631 Bytes


    Kommentar:



    Oscar:


    Speed:


    Average: 0.0520 sec.


    Minimum: 0.0477 sec.


    Maximum: 0.0580 sec.


    Size: 724 Bytes


    Kommentar: Sehr langsames Size-Skript (aber das ist ja nicht verboten :D)



    peethebee:


    Speed:


    Average: 0.0784 sec.


    Minimum: 0.0713 sec.


    Maximum: 0.0914 sec.


    Size: 598 Bytes


    Kommentar: Skript bereits erklärt.



    Tom99:


    Speed:


    Average: 0.4924 sec.*


    Minimum: 0.4812 sec.*


    Maximum: 0.5043 sec.*


    Size: 1637 Bytes*


    Kommentar:* _BigInt_Mul nicht ausprogrammiert, Zeiten nur von Add




    Damit zum Speed-Titel, der im September an eukalyptus geht.


    Mit 0.0454 sec. Durchschnittszeit gewinnt er knapp vor Oscar.



    Die Platzierungen:
    1. eukalyptus: 0.0454 sec.
    2. Oscar: 0.0520 sec. (+0.0066)
    3. funkey: 0.0740 sec. (+0.0286)
    4. peethebee: 0.0784 sec. (+0.0330)
    5. BugFix: 0.1337 sec. (+0.0883)
    6. goliath: 0.9993 sec. (+0.9539)
    7. GtaSpider: 1.0548 sec. (+1.0094)
    8. Tom99: 0.4924 sec.*
    -. azunai: x.xxxx sec.


    Auch der Size-Titel geht in diesem Monat an eukalyptus.


    Tabelle:
    1. eukalyptus: 590 Bytes
    2. peethebee: 598 Bytes
    3. GtaSpider: 631 Bytes
    4. Oscar: 724 Bytes
    5. funkey: 1400 Bytes
    6. Goliath: 1943 Bytes
    7. BugFix: 2139 Bytes
    8. Tom99: 1637 Bytes*
    -. azunai: 453 Bytes (funktioniert so nicht)


    Wir gratulieren eukalyptus ganz herzlich zum Doppelsieg. Meiner Meinung nach sind unglaubliche Beschleunigungen herausgekommen.


    Dass man solche Berechnungen auch mit AutoIt in unfassbar kurzer Zeit durchführen kann, ist schon Wahnsinn. Vor allem zeigen die Fortschritte, dass zwischen den ersten Ideen bei über einer Sekunde Laufzeit und dem Sieg mit vier Hundertstel-Sekunden ein Optimierungsfaktor von mindestens 25 liegt.


    Ich denke, dass jeder, der sich hier intensiv beschäftigt hat, einiges darüber gelernt hat, wie man einen Algorithmus beschleunigen kann und was speziell in AutoIt gut oder eben langsam ist.



    Danke für die rege Beteiligung, es hat mir großen Spaß gemacht!



    Was eine richtig coole Sache wäre, wäre wenn wir eine BigInt-UDF zusammenbekommen würden und dazu die besten Ideen kombinieren falls möglich :). Würde ich auch gerne im englischen Forum posten :).



    peethebee, auch im Namen von Waluev