Das deutsche QBasic- und FreeBASIC-Forum Foren-Übersicht Das deutsche QBasic- und FreeBASIC-Forum
Für euch erreichbar unter qb-forum.de, fb-forum.de und freebasic-forum.de!
 
FAQFAQ   SuchenSuchen   MitgliederlisteMitgliederliste   BenutzergruppenBenutzergruppen  RegistrierenRegistrieren
ProfilProfil   Einloggen, um private Nachrichten zu lesenEinloggen, um private Nachrichten zu lesen   LoginLogin
Zur Begleitseite des Forums / Chat / Impressum
Aktueller Forenpartner:

Dezimalzahl in String zu Dualzahl (Algo Verständnisproblem)

 
Neues Thema eröffnen   Neue Antwort erstellen    Das deutsche QBasic- und FreeBASIC-Forum Foren-Übersicht -> Allgemeine Fragen zu FreeBASIC.
Vorheriges Thema anzeigen :: Nächstes Thema anzeigen  
Autor Nachricht
Make-Grafik



Anmeldungsdatum: 08.10.2012
Beiträge: 29

BeitragVerfasst am: 21.01.2014, 23:03    Titel: Dezimalzahl in String zu Dualzahl (Algo Verständnisproblem) Antworten mit Zitat

Schönen guten Abend lächeln
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 happy)

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

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 lächeln
_________________
Hmn :/ Mal schaun was es bringt...
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
Beiträge der letzten Zeit anzeigen:   
Neues Thema eröffnen   Neue Antwort erstellen    Das deutsche QBasic- und FreeBASIC-Forum Foren-Übersicht -> Allgemeine Fragen zu FreeBASIC. Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

 Impressum :: Datenschutz