Die Mathematik hinter dem Konvertieren von einer Basis zu einer Basis, ohne die Basis 10 zu durchlaufen?

Dies scheint mir eine sehr grundlegende Frage zu sein. Entschuldigen Sie mich, wenn ich Ihnen etwas vorlese. Der wichtigste Punkt, den Sie hier lernen müssen, ist, dass eine Zahl nicht ihre Ziffernrepräsentation ist . Eine Zahl ist ein abstraktes mathematisches Objekt, während ihre Zifferndarstellung eine konkrete Sache ist, nämlich eine Folge von Symbolen auf einem Papier (oder eine Folge von Bits im Computerspeicher oder eine Folge von Tönen, die Sie machen, wenn Sie eine Zahl kommunizieren). Was Sie verwirrt, ist die Tatsache, dass Sie niemals eine Zahl sehen , sondern immer deren Ziffernrepräsentation. Am Ende denken Sie also, dass die Zahl die Darstellung ist.

Daher lautet die richtige Frage nicht “ wie konvertiere ich von einer Basis zu einer anderen „, sondern “ Wie finde ich heraus, welche Zahl durch eine bestimmte Ziffernfolge dargestellt wird? “ und “ Wie finde ich die Zifferndarstellung einer bestimmten Zahl? „.

Lassen Sie uns also zwei Funktionen in Python erstellen, eine zum Konvertieren einer Zifferndarstellung in eine Zahl und eine andere, um das Gegenteil zu tun. Hinweis: Wenn wir die Funktion ausführen, druckt Python natürlich die Zahl, die es in Basis 10 erhalten hat, auf dem Bildschirm . Dies bedeutet jedoch nicht, dass der Computer die Zahlen in Basis 10 hält 10 (es ist nicht „t“. Es ist irrelevant , wie der Computer die Zahlen darstellt.

def toDigits(n, b): """Convert a positive number n to its digit representation in base b.""" digits = [] while n > 0: digits.insert(0, n % b) n = n // b return digits def fromDigits(digits, b): """Compute the number given by digits in base b.""" n = 0 for d in digits: n = b * n + d return n 

Lassen Sie uns diese testen:

>>> toDigits(42, 2) [1, 0, 1, 0, 1, 0] >>> toDigits(42, 3) [1, 1, 2, 0] >>> fromDigits([1,1,2,0],3) 42 

Mit Konvertierungsfunktionen ausgestattet, lässt sich Ihr Problem leicht lösen:

def convertBase(digits, b, c): """Convert the digits representation of a number from base b to base c.""" return toDigits(fromDigits(digits, b), c) 

Ein Test :

>>> convertBase([1,1,2,0], 3, 2) [1, 0, 1, 0, 1, 0] 

Hinweis: wir haben nicht durch Basis 10-Darstellung gehen! Wir haben die Basis $ b $ -Darstellung in die Zahl und dann die Zahl in die Basis $ c $ . Die Nummer war in keiner Darstellung . (Eigentlich musste der Computer sie irgendwie darstellen, und er stellte sie mit elektrischen Signalen und Funky dar Sachen, die in Chips passieren, aber sicherlich die w bevor nicht 0 „s und 1“ s.)

Kommentare

• Dies

Ich denke, der beste Weg, dies zu verstehen, ist die Diskussion mit einem Außerirdischen (zumindest als eine Analogie).

Definition $ x $ ist eine Zahl in der Basis $ b $ bedeutet, dass $ x $ eine Ziffernfolge ist. $ < b $.

Beispiele Die Ziffernfolge 10010011011 ist eine Zahl in Basis 2, die Zeichenfolge 68416841531 ist eine Zahl in Basis 10, BADCAFE ist eine Zahl in Basis 16.

Jetzt Angenommen, ich bin auf dem Planeten QUUX aufgewachsen, wo jedem beigebracht wird, sein ganzes Leben lang in $ q $ zu arbeiten, und ich treffe Sie, der es gewohnt ist, $ b $ zu gründen. Also zeigst du mir eine Nummer und was mache ich? Ich brauche eine Möglichkeit, es zu interpretieren:

Definition Ich kann interpretieren eine Zahl in der Basis $ b $ (Hinweis: $ b $ ist eine Zahl in der Basis $ q $) nach der folgenden Formel

$$ \ begin {array} {rcl} [\! [\ epsilon] \!] & = & 0 \\ [\! [\ bar sd] \!] & = & [\! [\ bar s] \!] \ times b + d \ end {array} $$

wobei $ \ epsilon $ bezeichnet die leere Zeichenfolge und $ \ bar sd $ bezeichnet eine Zeichenfolge, die mit der Ziffer $ d $ endet. Eine Einführung in diese Notation finden Sie unter , mein Beweis, dass durch Hinzufügen hinzugefügt wird.

Also, was ist hier passiert? Sie haben mir eine Nummer gegeben in base $ b $ und ich habe es in base $ q $ interpretiert, ohne irgendeine seltsame Philosophie darüber, was Zahlen wirklich sind.

Schlüssel Der Schlüssel dazu ist, dass die $ \ times $ und $ + $, die ich habe, Funktionen sind, die auf Basis $ q $ -Nummern arbeiten. Dies sind einfache Algorithmen, die rekursiv auf Basis $ q $ -Nummern (Zeichenfolgen) definiert werden von Ziffern).

Dies mag etwas abstrakt erscheinen, da ich durchweg Variablen anstelle von tatsächlichen Zahlen verwendet habe. Nehmen wir also an, Sie sind eine Basis-13-Kreatur (mit Symbolen $ 0123456789XYZ $) und ich bin es verwendet, um 7 (was viel sinnvoller ist) mit den Symbolen $ \ alpha \ beta \ gamma \ delta \ rho \ zeta \ xi $ zu stützen.

Also habe ich Ihr Alphabet gesehen und es so tabelliert:

$$ \ begin {array} {| c | c || c | c || c | c |} \ hline 0 & \ alpha & 1 & \ beta & 2 & \ gamma \\ 3 & \ delta & 4 & \ rho & 5 & \ zeta \\ 6 & \ xi & 7 & \ beta \ alpha & 8 & \ beta \ beta \\ 9 & \ beta \ gamma & X \ beta \ delta & Y & \ beta \ rho \\ & & Z & \ beta \ zeta & & \\ \ hline \ end {array} $$

Ich weiß also, dass Sie in der Basis $ \ beta \ xi $ arbeiten, und ich weiß, welche Basis 7 eine beliebige Ziffer ist Schreiben entspricht.

Wenn wir nun über Physik diskutierten und Sie mir grundlegende Konstanten erzählten (sagen wir) $ 60Z8 $, muss ich dies interpretieren:

$$ \ begin { Array} {rcl} [\! [60Z8] \!] & = & \ xi (\ beta \ xi) ^ 3 + \ alpha (\ beta \ xi) ^ 2 + \ beta \ zeta (\ beta \ xi) + \ beta \ beta \\ \ end {array} $$

Also multipliziere ich zunächst $ \ beta \ zeta \ times \ beta \ xi $, aber das ist für mich Grundschulmaterial, ich erinnere mich:

Quux-Multiplikationstabelle

$$ \ begin {array} {| c | cccccc |} \ hline \\ \ times & \ beta & \ gamma & \ delta & \ rho & \ zeta & \ xi \\ \ hline \ beta & \ beta & \ gamma & \ delta & \ rho & \ zeta & \ xi \\ \ gamma & \ gamma & \ rho & \ xi & \ beta \ beta & \ beta \ delta & \ beta \ zeta \\ \ delta & \ delta & \ xi & \ beta \ gamma & \ beta \ zeta & \ gamma \ beta & \ gamma \ rho \\ \ rho & \ rho & \ beta \ beta & \ beta \ zeta & \ gamma \ gamma & \ gamma \ xi & \ delta \ delta \\ \ zeta & \ zeta & \ beta \ delta & \ gamma \ beta & \ gamma \ xi & \ delta \ rho & \ rho \ gamma \\ \ xi & \ xi & \ beta \ zeta & \ gamma \ rho & \ delta \ delta & \ rho \ gamma & \ zeta \ beta \\ \ beta \ alpha & \ beta \ alpha & \ gamma \ alpha & \ delta \ alpha & \ rho \ alpha & \ zeta \ alpha & \ xi \ alpha \\ \ hline \ end {array} $$

Um $ \ beta \ zeta \ times \ beta \ xi $ zu finden, gehe ich wie folgt vor:

$$ \ begin {array} {ccc} & \ beta & \ ze ta \\ \ times & \ beta & \ xi \\ \ hline & \ xi & \ gamma \\ & \ rho & \\ \ beta & \ zeta & \\ \ hline \ delta & \ beta & \ gamma \\ \ gamma & & \\ \ end {array} $$

also bin ich so weit gekommen

$$ \ begin {array} {rcl} [\! [60Z8] \!] & = & \ xi (\ beta \ xi) ^ 3 + \ alpha (\ beta \ xi) ^ 2 + \ beta \ zeta (\ beta \ xi) + \ beta \ beta \\ & = & \ xi (\ beta \ xi) ^ 3 + \ alpha (\ beta \ xi) ^ 2 + \ delta \ beta \ gamma + \ beta \ beta \\ \ end {array} $$

Jetzt muss ich die Addition mit dem Algorithmus durchführen, der wurde bereits erwähnt:

$$ \ begin {array} {ccc} \ delta & \ beta & \ gamma \\ & \ beta & \ beta \\ \ hline \ delta & \ gamma & \ delta \\ \ end {array} $$

also

$$ \ begin {array} {rcl} [ \! [60Z8] \!] & = & \ xi (\ beta \ xi) ^ 3 + \ alpha (\ beta \ xi) ^ 2 + \ beta \ zeta (\ beta \ xi) + \ beta \ beta \\ & = & \ xi ( \ beta \ xi) ^ 3 + \ alpha (\ beta \ xi) ^ 2 + \ delta \ beta \ gamma + \ beta \ beta \\ & = & \ xi (\ beta \ xi) ^ 3 + \ alpha (\ beta \ xi) ^ 2 + \ delta \ gamma \ delta \\ \ end {array} $ $

und wenn ich so weitermache, erhalte ich $$ [\! [60Z8] \!] = \ zeta \ delta \ xi \ gamma \ rho. $$

In Zusammenfassung: Wenn ich meine eigene Vorstellung von Zahlen in Form von Ziffernfolgen der Basis $ q $ habe, kann ich Ihre Zahlen von der Basis $ b $ in mein eigenes System interpretieren, basierend auf den grundlegenden arithmetischen Operationen, die nativ in funktionieren base $ q $.

Kommentare

• Nun, das waren viele schnörkellose Linien. Wie würde ich den Computer dazu bringen, das zu tun?
• @Griffin, ich denke, Sie stellen diese (seltsame) Frage vorzeitig. Sie wählen eine Programmiersprache aus und geben den Algorithmus für die Addition und Multiplikation auf Basis-Q-Zahlen (dargestellt als Ziffernlisten) ein. Dann definieren Sie eine Funktion, um Basis-B-Ziffern in Basis-Q-Zahlen und Basis-B-Zahlen in Basis-Q-Zahlen zu interpretieren. Ich ‚ habe das alles erklärt.
• Ich kenne das Konzept, das Sie darstellen möchten. Mein Problem ist, dass mein Computer ‚ Ihre schnörkellosen Linien nicht verwenden kann.
• Ich weiß, was Sie erklärt haben, aber es ist weitaus schwieriger, es in die Praxis umzusetzen. Sie sehen, dass das Definieren dieser Ziffern nicht ‚ so einfach ist.
• Auch warum haben Sie die Alpha-Ziffer an der höchstwertigen Position abgelegt? Da 6 = & xi;, würde ‚ t 7 = & alpha; & alpha;?

Dies ist ein Refactoring (Python) 3) von Andrejs Code. Während in Andrejs Codenummern durch eine Liste von Ziffern (Skalaren) dargestellt werden, werden in den folgenden Codenummern durch dargestellt Eine Liste von beliebigen Symbolen aus einer benutzerdefinierten Zeichenfolge:

def v2r(n, base): # value to representation """Convert a positive number to its digit representation in a custom base.""" b = len(base) digits = "" while n > 0: digits = base[n % b] + digits n = n // b return digits def r2v(digits, base): # representation to value """Compute the number represented by string "digits" in a custom base.""" b = len(base) n = 0 for d in digits: n = b * n + base[:b].index(d) return n def b2b(digits, base1, base2): """Convert the digits representation of a number from base1 to base2.""" return v2r(r2v(digits, base1), base2) 

So führen Sie eine Konvertierung von Wert zu Darstellung in einer benutzerdefinierten Basis durch:

>>> v2r(64,"01") "1000000" >>> v2r(64,"XY") "YXXXXXX" >>> v2r(12340,"ZABCDEFGHI") # decimal base with custom symbols "ABCDZ" 

So führen Sie eine Konvertierung von Darstellung (in einer benutzerdefinierten Basis) zu Wert durch :

>>> r2v("100","01") 4 >>> r2v("100","0123456789") # standard decimal base 100 >>> r2v("100","01_whatevr") # decimal base with custom symbols 100 >>> r2v("100","0123456789ABCDEF") # standard hexadecimal base 256 >>> r2v("100","01_whatevr-jklmn") # hexadecimal base with custom symbols 256 

So führen Sie eine Basiskonvertierung von einer Kundenbasis in eine andere durch:

>>> b2b("1120","012","01") "101010" >>> b2b("100","01","0123456789") "4" >>> b2b("100","0123456789ABCDEF","01") "100000000" 

Kommentare

• Willkommen auf der Website und vielen Dank für Ihren Beitrag. Das Erstellen eines gut optimierten Quellcodes ist jedoch nicht ‚ das, worum es auf dieser Site wirklich geht. Der Code von Andrej ‚ macht die Konzepte klar, was für seine Antwort erforderlich ist, aber die Verbesserung des Codes darüber hinaus ist eher eine Frage der Programmierung als der Informatik .
• @DavidRicherby Ich stimme teilweise zu, aber dieser Beitrag war zu lang für einen Kommentar und sein bester Ort ist irgendwo in der Nähe der Antwort von Andrej ‚. ‚ Deshalb habe ich es hier gepostet. Wenn Sie der Meinung sind, dass ‚ besser ist, könnte ich es in einen Kommentar mit einem Link zum Code konvertieren, aber ‚ wäre es nicht ein Übermaß an Purismus?
• Trotz @David ‚ s “ Site-Purist “ Einwände, ich fand Ihre Antwort nützlich, weil sie die Tatsache betont, dass die beteiligten Grundlagen abstrakter als “ Alphabete beliebiger Symbole unterschiedlicher Länge – und nicht auf den üblichen Bereich von 2-36 Zeichen beschränkt. Sie können tatsächlich Byteströme als “ -Ziffern “ der Basis-256-Ganzzahlwerte betrachten.

Grundlegende Operation der Basiskonvertierung ist die toDigits() Operation der Antwort von @AndrejBauer. Um dies zu erreichen, muss jedoch keine Zahl in der internen Darstellung der Zahlen erstellt werden. Dies ist im Grunde eine Konvertierung von und zur Basis-2-Darstellung.Sie können die erforderlichen Operationen in der ursprünglichen Basisdarstellung ausführen.

Der erste Schritt besteht also darin, eine sich wiederholende Modulo-Divisionsoperation durchzuführen.

def convertBase(n,original_base,destination_base): digits = [] while not is_zero(n): digits.insert(0,modulo_div(n,original_base,destination_base)) return digits 

Da es sich bei der internen Darstellung um Ziffern handelt, muss eine Spezilisierung vorgenommen werden Funktion zum Testen von Null

def is_zero(n): for d in n: if d != 0: return False return True 

Schließlich muss man die modulo_div-Operation ausführen, die tatsächlich die Standarddivision nach Zielbasis ist, wie wir in der Schule gelernt haben.

def modulo_div(n,original_base,destination_base): carry = 0 for i in range(len(n)): d = n[i] d+=original_base*carry carry = d%destination_base d=(d//destination_base) n[i] = d #print(i,d,carry) return carry 

Nur eine Testprüfung, um sicherzustellen, dass der Code korrekt ist:

print(convertBase([1,1,2,0], 3, 2)) #[1, 0, 1, 0, 1, 0] print(convertBase([1, 0, 1, 0, 1, 0], 2, 3)) #[1, 1, 2, 0] 

Kommentare

• Vielen Dank für die Veröffentlichung, aber bitte beachten Sie, dass wir ‚ keine Codierungssite sind, daher ist ein großer Codeblock nicht ‚ hier nicht als Antwort geeignet. Insbesondere wenn die Frage explizit lautet: “ Ich ‚ benötige keinen Code, sondern nur die grundlegende Mathematik dahinter. “
• @DavidRicherby Ich habe versucht, Text hinzuzufügen.
• Danke. Und ich sehe dort ‚ eine Menge Code auf dieser Seite, trotz allem, was ich gesagt habe!
• @David: FWIW, ich denke, dies beantwortet das OP Die Frage von ‚ zeigt am besten, wie zwischen den beiden Basen konvertiert wird, ohne zuerst die Darstellung des Originals in eine Zwischenform und dann in die Zielbasis zu konvertieren.
• Netter Versuch, aber d befindet sich immer noch in Basis 10, also extrahieren Sie tatsächlich einen kleineren Teil von n, konvertieren ihn in Basis 10, konvertieren ihn dann in die gewünschte Basis und sammeln diese im Endergebnis.

Ich kenne eine einfache Möglichkeit, eine Basiskonvertierung durchzuführen, für die kein Computerprogramm erforderlich ist eine Möglichkeit, von einer Basis zu Basis 2 und umgekehrt zu konvertieren und dann von einer Basis zu einer anderen Basis zu konvertieren, indem zuerst von der ersten Basis zu Basis 2 konvertiert wird und dann von Basis 2 zu der anderen Basis konvertiert wird. 2 ist so einfach zu multiplizieren oder durch eine beliebige Basis zu dividieren.

Um von einer beliebigen Basis zu einer Basis 2 zu konvertieren, müssen Sie dies nur für eine beliebige Zahl erkennen, wenn Sie die Basis 2-Notation verwenden und beginnen von 0 und dann für jede Ziffer in der Reihenfolge von links nach rechts doppelt, wenn diese Ziffer Null ist und doppelt als 1 addieren, wenn diese Ziffer 1 ist, erhalten Sie diese Zahl selbst. Wenn Sie diese Zahl nun in einer beliebigen Basis angeben, können Sie in dieser Basis durch 2 teilen, um einen Quotienten und einen Rest zu erhalten. Wenn der Rest 1 ist, ist die letzte Binärziffer 1 und wenn der Rest 0 ist, ist die letzte Binärziffer 0. Teilen Sie erneut durch 2. Wenn der Rest 1 ist, ist die vorletzte Ziffer 1 und wenn der Rest 0 ist, ist die vorletzte Ziffer 0 usw., bis Sie einen Quotienten von 0 erhalten.

Um von Basis 2 zu einer beliebigen zu konvertieren Basis, alles, was Sie tun müssen, ist in dieser Basis, beginnen Sie bei 0, dann verdoppeln Sie für jede Binärziffer von links nach rechts in dieser Basis, wenn diese Ziffer 0 ist, und verdoppeln Sie dann 1 in dieser Basis, wenn diese Ziffer 1 ist.

Kommentare

• 2 is so easy to multiply or divide by in any base. Ich habe ‚ t nicht siehe das für ungerade Basen, die mehr als eins aus einer Zweierpotenz sind (zunächst 11 und 13).