Die Mathematik, die dahinter steht, von einer Basis zu einer anderen Basis zu konvertieren, ohne die Basis 10 zu durchlaufen?

35

Ich habe mich mit der Mathematik beschäftigt, die dahinter steckt, von einer Basis zu einer anderen Basis zu konvertieren. Hier geht es vor allem darum, meine Ergebnisse zu bestätigen. Ich habe meine Antwort auf mathforum.org gefunden, bin mir aber immer noch nicht sicher, ob ich die richtige Antwort habe. Ich habe das Konvertieren von einer größeren Basis zu einer kleineren Basis in Ordnung, da es einfach ist, die erste Ziffer mit der Basis zu multiplizieren, die Sie als nächste Ziffernwiederholung hinzufügen möchten. Mein Problem tritt auf, wenn ich von einer kleineren Basis zu einer größeren Basis konvertiere. Dabei wird erläutert, wie Sie die gewünschte größere Basis in die kleinere Basis umwandeln müssen. Ein Beispiel wäre, von der Basis 4 zur Basis 6 zu wechseln. Sie müssen die Zahl 6 in die Basis 4 umwandeln, um die Zahl 12 zu erhalten. Sie tun dann genau das Gleiche wie beim Umwandeln von groß zu klein. Die Schwierigkeit, die ich dabei habe, scheint zu sein, dass Sie wissen müssen, welche Zahl sich in der anderen Basis befindet. Ich müsste also wissen, was 6 in Basis 4 ist. Dies ist ein großes Problem in meinem Kopf, da ich dann einen Tisch bräuchte. Kennt jemand einen Weg, dies auf eine bessere Art und Weise zu tun.

Ich dachte, eine Basiskonvertierung würde helfen, aber ich kann diese Arbeit nicht finden. Und von der Site aus, die ich gefunden habe, scheint es Ihnen zu ermöglichen, von Basis zu Basis zu konvertieren, ohne die Basis 10 zu durchlaufen, aber Sie müssen zuerst wissen, wie Sie die erste Zahl von Basis zu Basis konvertieren. Das macht es irgendwie sinnlos.

Kommentatoren sagen, ich muss in der Lage sein, einen Buchstaben in eine Zahl umzuwandeln. Wenn ja, weiß ich das schon. Das ist jedoch nicht mein Problem. Mein Problem ist, um eine große Basis in eine kleine Basis umzuwandeln, muss ich zuerst die Basisnummer, die ich habe, in die gewünschte Basisnummer umwandeln. Auf diese Weise kann ich den Zweck nicht erfüllen, da ich mein Problem bereits gelöst habe, wenn ich in der Lage bin, diese Basen in andere Basen umzuwandeln.

Bearbeiten: Ich habe herausgefunden, wie man von Basen kleiner oder gleich 10 in andere Basen kleiner oder gleich 10 konvertiert. Ich kann auch von einer Basis größer als 10 zu jeder Basis gehen, die 10 oder weniger ist. Das Problem tritt auf, wenn Sie von einer Basis größer als 10 zu einer anderen Basis größer als 10 konvertieren. Oder wenn Sie von einer Basis kleiner als 10 zu einer Basis größer als 10 wechseln auf Code angewendet.

Greif
quelle
1
Ist diese Frage zum Thema für dieses Forum?
Andrej Bauer
2
Das Verfahren ist trivial, solange Sie in der Zielbasis addieren und multiplizieren können. Wenn Sie nicht können, denke ich nicht, dass es möglich ist.
Karolis Juodelė
9
Zunächst sollte Griffin gesagt werden, was viele Schüler hören müssen: Zahlen existieren, ohne in einer Basis vertreten zu sein . Dann ist die Antwort klar: Wir brauchen Algorithmen, einen zum Konvergieren einer Darstellung einer Zahl in einer gegebenen Basis mit der Zahl (das heißt, etwas, das ein stringund ein zurückgibt int), und einen Algorithmus, der eine Zahl nimmt und ihre Darstellung zurückgibt in einer bestimmten Basis.
Andrej Bauer
1
@AndrejBauer Die Frage bezieht sich auf CS: Auch wenn es nicht so formuliert ist, handelt es sich um einen Algorithmus zur Konvertierung zwischen Zahlendarstellungen. [Anmerkung: Ich habe einige verwirrende Kommentare gelöscht. Griffin: Bitte bearbeiten Sie Ihre Frage, um sie zu aktualisieren. Andere: Bitte nehmen Sie es zum Plaudern mit .]
Gilles 'SO - hören Sie auf, böse zu sein'
1
@Griffin es ist lange her seit deiner ursprünglichen Frage. Ich hoffe du hast deine Antwort gefunden. Wenn ja, könnte es eine großartige Idee sein, eine Antwort zu aktualisieren und zu akzeptieren oder Ihre zu posten. In der Zwischenzeit habe ich in den Code Jam-Archiven von Google ein paar sehr nette Ideen gefunden (die sich mit der Implementierung in C ++ befassen). Einige Lösungen für dieses Problem sind sehr kreativ code.google.com/codejam/contest/32003/dashboard
IsaacCisneros

Antworten:

45

Dies scheint mir eine sehr grundlegende Frage zu sein, entschuldigen Sie mich, wenn ich Sie ein wenig belehre. Der wichtigste Punkt, den Sie hier lernen müssen, ist, dass eine Zahl nicht ihre Stellendarstellung ist . Eine Zahl ist ein abstraktes mathematisches Objekt, während ihre Stellendarstellung 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 bei der Übermittlung einer Zahl erzeugen). Was Sie ist verwirrt , ist die Tatsache , dass Sie nie sehen eine Zahl , sondern immer Ziffernfolge abweichen. So Sie am Ende denken , dass die Zahl ist die Darstellung.

Daher lautet die richtige Frage nicht "Wie konvertiere ich von einer Basis in eine andere", sondern "Wie finde ich heraus, welche Zahl durch eine bestimmte Ziffernfolge dargestellt wird" und "Wie finde ich die Ziffernrepräsentation von a gegebene Nummer ".

Lassen Sie uns also zwei Funktionen in Python erzeugen, eine zum Umwandeln einer Ziffernrepräsentation in eine Zahl und eine andere zum Umkehren. Hinweis: Wenn wir die Funktion Python ausführen, wird auf dem Bildschirm natürlich die Nummer ausgegeben, die in Basis 10 gespeichert wurde. Dies bedeutet jedoch nicht , dass der Computer die Nummern in Basis 10 beibehält (dies ist nicht der Fall ). Es ist unerheblich, 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, ist Ihr Problem leicht zu 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 die Darstellung der Basis 10 nicht durchlaufen! Wir haben die Darstellung der Basis in die Zahl und dann die Zahl in die Basis c konvertiert . Die Zahl war nicht in jeder Darstellung. (Eigentlich war es so, der Computer musste es irgendwie darstellen, und es stellte es mit elektrischen Signalen und funky Sachen dar, die in Chips vorkommen, aber sicher waren das keine Nullen und Einsen.)bc

Andrej Bauer
quelle
4
Das überzeugt mich nicht zu 100%. Tatsächlich haben Sie die Zahl in eine Darstellung konvertiert (obwohl Sie behaupten können, nicht zu wissen, was es ist), weil Computer keine platonischen Mathematiker sind und Ihr Algorithmus keine willkürliche Folge von Ziffern in der Basis in die Basis b 2 konvertieren kann ; Es kann nur Sequenzen konvertieren, die von der konkreten Maschine dargestellt werden können. Python ist bezaubernd flexibel; C wäre nicht so nachsichtig gewesen. Es ist durchaus zulässig zu fragen, wie beliebige Zeichenfolgen von b 1 in b 2 konvertiert werden können . Dies ist jedoch nur in linearer Zeit möglich, mit Ausnahme bestimmter Basiskombinationen (z. B. 2 - 16)b1b2b1b2
rici
1
Es ist gültig, die Frage zu stellen, aber um die richtige Antwort zu finden, ist es am besten, sich der Tatsache bewusst zu sein, dass Zahlen abstrakte Einheiten sind.
Andrej Bauer
2
Dabei wird die Zahl durch die Darstellung zur Basis 10 weitergereicht, da fromDigitsdie Zahl zur Basis 10 zurückgegeben wird.
Am
8
@anorton: Nein, definitiv nicht . Python druckt die Nummer auf dem Bildschirm in einer 10-stelligen Basisdarstellung, aber die Nummer selbst wird nicht auf diese Weise gespeichert. Was ich versuche, ist, dass es unerheblich ist , wie die Zahlen in Python implementiert werden. Das ist egal. Wichtig ist nur, dass sie sich wie Zahlen verhalten.
Andrej Bauer
3
Endlich eine allgemeine Lösung für jede Basis und nicht nur für bestimmte Anwendungsfälle, Basen unter 36 oder Fälle, in denen Sie genügend eindeutige Symbole finden können.
J. Money
21

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

Definition ist eine Zahl in der Basis bxb bedeutet, dass eine Ziffernfolge < b ist .x<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.

Angenommen, ich bin auf dem Planeten QUUX aufgewachsen, auf dem jedem beigebracht wird, ein Leben lang in zu arbeiten , und ich treffe dich, der es gewohnt ist, b zu gründen . Also zeigst du mir eine Nummer und was mache ich? Ich brauche einen Weg, um es zu interpretieren:qb

Definition Ich kann eine Zahl in der Basis b (Anmerkung: b ist eine Zahl in der Basis q ) durch die folgende Formel interpretierenbbq

[[ϵ]]=0[[s¯d]]=[[s¯]]×b+d

Dabei bezeichnet die leere Zeichenfolge und ˉ s d eine Zeichenfolge, die mit der Ziffer d endet . Siehe meinen Beweis, dass der Zusatz eine Einführung in diese Notation gibt.ϵs¯dd

Also, was ist hier passiert? Sie haben mir eine Zahl in Basis und ich habe sie in Basis q interpretiert, ohne irgendeine seltsame Philosophie darüber, was Zahlen wirklich sind.bq

Taste Der Schlüssel dazu ist, dass das und das + I Funktionen sind, die auf Basis- q- Zahlen arbeiten. Hierbei handelt es sich um einfache Algorithmen, die rekursiv auf Basis von q- Zahlen (Ziffernfolgen) definiert werden.×+qq


Dies mag etwas abstrakt erscheinen, da ich durchgehend Variablen anstelle von tatsächlichen Zahlen verwendet habe. Nehmen wir also an, Sie sind eine Kreatur der Basis 13 (mit den Symbolen ) und ich bin es gewohnt, mit den Symbolen α β γ δ ρ ζ ξ die Basis 7 zu verwenden (was viel sinnvoller ist) .0123456789XYZαβγδρζξ

Also habe ich dein Alphabet gesehen und es folgendermaßen tabelliert:

0α1β2γ3δ4ρ5ζ6ξ7βα8ββ9βγXβδYβρZβζ

βξ

60Z8

[[60Z8]]=ξ(βξ)3+α(βξ)2+βζ(βξ)+ββ

βζ×βξ

Quux-Multiplikationstabelle

×βγδρζξββγδρζξγγρξβββδβζδδξβγβζγβγρρρβββζγγγξδδζζβδγβγξδρργξξβζγρδδργζββαβαγαδαραζαξα

so to find βζ×βξ I do:

βζ×βξξγρβζδβγγ

so I've got this far

[[60Z8]]=ξ(βξ)3+α(βξ)2+βζ(βξ)+ββ=ξ(βξ)3+α(βξ)2+δβγ+ββ

Now I need to perform the addition using the algorithm which was mentioned before:

δβγββδγδ

so

[[60Z8]]=ξ(βξ)3+α(βξ)2+βζ(βξ)+ββ=ξ(βξ)3+α(βξ)2+δβγ+ββ=ξ(βξ)3+α(βξ)2+δγδ

and continuing this way I get

[[60Z8]]=ζδξγρ.

In summary: If I have my own conception of number in terms of base q strings of digits, then I have way to interpret your numbers from base b into my own system, based on the fundamental arithmetic operations - which operate natively in base q.

Discrete lizard
quelle
1
Well that was a good deal of squiggly lines. How would I get the computer to do that though?
Griffin
1
@Griffin, I think you are asking that (strange) question prematurely. You pick a programming language and type out the algorithm for addition and multiplication on base q numbers (represented as lists of digits), then define a function to interpret base b digits into base q numbers and interpret base b numbers into base q numbers. I've explained all this.
Thing is I know the concept your trying to portray. My problem is my computer can't use your squiggly lines.
Griffin
I know what you explained but putting it into practice is far harder. You see defining those digits isn't as easy.
Griffin
1
Also why did you drop the alpha digit in the most significant position? Since 6 = &xi;, Wouldn't 7 = &alpha;&alpha;?
Giovanni Botta
9

This is just a refactoring (Python 3) of Andrej's code. In Andrej's code numbers are represented through a list of digits (scalars), while in the following code numbers are represented through a list of symbols taken from a custom string:

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)

To perform a conversion from value to representation in a custom base:

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

To perform a conversion from representation (in a custom base) to value:

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

To perform a base conversion from one custome base to another:

>>> b2b('1120','012','01')
'101010'
>>> b2b('100','01','0123456789')
'4'
>>> b2b('100','0123456789ABCDEF','01')
'100000000'
mmj
quelle
1
Welcome to the site and thanks for your contribution. However, producing well-optimized source code isn't what this site is really about. Andrej's code makes the concepts clear, which is what is needed for his answer, but improving the code beyond that is a matter of programming, rather than computer science.
David Richerby
1
@DavidRicherby I partly agree, but this contribution was too long for a comment and its best place to be is somewhere near Andrej's answer, that's why I posted it here. Anyway if you think it's better I could convert it to a comment with a link to the code, but wouldn't it be an excess of purism?
mmj
1

Die grundlegende Funktionsweise der Basiskonvertierung ist die toDigits()Funktionsweise von @AndrejBauer answer. 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 spezielle Funktion zum Testen von Null erstellt werden

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

Irgendwann muss man die Operation modulo_div ausführen, die eigentlich die Standardeinteilung 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 Testüberprü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]
Xavier Combelle
quelle
Vielen Dank für die Veröffentlichung, aber bitte beachten Sie, dass wir keine Codierungssite sind. Daher ist ein großer Codeblock als Antwort hier nicht angebracht. Besonders wenn die Frage explizit lautet: "Ich brauche keinen Code, ich brauche nur die grundlegende Mathematik dahinter."
David Richerby
@DavidRicherby Ich habe versucht, Text hinzuzufügen.
Xavier Combelle
Vielen Dank. Und ich sehe, dass es auf dieser Seite eine Menge Code gibt, trotz allem, was ich gesagt habe!
David Richerby
0

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

Um von einer Basis zu einer Basis 2 zu konvertieren, müssen Sie nur erkennen, dass für jede Zahl, wenn Sie die Notation der Basis 2 verwenden und bei 0 beginnen, und dann für jede Ziffer in der Reihenfolge von links nach rechts das Doppelte, wenn diese Ziffer Null und ist Wenn diese Ziffer gleich 1 ist, erhalten Sie diese Zahl. Wenn Sie nun diese Zahl in einer beliebigen Basis angeben, können Sie sie 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 und so weiter, bis Sie einen Quotienten von 0 erhalten.

Um von der Basis 2 zu einer beliebigen Basis zu konvertieren, müssen Sie nur in dieser Basis beginnen und mit 0 beginnen. Wenn diese Ziffer 0 ist, verdoppeln Sie für jede von links nach rechts gehende Binärziffer die Zahl in dieser Basis und addieren dann 1 dazu Basis, wenn diese Ziffer 1 ist.

Timothy
quelle
2 is so easy to multiply or divide by in any base.Ich sehe das nicht für ungerade Basen, die mehr als eins aus jeder Potenz von zwei sind (11 und 13, um damit zu beginnen).
Greybeard
0

Sie können von Base n zu Base 10 konvertieren, ohne eine Konvertierung in eine Zwischenbase vorzunehmen.

Um beispielsweise von Basis n zu Basis 9 zu konvertieren, verwenden Sie den Algorithmus für die Konvertierung zu Basis 10 und ersetzen "10" durch "9". Das gleiche gilt für jede andere Basis.

gnasher729
quelle