Le calcul derrière la conversion d'une base à une base sans passer par la base 10?

Je me suis penché sur le calcul derrière la conversion d'une base à une autre. Il s’agit plus de confirmer mes résultats que d’autre chose. J'ai trouvé ce qui semble être ma réponse sur mathforum.org mais je ne suis toujours pas sûr d'avoir bien compris. J'ai la conversion d'une base plus grande à une base plus petite, d'accord parce que c'est simplement prendre le premier chiffre à multiplier par la base que vous voulez ajouter au prochain chiffre à répéter. Mon problème vient de la conversion d'une base plus petite en une base plus grande. Ce faisant, ils expliquent comment vous devez convertir la plus grande base que vous souhaitez en une plus petite. Par exemple, si vous passez de la base 4 à la base 6, vous devez convertir le nombre 6 en base 4 et en obtenir 12. Vous faites alors la même chose que lorsque vous convertissiez de grande à petite. La difficulté que j'ai avec ceci est qu'il semble que vous ayez besoin de savoir quel numéro est dans l'autre base. J'aurais donc besoin de savoir ce qui est 6 dans la base 4. Cela crée un gros problème dans mon esprit car il me faudrait alors un tableau. Est-ce que quelqu'un connaît un moyen de le faire d'une meilleure façon.

Je pensais qu'une conversion de base aiderait, mais je ne peux en trouver aucun qui fonctionne. Et sur le site, je trouve que cela semble vous permettre de convertir de base en base sans passer par la base 10, mais vous devez d’abord savoir comment convertir le premier nombre de base en base. Cela le rend un peu inutile.

Les commentateurs disent que je dois être capable de convertir une lettre en un nombre. Si c'est le cas, je le sais déjà. Ce n'est pas mon problème cependant. Mon problème est de convertir une grande base en une petite base. Je dois d’abord convertir le numéro de base que j'ai en un nombre de base que je veux. Ce faisant, je rejette le but parce que, si j’ai la capacité de convertir ces bases en d’autres bases, j'ai déjà résolu mon problème.

Edit: J'ai découvert comment convertir des bases inférieures ou égales à 10 en d'autres bases inférieures ou égales à 10. Je peux également passer d'une base supérieure à 10 à une base inférieure ou égale à 10. Le problème commence lors de la conversion d'une base supérieure à 10 en une autre base supérieure à 10. Ou du passage d'une base inférieure à 10 à une base supérieure à 10. Je n'ai pas besoin de code, j'ai juste besoin des bases mathématiques qui peuvent être derrière appliqué au code.

Cela me semble une question très fondamentale, alors excusez-moi si je vous fais un peu la leçon. Le point le plus important à apprendre ici est qu’un nombre n’est pas sa représentation numérique . Un nombre est un objet mathématique abstrait, alors que sa représentation numérique est une chose concrète, à savoir une séquence de symboles sur un papier (ou une séquence de bits dans la mémoire de calcul, ou une séquence de sons que vous faites lorsque vous communiquez un nombre). Ce qui vous dérange, c'est que vous ne voyez jamais un chiffre mais toujours sa représentation numérique. Vous finissez donc par penser que le nombre est la représentation.

Par conséquent, la bonne question à poser n’est pas "comment convertir une base en une autre", mais "comment savoir quel numéro est représenté par une chaîne de chiffres donnée" et "comment trouver la représentation numérique d’un chiffre?". numéro donné ".

Alors produisons deux fonctions en Python, l’une pour convertir une représentation numérique en un nombre et l’autre pour faire le contraire. Remarque: lors de l'exécution de la fonction, Python imprimera bien sûr à l'écran le numéro obtenu en base 10. Cela ne signifie toutefois pas que l'ordinateur conserve les numéros en base 10 (ce n'est pas le cas). La façon dont l'ordinateur représente les nombres n'a aucune importance .

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

Laissez-nous tester ces:

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

Armé de fonctions de conversion, votre problème est résolu facilement:

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

Un examen:

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

Remarque: nous n'avons pas traversé la représentation en base 10! Nous avons converti la représentation base en nombre, puis le nombre en base c . Le nombre était pas dans une représentation. (En fait, l'ordinateur devait le représenter d'une manière ou d'une autre, et le représentait en utilisant des signaux électriques et des trucs géniaux qui se produisent dans les puces, mais ce ne sont certainement pas des 0 et des 1.)$b$$c$

Je pense que la meilleure façon de comprendre cela est de discuter avec un étranger (au moins par analogie).

La définition est un nombre en base $x$$b$ signifie que est une chaîne de chiffres < b .$x$$<b$

Exemples La chaîne de chiffres 10010011011 est un nombre en base 2, la chaîne 68416841531 est un nombre en base 10, BADCAFE est un nombre en base 16.

Maintenant, supposons que j'ai grandi sur la planète QUUX où tout le monde apprend à travailler dans toute sa vie, et que je vous rencontre, vous qui avez l'habitude de baser b . Alors tu me montres un numéro et que dois-je faire? J'ai besoin d'un moyen de l'interpréter:$q$$b$

Définition Je peux interpréter un nombre en base (Remarque: b est un nombre en base q ) à l'aide de la formule suivante$b$$b$$q$

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

où désigne la chaîne vide et ˉ s d une chaîne se terminant par le chiffre d . Voir ma preuve que l'addition ajoute pour une introduction à cette notation.$\epsilon$$\bar s d$$d$

Alors qu'est-ce qui s'est passé ici? Vous m'avez donné un chiffre en base et je l'ai interprété en base q sans aucune philosophie étrange sur ce que sont réellement les nombres.$b$$q$

Key La clé de ceci est que le et le + que j'ai sont des fonctions qui fonctionnent sur des nombres de base q . Ce sont des algorithmes simples définis récursivement sur des nombres de base q (chaînes de chiffres).$\times$$+$$q$$q$

---

Cela peut sembler un peu abstrait puisque j'ai toujours utilisé des variables plutôt que des nombres réels. Alors supposons que vous êtes une créature de base 13 ( en utilisant des symboles ) et je suis habitué à la base 7 (qui est beaucoup plus sensible) en utilisant des symboles a ß gamma ô p Ç Ç .$0123456789XYZ$$\alpha \beta \gamma \delta \rho \zeta \xi$

J'ai donc vu votre alphabet et le tabulé ainsi:

$$\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}$$

Donc , je sais que vous travaillez dans la base , et je sais ce que le numéro 7 de base un chiffre que vous écrivez correspond à.$\beta\xi$

Maintenant, si nous parlions de physique et que vous me parliez de constantes fondamentales (disons) , je dois donc interpréter ceci:$60Z8$

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

Je commence par la multiplication des mais est de qualité des choses de l' école pour moi, je me souviens:$\beta \zeta \times \beta\xi$

Table de multiplication Quux

$$\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}$$

$\beta \zeta \times \beta\xi$

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

donc j'ai jusqu'ici

$$\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}$$

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

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

so

$$\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}$$

and continuing this way I get

$$[\![60Z8]\!] = \zeta\delta\xi\gamma\rho.$$

---

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

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'

Fundamental operation of base convertion is the toDigits() operation of @AndrejBauer answer. However, to make it there is no need to create a number in the internal representation of the numbers, which is basically a conversion from and to base 2 representation. You can make the needed operations in the original base representation.

So the first step is to do repetitive modulo division operation

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

As the internal representation is digits, one has to make a specilaised function for testing zero

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

Eventually one has to make the modulo_div operation which is actually the standard division by destination base as we learnt at school.

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

just a test check to verify the code is correct:

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]

I know an easy way to do base conversion that doesn't require a computer program. It's by defining a way to convert from any base to base 2 and vice versa and then coverting from one base to another base by first converting from the first base to base 2 then converting from base 2 to the other base. 2 is so easy to multiply or divide by in any base.

To convert from any base to base 2, all you have to do is recognize that for any number, if you take its base 2 notation and start from 0 and then for each digit in order from left to right double if that digit is zero and double than add 1 if that digit is 1, you get to that number itself. Now given that number in any base, you can divide by 2 in that base to get a quotient and remainder. If the remainder is 1, the last binary digit is 1 and if the remainder is 0, the last binary digit is 0. Divide by 2 again. If the remainder is 1, the second last digit is 1 and if the remainder is 0, the second last digit is 0 and so on until you get a quotient of 0.

To convert from base 2 to any base, all you have to do is in that base, start from 0, then for each binary digit going from left to right, double in that base if that digit is 0 and double then add 1 in that base if that digit is 1.

You can convert from base n to base 10 without any conversion to some intermediate base.

To convert from base n to base 9, for example, you take the algorithm for conversion to base 10, and replace “10” with “9”. Same for any other base.