Make-Grafik
Anmeldungsdatum: 08.10.2012 Beiträge: 29
|
Verfasst am: 22.01.2014, 00:03 Titel: Dezimalzahl in String zu Dualzahl (Algo Verständnisproblem) |
|
|
Schönen guten Abend
Ich habe hier eine etwas speziellere Frage zu einem bereits geschriebenen Algorithmus. Falls es nicht ins Unterforum passt bitte ich einen Administrator oder Moderator (je nachdem wer dafür zuständig ist) den Thread zu verschieben. Erst einmal der Code dazu: http://www.freebasic-portal.de/code-beispiele/mathematik/einfache-schnelle-bigint-erweiterung-284.html
Es geht mir dabei einzig und alleine um den Constructor welcher einen String beim initialisieren entgegen nimmt. Diesen findet ihr in Zeile 341. Hier ist aber noch einmal der Code dazu: Code: | Constructor bigint (ByRef a As String)
Dim As Integer p, i, j, ch, blocks, sign
If InStr(a, "-") <> 0 Then sign = -1
'------------------------------------------------------------
' extract numerics from input string
j = 0 ' in-place write pointer
For i = 0 To Len(a) - 1
ch = a[i]
If (ch >= Asc("0")) And (ch <= Asc("9")) Then
a[j] = ch
j += 1
End If
Next i
a = Left(a, j) ' j is one ahead from string index = length of a
'------------------------------------------------------------
' extend to next multiple of 9 digits
i = Len(a)
blocks = Int(0.99 + i / 9) ' number of 9 digit blocks needed
p = 9 * blocks
a = String(p - i, "0") + a ' pad to next multiple of 9 digits
'------------------------------------------------------------
' decimal to binary conversion
i = ( 8 + Len(a) * 3.32192809488) \ 8 ' bytes needed for binary
blocks = 1 + (i \ 4) ' adjust to multiple of 4
this.s = String(blocks * 4, Chr(0) ) ' binary destination string
'------------------------------------------------------------
Dim As UInteger<32> Ptr bp, bpz, bpcarry, bpdata
bpz = Cast(UInteger<32> Ptr, StrPtr(this.s)) ' binary output string[0]
Dim As ULongInt product, carry, multiplier = 1e9
bpdata = Cast(UInteger<32> Ptr, @product) ' bottom half of product
bpcarry = bpdata + 1 ' top half of product
'------------------------------------------------------------
blocks = 1 ' blocks will be advanced as required by carry
For i = 1 To Len(a)-8 Step 9 ' msd to lsd in blocks of 9
bp = bpz ' point back to the start
carry = ValULng(Mid(a, i, 9)) ' take the next 9 digit block
For j = 1 To blocks
product = CLngInt(*bp) * multiplier + carry
*bp = CUInt<32>(*bpdata)
carry = CULngInt(*bpcarry)
bp += 1
Next j
' advancing blocks only as needed doubles the speed of conversion
If Carry Then
*bp = carry
blocks += 1 ' an exact count of the blocks used
End If
Next i
this.s = Left(this.s, blocks * 4) ' keep only used blocks
'-------------------------------------------------------------
If this.s[Len(this.s)-1] And 128 Then this.s = this.s + bigint_0.s ' MSB must be 0
If sign Then This = bigint_negate(This)
End Constructor |
Mein Problem ist, dass ich die Mathematik dahinter nicht verstehe. Ich hab das Codetechnisch schon bereits alles durchschaut und weiß auch was dieser Constructor macht.
Im ersten Abschnitt wird geprüft ob ein Minuszeichen im String vorhanden ist. Aber das ist denke ich noch sehr deutlich erkennbar.
Im zweiten Abschnitt werden alle Zeichen aussortiert, die keine Zeichen von „0“ bis „9“ sind.
Im dritten Abschnitt wird der Dezimalzahl noch einige führende Nullen hinzugefügt. Die Länge des Strings muss eine Vielfache von 9 entsprechen. (Falls ich mich da nicht verguckt habe )
Der vierte und fünfte Abschnitt ist noch ein wenig Vorbereitung für den sechsten Abschnitt.
Der sechste Abschnitt ist der für mich interessanteste Teil. Hier wird der String in 9er Blöcken zerlegt und einzeln bearbeitet. Ganz zum Schluss liegt dann der eingegebene String bei der Initialisierung als eine Duale Zahl vor. Die Bits sind intern zu jeweils einen Byte zusammengefasst und werden als einzelnes Zeichen in der Membervariable s des Betroffenen Objektes gespeichert. Die einzelnen Bits lassen sich dann später mit der Funktion bigint_binary so auslesen, dass die Bits dann hintereinander als String vorliegen. Beispielsweise so: „01000001“. Wenn man stattdessen die Membervariable s aufruft erhält man das Zeichen „A“.
Der Algorithmus wurde speziell für große Zahlen entwickelt und läuft sehr schnell weshalb ich auch die Mathematik dahinter verstehen möchte, damit ich dies in andere Sprachen umschreiben kann. Ich habe derzeitig leider keine Verwendung dafür in FreeBASIC. Ich brauche diesen Algorithmus in einer Skriptsprache welche keine Pointer unterstützt. Deswegen ist dies auch nicht so einfach umzuschreiben.
Jedenfalls wollte ich nun wissen wie das mathematisch dort bewerkstelligt wurde. Ich sehe da keinen Zusammenhang, kann die einzelnen Schritte aber sehr gut verfolgen. Wenn mir das jemand erklären könnte, wäre ich mehr als dankbar dafür. LG Make _________________ Hmn :/ Mal schaun was es bringt... |
|