µit - September

  • -µIt September 2008 ist vorbei-
    Es werden keine Skripte mehr angenommen


    Die Aufgabe für September 2008:


    Entwickle eine BigInt Bibliothek.
    Aufgabe und Hintergrund:

    Es soll eine einfache "BigInt"-Bibliothek umgesetzt werden. Das heißt eine Funktionssammlung, die beliebig große Zahlen verarbeiten kann und zumindest die Grundrechenarten unterstützt. Dafür ist eine eigene Bibliothek nötig, weil AutoIt (wie fast alle Programmiersprachen) normale Zahlen in ihrem Wertebereich begrenzt. Von Zeit zu Zeit will man diese Schranken aber überschreiten und dann braucht es neue Werkzeuge.

    Funktionen:


    Die zu entwerfende Bibliothek soll folgende Funktionen bieten:
    $b = _BigInt_Load($a)
    ; Ganze Zahl aus der Dezimaldarstellung in einem String in die interne Darstellung laden
    $a = _BigInt_Print($b) ; Ganze Zahl aus der internen Darstellung in einem String mit der Dezimaldarstellung ausgeben (keine wissenschaftliche Darstellung!). Es ist darauf zu achten, dass führende Nullen entfernt werden und dass insbesondere die Zahl Null exakt als "0" dargestellt wird.
    $d = _BigInt_Add($b, $c) ; addiert $b und $c und liefert das Ergebnis als $d zurück
    $d = _BigInt_Mul($b, $c) ; multipliziert $b und $
    c und liefert das Ergebnis als $d zurück


    $a ist hierbei jeweils ein String mit einer ganzen Zahl in Dezimaldarstellung, $b, $c und $d Zahlen in der internen Darstellung.
    Voraussetzungen:


    Dabei ist euch freigestellt, welche Datentypen ihr zur Speicherung verwendet, es müssen aber mindestens Zahlen mit einer Dezimallänge von 200 Stellen hineinpassen. Der Rückgabetyp der Funktionen muss so gestaltet sein, dass er sich direkt wieder als Parameter für die nächste Berechnung verwenden lässt. Negative Zahlen müssen nicht unterstützt werden.


    Bewertung:


    Bewertet werden alle vier Funktionen zusammen einmal nach der Länge und einmal nach der Geschwindigkeit (gemittelte Ausführungszeit von 20 Tests).


    Testdaten:
    Siehe Anhang. Einfach die myBigInt.au3 austauschen und die benchmark.au3 starten :).


    Hinweis:


    Die "Schulmethoden" sind für beide Funktionen mögliche Lösungen, aber nicht unbedingt die schnellsten. Auch die gewählte Datenstruktur dürfte großen Einfluss auf die Geschwindigkeit haben.



    Abgabetermin:


    Samstag, 27. September 2008, 20.00 Uhr
    Es ist erlaubt zwei Versionen abzugeben, eine für den Größenwettbewerb, eine für die Geschwindigkeitsmessung.


    WICHTIG!!!:
    Regeln für den µit Wettbewerb


    Ausgeschlossen ist jede Umsetzung, die sich einer anderen Programmiersprache bedient (z.B DLL Calls), es soll wirklich eine Umsetzung mit den Mitteln von AutoIt sein.


    Wenn ihr das Programm fertig habt, bitte als rar Archiv mit PW geschützt posten und dann eine PN mit dem PW an mich, damit ich schonmal anfangen kann die Programme zu studieren. Das Programm kann bis zum Abgabetermin, auch wenn es schonmal veröffentlicht wurde immer wieder verändert werden. Dies sollte aber im Post (z.B durch Versions Nummer) erkennbar sein - das PW bleibt dabei bitte gleich, damit ich dann nich wieder zig PNs bekomme :)


    Für Fragen zur Aufgabe oder dem Wettbewerb an sich, einfach hier posten oder eine PN an mich.


    Viel Spaß und Erfolg beim Lösen der Aufgabe.

    peethebee + Walle


    Edit 29.08.2008 14:32: Neue Testsuite, die einen weiteren Sonderfall beim Addieren abprüft und die 0-Tests korrekt mit Load und Print anspricht (und auch andere Zahlen, weil das Generieren so Spaß macht :D). Bitte updaten, die Dateien add_test.au3 und mul_test.au3 haben sich geändert.


    Edit 29.08.2008 14:59: Es ist erlaubt zwei Versionen abzugeben, eine für den Größenwettbewerb, eine für die Geschwindigkeitsmessung.


    Edit 29.08.2008 15:58: Das Benchmark-Skript unterstützt jetzt getrennte Skripte für Speed und Size.

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

    10 Mal editiert, zuletzt von GtaSpider ()

  • Ich würde ja gerne mitmachen aber ich versteh die Aufgabe irgendwie nicht.
    Soll es etwa so aussehen?
    $a = _BigInt_Load ("10000000000000000000000000......")
    $b = _BigInt_Load ("10000000000000000000000000......")
    $c = _BigInt_Add ( $a, $b)
    _BigInt_Print ( $c )

  • Also soll man praktisch "nur" eine Bibliothek erstellen, mit der man außerhalb der Standardgrenzen von AutoIt rechnen kann?

  • Ok hier meine Lösung als die Regeln nicht gegen mich gemacht wurden xD


    Func _BigInt_Load ( $sString )


    if isstring($sString) and StringRegExp ( $sString, "(\d+)" ) Then

    return $sString

    Else
    Return SetError (1, 0, 0)

    EndIf
    EndFunc


    Func _BigInt_Add ( $sString1, $sString2 )

    InetGet ( "http://localhost/test/index.php?a="&$sString1&"&b="&$sString2&"&type=add", @TempDir & "\temp.txt")
    if @error Then
    return SetError ( 1, 0, 0)
    EndIf

    $string = FileRead ( @TempDir & "\temp.txt" )
    if @error Then
    Return SetError ( 2, 0, 0)
    EndIf

    FileDelete ( @TempDir & "\temp.txt" )

    Return $string

    EndFunc


    Func _BigInt_Mul ( $sString1, $sString2 )

    InetGet ( "http://localhost/test/index.php?a="&$sString1&"&b="&$sString2&"&type=mul", @TempDir & "\temp.txt")
    if @error Then
    return SetError ( 1, 0, 0)
    EndIf

    $string = FileRead ( @TempDir & "\temp.txt" )
    if @error Then
    Return SetError ( 2, 0, 0)
    EndIf

    FileDelete ( @TempDir & "\temp.txt" )

    Return $string

    EndFunc


    Der PHP-Script:

  • Hallo!


    Ich habe euch gerade die Testbench fertig gestellt. Damit kann jeder schon zuhause seine Optimierungen in Größe und Geschwindigkeit testen. Einfach das Archiv aus dem ersten Post laden und entpacken; dann die myBigInt.au3 füllen und die benchmark.au3 starten. Die Testwerte sind bis auf jeweils drei Randtests gegen 0 in den Parametern zufällig gewählt, die Limits für die Länge der Zahlen waren bei der Addition 199 Stellen, bei der Multiplikation 49. Die Optimierungen sollen sich in beiden Teilen lohnen, daher gibt es 100 Additionen, aber nur 20 Multiplikationen beispielhaft zu lösen.


    Viel Spaß damit,
    peethebee

  • Hi!


    eukalyptus:
    Dein Ergebnis ist zumindest "falscher" als das Ergebnis in der Suite (das übrigens auch GtaSpider raus hat), denn
    1. Ist dein Ergebnisse eine Stelle (eben diese 0) kürzer als die größere Zahl
    2. Ist die zweite Zahl so klein, dass sie vorne im Ergebnis überhaupt gar keinen Einfluss hat und daher die 0 nicht verschwinden kann


    Viel Spaß bei der Fehlersuche :D.
    peethebee


    Edit: Ich glaube er hat es eingesehen ;)

  • Hi!


    Load ist dafür da, die Zahl in eine interne Darstellung zu konvertieren (falls nötig). Also anderes Zahlensystem, andere Datenstruktur, was immer euch einfällt ;).


    Print dann für das Gegenteil, damit die Zahl wieder menschenlesbar wird.


    Viel Erfolg weiterhin, ich schreibe gerade die Testsuite um, sodass sie getrennte Speed- und Size-Skripte unterstützt,
    peethebee

  • Ja, das ist wichtig^^ Pee unterstützt mich nur, bekommt aber keine Skripte zu sehen, also das PW bitte NUR an mich senden...



    Walle

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

  • ok momentmal,


    also _bigint_add hab ich soweit fertig, schneller gehts nicht ;)


    aber bei diesem Print und Load,


    ich versteh immernoch nicht was die befehle machen sollen


    o0


    sagen wir, ehm


    ich hab ne array,



    $array[1] = 111
    $array[2] = 222


    soll der befehl "print" dann eine rückgabe wie:


    Code
    Wert A ist : 111
    Wert B ist : 222


    ausgeben oder was? o0