µit - September

Noch ein Kandidat! Klasse!
Jetzt musst Du Dich aber ranhalten. Wir anderen haben ja schon einigen Vorsprung.
Allerdings ist bei mir das Ende auch schon erreicht. Finde einfach keine Optimierungsmöglichkeiten mehr.

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

Erklärung zu meinem Skript:

peethebee

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.

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.

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?

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.

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:

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

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