µ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?

    • Offizieller Beitrag

    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

    • Offizieller Beitrag

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

    Spoiler anzeigen
    [autoit]

    #include-once

    [/autoit] [autoit][/autoit] [autoit]

    Func _BigInt_Load($S)
    Return $S
    EndFunc ;==>_BigInt_Load

    [/autoit] [autoit][/autoit] [autoit]

    Func _BigInt_Print($S)
    Return $S
    EndFunc ;==>_BigInt_Print

    [/autoit] [autoit][/autoit] [autoit]

    Func _BigInt_Add(ByRef $1, ByRef $2)
    Local $l1 = StringLen($1), $l2 = StringLen($2), $s0 = ''
    Select
    Case $l1 > $l2
    For $j = 1 To $l1 - $l2
    $s0 &= '0'
    Next
    $2 = $s0 & $2
    Case Else
    For $j = 1 To $l2 - $l1
    $s0 &= '0'
    Next
    $1 = $s0 & $1
    EndSelect
    Local $ue = '0', $out = '', $tmp, $tlen, $s0
    While StringLen($1) > 14
    $tmp = StringRight($1, 14) + StringRight($2, 14) + $ue
    $tlen = StringLen($tmp)
    Switch $tlen
    Case 0 To 13
    $s0 = ''
    For $j = 1 To (14 - $tlen)
    $s0 &= '0'
    Next
    $tmp = $s0 & $tmp
    $ue = '0'
    Case 14
    $ue = '0'
    Case Else
    $ue = StringLeft($tmp, 1)
    EndSwitch
    $out = StringRight($tmp, 14) & $out
    $1 = StringTrimRight($1, 14)
    $2 = StringTrimRight($2, 14)
    WEnd
    Return ($1 + $2 + $ue) & $out
    EndFunc ;==>_BigInt_Add

    [/autoit] [autoit][/autoit] [autoit]

    Func _BigInt_Mul(ByRef $1, ByRef $2)
    If $1 = '0' Or $2 = '0' Then Return '0'
    $l = StringLen($1)
    If $l < 8 Then
    Local $a1[1] = [$1]
    Else
    Local $a1[Floor($l / 7) + 1]
    For $i = 0 To UBound($a1) - 2
    $sZ = ''
    For $j = 1 To ($l - ($i + 1) * 7)
    $sZ &= '0'
    Next
    $a1[$i] = StringLeft($1, 7) & $sZ
    $1 = StringTrimLeft($1, 7)
    Next
    $a1[UBound($a1) - 1] = $1
    EndIf
    $l = StringLen($2)
    If $l < 8 Then
    Local $a2[1] = [$2]
    Else
    Local $a2[Floor($l / 7) + 1]
    For $i = 0 To UBound($a2) - 2
    $sZ = ''
    For $j = 1 To ($l - ($i + 1) * 7)
    $sZ &= '0'
    Next
    $a2[$i] = StringLeft($2, 7) & $sZ
    $2 = StringTrimLeft($2, 7)
    Next
    $a2[UBound($a2) - 1] = $2
    EndIf
    Local $sum = 0
    For $i = 0 To UBound($a1) - 1
    For $j = 0 To UBound($a2) - 1
    $x = (StringLeft($a1[$i], 7) * StringLeft($a2[$j], 7)) & StringTrimLeft($a1[$i], 7) & StringTrimLeft($a2[$j], 7)
    $sum = _BigInt_Add($sum, $x)
    Next
    Next
    Return $sum
    EndFunc ;==>_BigInt_Mul

    [/autoit] [autoit][/autoit] [autoit][/autoit]
  • 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:

    Spoiler anzeigen
    [autoit]

    #include-once
    Func _BigInt_Add($a,$b)
    If $a[0]<$b[0]Then
    $S=$a
    $a=$b
    $b=$S
    EndIf
    For $i=1 To $a[0]
    If $i>$a[0]-$b[0]Then $a[$i]+=$b[$i-($a[0]-$b[0])]
    Next
    Return $a
    EndFunc
    Func _BigInt_Mul($a,$b)
    Local $E[$a[0]+$b[0]]=[$a[0]+$b[0]-1]
    For $i=1 To $b[0]
    For $j=1 To $a[0]
    $E[$j+$i-1]+=$a[$j]*$b[$i]
    Next
    Next
    Return $E
    EndFunc
    Func _BigInt_Load($a)
    Return StringSplit($a,"")
    EndFunc
    Func _BigInt_Print($a,$E="",$R=0)
    For $i=$a[0]To 1 Step -1
    $a[$i]+=$R
    $R=Floor($a[$i]/10)
    $E=Mod($a[$i],10)&$E
    Next
    If $R>0 Then $E=$R&$E
    If $E=0 Then $E="0"
    Return $E
    EndFunc

    [/autoit]

    myBigInt_speed:

    Spoiler anzeigen
    [autoit]

    #include-once

    [/autoit] [autoit][/autoit] [autoit]

    Global $L, $R, $E, $T, $i, $j, $C ;Ich verwende 1-stellige Variablen, da ich behaupte, daß das performanceverbesserungen bringt ;)
    ;UND ich deklariere alle als Global, damit die Functions nicht erst deklarieren müssen...

    [/autoit] [autoit][/autoit] [autoit]

    Func _BigInt_Add($a, $b)
    $L = StringLen($b)
    $T = StringLen($a)
    $R=0
    $E=""
    If $L > $T Then $L=$T ;für die Schleife wird die kürzere Zahl genommen; Ich behaupte jetzt, daß die anderen Teilnehmer die längere Zahl verwendet haben...*g* - siehe "Return"
    For $i = $L To 0 Step -15 ;Warum gerade 15? - wenn man Stringzahlen mit Auoit addiert, gehen max 14-stellige Zahlen (beim Benchmark 15 *g*); komischerweise funktionieren bei Integer 18-stellige Zahlen...
    $T = StringRight($a, 15) + StringRight($b, 15) + $R ; Wird addiert lt. Schulmethode incl. Rest, welcher sich erst in der Schleife ergibt
    $a = StringTrimRight($a, 15) ;verarbeitete Stellen steichen
    $b = StringTrimRight($b, 15)
    $R = Floor($T / 1000000000000000) ;Rest wird ermittelt
    $T = Mod($T, 1000000000000000) ;Tatsächlicher Wert, der zu Ergebnis kommt
    If $T <= 100000000000000 Then $T = StringRight("000" & $T, 15) ; Bei Rechenoperationen werden die führenden Nullen gestrichen, wir benötigen aber immer 15-stellige Strings (normallerweise sollten da 15 Nullen sein, bei Pee´s Benchmark reichen aber 3 :))
    $E = $T & $E
    Next
    Return $a&$b&$E ;da ich die kürzere Zahl in der Schleife hab, muß ich den Rest der längeren Zahl vorne dran heften (ka, ob das immer funktioniert, beim Benchmark funzt´s - evtl fehlt bei anderen Zahlen mal ein Rest ?!)
    EndFunc ;==>_BigInt_Add

    [/autoit] [autoit][/autoit] [autoit]

    Func _BigInt_Mul($a, $b) ;die Zahlen werden in ein Array gesplittet und dann lt Schulmethode berechnet; Siehe unten...
    $a = _Split7($a)
    $b = _Split7($b)
    Local $E[$a[0] + $b[0]] = [$a[0] + $b[0] - 1] ;Die Stellenlänge bei MUL ist immer max. Länge_a + Länge_b
    For $i = 1 To $b[0]
    For $j = 1 To $a[0]
    $E[$j + $i - 1] += $a[$j] * $b[$i] ;ich addiere die Multiplikationswerte im Array und lasse sie erst später mit _Merge7() zusammenfügen (Siehe ganz unten; geht das immer, oder kann der Wert die 14 Stellige Autoit-Grenze überscheiten??!)
    Next
    Next
    Return _Merge7($E)
    EndFunc ;==>_BigInt_Mul

    [/autoit] [autoit][/autoit] [autoit]

    Func _Merge7($a) ; Addiert die einzelnen Array-Werte lt. Schulmethode, übergibt den Rest an die nächste usw...(im Prinzip wie bei _BigInt_add)
    $E=""
    $R=0
    For $i = $a[0] To 1 Step -1
    $a[$i] += $R
    $R = Floor($a[$i] / 10000000)
    $T = Mod($a[$i], 10000000)
    If $i > 1 And $T <= 10000000 Then $T = StringRight("00" & $T, 7) ;wieder wie oben, nur halt 7-stellig...
    $E = $T & $E
    Next
    If $R > 0 Then $E = $R & $E
    If $E = 0 Then $E = "0"
    Return $E
    EndFunc ;==>_Merge7

    [/autoit] [autoit][/autoit] [autoit]

    Func _Split7($a) ;Splittet die Zahl in ein Array mit jeweils 7-stelligen Zahlen; Warum 7 ?: weil 7+7=14 und 14-stellige Strings sind das Maximum, was Autoit addieren kann
    $L = StringLen($a)
    $C = Ceiling($L / 7)
    Local $E[$C + 1]
    For $i = $L To 1 Step -7
    $E[$C] = StringRight($a, 7)
    $a = StringTrimRight($a, 7)
    $C -= 1
    Next
    $E[0] = Ceiling($L / 7)
    Return $E
    EndFunc ;==>_Split7

    [/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

    Func _BigInt_Load($a)
    Return $a
    EndFunc ;==>_BigInt_Load

    [/autoit] [autoit][/autoit] [autoit]

    Func _BigInt_Print($a)
    While StringLeft($a, 1) = "0" And StringLen($a) > 1 ;Führende Nullen werden gestrichen (ist schneller als StringRegExpReplace($X,"^[0-]*",""))
    $a = StringTrimLeft($a, 1)
    WEnd
    Return $a
    EndFunc ;==>_BigInt_Print

    [/autoit] [autoit][/autoit] [autoit]

    ;Zu Mul:
    ;Bei der Schulmethode werden die einzelnen Zahlen multipliziert, der Rest weitergegeben und am Schluß die Teilergebnisse addiert... (das geht auch 7-stellig, hab ich in irgendeiner Version auch gemacht...)
    ;ich addiere die einzelnen Multiplikationen im Array und mach das mit dem Restübergeben erst bei _Merge7!
    ;wenn theoretisch ein Array den Wert von 14 Stellen überschreitet, dann gibts evtl. ein Problem! Beim Benchmark geht´s, aber geht das auch mit beliebig langen Zahlen?!?

    [/autoit]

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

    lgE

    • Offizieller Beitrag

    Meine beiden Scripte:

    Size:

    Spoiler anzeigen
    [autoit]


    #include-once
    Func _BigInt_Add($a,$b)
    Local $p=StringSplit($a&'0',''),$q=StringSplit($b&'0',''),$t=$p,$c=0,$o
    If $p[0]<$q[0] Then
    $p=$q
    $q=$t
    EndIf
    For $i=1 To $p[0]-1
    $t=Int($p[$p[0]-$i])+Int($q[$q[0]-$i*($i<$q[0])])+$c
    $c=Int(0+StringTrimRight($t,1))
    $o=StringRight($t,1)&$o
    Next
    If Int($c) Then $o=$c&$o
    Return $o
    EndFunc
    Func _BigInt_Mul($a,$b)
    Local $o,$t,$p=StringSplit($a,''),$q=StringSplit($b,''),$j=$q[0]
    Do
    $k=$p[0]
    Do
    $t=Int($p[$k])*Int($q[$j])
    For $l=1 To $p[0]-$k+$q[0]-$j
    $t&='0'
    Next
    $o=_BigInt_Add($o,$t)
    $k-=1
    Until $k<1
    $j-=1
    Until $j<1
    Return StringRegExpReplace($o,'(\A0+)(.+)','$2')
    EndFunc
    Func _BigInt_Load($a)
    Return $a
    EndFunc
    Func _BigInt_Print($a)
    Return $a
    EndFunc

    [/autoit]

    Speed:

    Spoiler anzeigen
    [autoit]


    #NoTrayIcon
    #include-once
    Func _BigInt_Add($sAdd1, $sAdd2)
    Local $sOut, $sTemp, $iCarry = 0
    If StringLen($sAdd1) < StringLen($sAdd2) Then
    $sTemp = $sAdd1
    $sAdd1 = $sAdd2
    $sAdd2 = $sTemp
    EndIf
    Local $aAdd1 = StringRegExp($sAdd1, '\A\d{' & Mod(StringLen($sAdd1), 18) & '}|\d{18}+', 3), $iCountAdd1 = UBound($aAdd1) - 1
    Local $aAdd2 = StringRegExp($sAdd2, '\A\d{' & Mod(StringLen($sAdd2), 18) & '}|\d{18}+', 3), $iCountAdd2 = UBound($aAdd2) - 1
    For $i = 0 To $iCountAdd1
    If $i <= $iCountAdd2 Then
    $sTemp = Int($aAdd1[$iCountAdd1 - $i]) + Int($aAdd2[$iCountAdd2 - $i]) + $iCarry
    Else
    $sTemp = Int($aAdd1[$iCountAdd1 - $i]) + $iCarry
    EndIf
    $iCarry = Int(0 + StringTrimRight($sTemp, 18))
    $sOut = StringRight('000000000000000000' & $sTemp, 18) & $sOut
    Next
    Return StringRegExpReplace($sOut, '(\A0+)(\d+)', '$2')
    EndFunc

    [/autoit] [autoit][/autoit] [autoit]

    Func _BigInt_Mul($sTerm1, $sTerm2)
    Local $aTerm1 = StringRegExp($sTerm1, '\A\d{' & Mod(StringLen($sTerm1), 9) & '}|\d{9}+', 3), $iCountTerm1 = UBound($aTerm1) - 1
    Local $aTerm2 = StringRegExp($sTerm2, '\A\d{' & Mod(StringLen($sTerm2), 9) & '}|\d{9}+', 3), $iCountTerm2 = UBound($aTerm2) - 1
    Local $sOut, $sTemp, $iCarry = 0, $sRow, $sPad
    For $j = $iCountTerm2 To 0 Step -1
    For $k = $iCountTerm1 To 0 Step -1
    $sTemp = Int($aTerm1[$k]) * Int($aTerm2[$j]) + $iCarry
    $iCarry = Int(0 + StringTrimRight($sTemp, 9))
    If $k > 0 Then $sTemp = StringRight('000000000' & $sTemp, 9)
    $sRow = $sTemp & $sRow
    Next
    $sOut = _BigInt_Add($sOut, $sRow & $sPad)
    $sPad &= '000000000'
    $sRow = ''
    $iCarry = 0
    Next
    Return $sOut
    EndFunc

    [/autoit] [autoit][/autoit] [autoit]

    Func _BigInt_Load($a)
    Return $a
    EndFunc

    [/autoit] [autoit][/autoit] [autoit]

    Func _BigInt_Print($a)
    Return $a
    EndFunc

    [/autoit]
    • Offizieller Beitrag

    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:

    [autoit]

    $BigInt_1 = _StringRepeat('9', 180)
    $BigInt_2 = _StringRepeat('9', 90)

    [/autoit][autoit][/autoit][autoit]

    ConsoleWrite(_BigInt_Add($BigInt_1, $BigInt_2) & @CRLF)

    [/autoit]

    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.

    Spoiler anzeigen
    [autoit]

    #include-once

    [/autoit] [autoit][/autoit] [autoit]

    Global $L, $R, $E, $T, $i, $j, $C

    [/autoit] [autoit][/autoit] [autoit]

    Func _BigInt_Add($a, $b)
    $L = StringLen($a)
    $T = StringLen($b)
    $R=0
    $E=""
    If $L < $T Then $L=$T
    For $i = $L To 1 Step -14
    $T = StringRight($a, 14) + StringRight($b, 14) + $R
    $a = StringTrimRight($a, 14)
    $b = StringTrimRight($b, 14)
    $R = Floor($T / 100000000000000)
    $T = Mod($T, 100000000000000)
    If $i > 14 And $T <= 10000000000000 Then $T = StringRight("00000000000000" & $T, 14)
    $E = $T & $E
    Next
    Return $E
    EndFunc ;==>_BigInt_Add

    [/autoit] [autoit][/autoit] [autoit]

    Func _BigInt_Mul($a, $b)
    $a = _Split7($a)
    $b = _Split7($b)
    Local $E[$a[0] + $b[0]] = [$a[0] + $b[0] - 1]
    For $i = 1 To $b[0]
    For $j = 1 To $a[0]
    $E[$j + $i - 1] += $a[$j] * $b[$i]
    Next
    Next
    Return _Merge7($E)
    EndFunc ;==>_BigInt_Mul

    [/autoit] [autoit][/autoit] [autoit]

    Func _Merge7($a)
    $E=""
    $R=0
    For $i = $a[0] To 1 Step -1
    $a[$i] += $R
    $R = Floor($a[$i] / 10000000)
    $T = Mod($a[$i], 10000000)
    If $i > 1 And $T <= 10000000 Then $T = StringRight("00000000000000" & $T, 7)
    $E = $T & $E
    Next
    If $R > 0 Then $E = $R & $E
    If $E = 0 Then $E = "0"
    Return $E
    EndFunc ;==>_Merge7

    [/autoit] [autoit][/autoit] [autoit]

    Func _Split7($a)
    $L = StringLen($a)
    $C = Ceiling($L / 7)
    Local $E[$C + 1]
    For $i = $L To 1 Step -7
    $E[$C] = StringRight($a, 7)
    $a = StringTrimRight($a, 7)
    $C -= 1
    Next
    $E[0] = Ceiling($L / 7)
    Return $E
    EndFunc ;==>_Split7

    [/autoit] [autoit][/autoit] [autoit]

    Func _BigInt_Load($a)
    Return $a
    EndFunc ;==>_BigInt_Load

    [/autoit] [autoit][/autoit] [autoit]

    Func _BigInt_Print($a)
    While StringLeft($a, 1) = "0" And StringLen($a) > 1
    $a = StringTrimLeft($a, 1)
    WEnd
    Return $a
    EndFunc ;==>_BigInt_Print

    [/autoit]

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

    Spoiler anzeigen


    Schulmethode:
    456*123
    ---------
    45600
    .9120
    ..1368
    -------
    56088

    hier werden alle einzelnen Ziffern miteinander multipliziert, der Übertrag an die nächste weitergegeben und die Teilergebnisse addiert.
    Wenn man sich die Teilergebnisse nun anschaut, stellt man fest, daß die Stelle von 6*1 in einem anderen Teilergebnis 5*2 und im nächsten 4*3 ist.
    So komm ich auf meine Methode. Ich spare mir den Übertrag vorerst und addiere die einzelnen Multiplikationen gleich

    Meine Methode: (Bei meinem Script verwende ich 7-stellige Array´s; zum Veranschaulichen hier nur 1-stellige)
    jede Ziffer kommt in ein eigenes Array: [4] [5] [6] * [1] [2] [3]
    Das Ergebnis ist auch ein Array:
    [1] = 4*1 = 4
    [2] = 5*1 + 4*2 = 13
    [3] = 6*1 + 5*2 + 4*3 = 28
    [4] = 6*2 + 5*3 = 27
    [5] = 6*3 = 18

    nun hab ich: [4] [13] [28] [27] [18]
    dieses Array füge ich nun zum Ergebnis, indem ich hier nun von rechts nach links den Übertrag weitergebe:
    Einserstelle [18] des Ergebnis ist 8, Übertrag zu Zehnerstelle [27] ist 1...usw.
    [4] [13] [28] [27] [18]=
    56088

    Die Geschwindigkeit erreiche ich dadurch, daß ich NICHT für jedes Teilergebnis den Übertrag berechne, sondern erst am Schluß und das nur 1Mal!
    Außerdem sind die einzelnen Additionen so klein, daß ich die Autoit-Addition verwenden kann.

    an dieser Stelle möchte ich auch gleich ein Problem darstellen:
    betrachten wir eine Zeile von oben: [3] = 6*1 + 5*2 + 4*3 = 28
    Je länger die zu berechnenden Zahlen sind, desto länger wird auch diese Zeile!
    theoretisch wird irgendwann die berechenbare Grenze erreicht, also wenn das Ergebnis dieser Zeile für Autoit zu groß wird.
    Für diesen Fall benötigt man dann eine andere Lösung (Zwischendurch Übertrag berechnen und diese Teilergebnisse mit _BigIn_Add zusammenzählen...?!)

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

    lgE

    • Offizieller Beitrag

    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!?!

    [autoit]

    $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

    [/autoit]


    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.

    • Offizieller Beitrag

    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