Les mathématiques derrière la conversion de nimporte quelle base à nimporte quelle base sans passer par la base 10?

Cela me semble une question très basique, alors excusez-moi si je vous fais un peu la morale. Le point le plus important que vous devez apprendre ici est que un nombre nest 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 en mémoire de calcul, ou une séquence de sons que vous émettez lorsque vous communiquez un nombre). Ce qui vous déroute, cest le fait que vous ne voyez jamais un nombre 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 nest pas  » comment puis-je convertir dune base en une autre  » mais plutôt  » comment savoir quel nombre est représenté par une chaîne donnée de chiffres  » et  » comment trouver la représentation numérique dun nombre donné « .

Produisons donc deux fonctions en Python, une pour convertir une représentation numérique en un certain nombre, et un autre pour faire le contraire. Remarque: lorsque nous exécutons la fonction Python va bien sûr imprimer à lécran le numéro quil a obtenu en base 10. Mais cela ne signifie pas que lordinateur garde les nombres en base 10 (ce nest pas « t). La façon dont lordinateur représente les nombres na 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 

Testons ces derniers:

>>> 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 se résout 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 test :

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

Remarque: nous lavons fait pas passer par la représentation de base 10! Nous avons converti la représentation de base $ b $ en nombre, puis le nombre en base $ c $ . Le nombre nétait pas dans aucune représentation. (En fait, il était, lordinateur devait le représenter dune manière ou dune autre, et il la représenté en utilisant des signaux électriques et funky trucs qui se produisent dans les puces, mais certainement ceux w Il ny a pas 0 « s et 1 » s.)

Commentaires

• Cela ne ‘ pas convaincre moi à 100%. En fait, vous avez converti le nombre en une représentation (bien que vous puissiez prétendre ne pas savoir ce que cest) parce que les ordinateurs ne sont pas des mathématiciens platoniques et votre algorithme ne peut pas convertir une séquence arbitraire de chiffres en base $ b_1 $ en base $ b_2 $; il ne peut convertir que des séquences représentables par la machine à béton. Python est délicieusement flexible; C naurait pas été si indulgent. Il est parfaitement valable de se demander comment convertir des chaînes arbitraires de $ b_1 $ en $ b_2 $; cependant, cela nest possible quen temps linéaire, sauf avec certaines combinaisons de base (par exemple 2 < – > 16)
• Il est valide de poser la question, mais pour trouver la bonne réponse, il vaut mieux être conscient du fait que les nombres sont des entités abstraites.
• Ceci fait passer le nombre via la représentation en base 10, car fromDigits renvoie le nombre en base 10.
• @anorton: Non, certainement pas . Python imprime le nombre à lécran dans une représentation de base à 10 chiffres, mais le nombre lui-même nest pas stocké de cette façon. Ce que jessaie de comprendre, cest que la manière dont les nombres sont implémentés dans Python est sans importance . Cela na pas dimportance. La seule chose qui compte, cest quils se comportent comme des nombres.
• Enfin une solution générale pour nimporte quelle base et non limitée à des cas dutilisation particuliers, des bases inférieures à 36 ou des instances où vous pouvez trouver suffisamment de symboles uniques .

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

Définition $ x $ est un nombre en base $ b $ signifie que $ x $ est une chaîne de chiffres $ < 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 jai grandi sur la planète QUUX où tout le monde apprend à travailler en $ q $ toute sa vie, et que je vous rencontre qui est habitué à baser $ b $. Alors vous me montrez un numéro, et que dois-je faire? Jai besoin dun moyen de linterpréter:

Définition Je peux interpréter un nombre en base $ b $ (Remarque: $ b $ est un nombre en base $ q $) par la formule suivante

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

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

Alors, que sest-il passé ici? Vous mavez donné un numéro en base $ b $ et je « lai interprété en base $ q $ sans aucune philosophie bizarre sur ce que sont vraiment les nombres.

Clé La clé de ceci est que les $ \ times $ et $ + $ que jai sont des fonctions qui opèrent 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).

Cela peut sembler un peu abstrait car jai utilisé des variables plutôt que des nombres réels. Supposons donc que vous soyez une créature de base 13 (en utilisant les symboles $ 0123456789XYZ $) et je suis utilisé en base 7 (ce qui est beaucoup plus judicieux) en utilisant les symboles $ \ alpha \ beta \ gamma \ delta \ rho \ zeta \ xi $.

Jai donc vu votre alphabet et je lai 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 en base $ \ beta \ xi $, et je sais quel nombre de base 7 vous écrire correspond à.

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

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

Je commence donc par multiplier $ \ beta \ zeta \ times \ beta \ xi $ mais ce sont des trucs décole primaire pour moi, je me souviens:

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

donc pour trouver $ \ beta \ zeta \ times \ beta \ xi $ je fais:

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

donc je suis allé jusquici

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

Maintenant, je dois effectuer laddition en utilisant lalgorithme qui a été mentionné auparavant:

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

donc

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

et en continuant de cette manière, jobtiens $$ [\! [60Z8] \!] = \ zeta \ delta \ xi \ gamma \ rho. $$

In résumé: Si jai ma propre conception du nombre en termes de chaînes de chiffres de base $ q $, alors jai le moyen dinterpréter vos nombres de base $ b $ dans mon propre système, basé sur les opérations arithmétiques fondamentales – qui opèrent nativement dans base $ q $.

Commentaires

• Et bien cétait beaucoup de lignes ondulées. Comment pourrais-je faire en sorte que lordinateur fasse ça?
• @Griffin, je pense que vous posez cette (étrange) question prématurément. Vous choisissez un langage de programmation et tapez lalgorithme pour laddition et la multiplication sur les nombres de base q (représentés sous forme de listes de chiffres), puis définissez une fonction pour interpréter les chiffres de base b en nombres de base q et interpréter les nombres de base b en nombres de base q. Jai ‘ expliqué tout cela.
• Le fait est que je connais le concept que vous essayez de décrire. Mon problème est que mon ordinateur ne peut ‘ utiliser vos lignes ondulées.
• Je sais ce que vous avez expliqué, mais le mettre en pratique est beaucoup plus difficile. Vous voyez que la définition de ces chiffres n’est ‘ que facile.
• Pourquoi avez-vous également laissé tomber le chiffre alpha à la position la plus significative? Puisque 6 = & xi ;, wouldn ‘ t 7 = & alpha; & alpha ;?

Il sagit dun refactoring (Python 3) du code de Andrej « . Alors que dans Andrej, les numéros de code sont représentés par une liste de chiffres (scalaires), dans les numéros de code suivants sont représentés par une liste de symboles arbitraires tirée dune chaîne personnalisée:

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) 

Pour effectuer une conversion de valeur en représentation dans une base personnalisée:

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

Pour effectuer une conversion de représentation (dans une base personnalisée) en valeur :

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

Pour effectuer une conversion de base dune base personnalisée à une autre:

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

Commentaires

• Bienvenue sur le site et merci pour votre contribution. Cependant, produire un code source bien optimisé n’est ‘ que l’objet de ce site. Le code dAndrej ‘ rend les concepts clairs, ce qui est nécessaire pour sa réponse, mais améliorer le code au-delà de cela est une question de programmation, plutôt que dinformatique science .
• @DavidRicherby Je suis en partie daccord, mais cette contribution était trop longue pour un commentaire et son meilleur endroit pour être est quelque part près de la réponse dAndrej ‘, cest ‘ que je lai posté ici. Quoi quil en soit, si vous pensez que ‘ est mieux, je pourrais le convertir en commentaire avec un lien vers le code, mais ‘ que ce soit un excès de purisme?
• Malgré @David ‘ s  » site-purist  » objections, jai trouvé votre réponse utile car elle met laccent sur le fait que les bases impliquées peuvent être considérées de manière plus abstraite comme  » alphabets  » de symboles arbitraires de différentes longueurs – et non limités à la plage habituelle de 2 à 36 caractères. Vous pourriez en fait considérer les flux doctets comme les  » chiffres  » de valeurs entières de base 256.

Lopération fondamentale de conversion de base est lopération toDigits() de la réponse @AndrejBauer. Cependant, pour le faire, il nest pas nécessaire de créer un nombre dans la représentation interne des nombres, qui est essentiellement une conversion de et vers une représentation en base 2.Vous pouvez effectuer les opérations nécessaires dans la représentation de base dorigine.

La première étape est donc de faire une opération de division modulo répétitive

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 

Comme la représentation interne est composée de chiffres, il faut faire une spécification fonction pour tester zéro

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

Finalement, on doit faire lopération modulo_div qui est en fait la division standard par base de destination comme nous lavons appris à lécole.

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 

juste un test de vérification pour vérifier que le code est 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] 

Commentaires

• Merci davoir posté mais veuillez noter que nous ‘ ne sommes pas un site de codage, donc un gros bloc de code nest pas ‘ t approprié comme réponse ici. Surtout quand la question dit explicitement,  » Je nai ‘ pas besoin de code, jai juste besoin des calculs de base.  »
• @DavidRicherby Jai essayé dajouter du texte.
• Merci. Et je vois là ‘ beaucoup de code sur cette page, malgré ce que jai dit!
• @David: FWIW, je pense que cela répond à lOP ‘ est la meilleure question car elle montre comment convertir entre les deux bases sans dabord convertir la représentation de loriginal en une forme intermédiaire, puis la convertir en base de destination.
• Bien essayé, mais d est toujours en base 10, donc vous extrayez en fait une partie plus petite de n en le convertissant en base 10, puis en le convertissant en base souhaitée et en les collectant dans le résultat final.

Je connais un moyen simple de faire une conversion de base qui ne nécessite pas de programme informatique. Cest en définissant un moyen de convertir de nimporte quelle base en base 2 et vice versa, puis de passer dune base à une autre base en convertissant dabord de la première base en base 2 puis en convertissant de la base 2 à lautre base. 2 est si facile à multiplier ou à diviser par dans nimporte quelle base.

Pour convertir de nimporte quelle base en base 2, tout ce que vous avez à faire est de reconnaître que pour nimporte quel nombre, si vous prenez sa notation de base 2 et commencez à partir de 0, puis pour chaque chiffre dans lordre de gauche à droite, doubler si ce chiffre est égal à zéro et doubler ensuite ajouter 1 si ce chiffre est 1, vous obtenez ce nombre lui-même. Maintenant, étant donné ce nombre dans nimporte quelle base, vous pouvez diviser par 2 dans cette base pour obtenir un quotient et un reste. Si le reste est 1, le dernier chiffre binaire est 1 et si le reste est 0, le dernier chiffre binaire est 0. Divisez à nouveau par 2. Si le reste est 1, lavant-dernier chiffre est 1 et si le reste est 0, lavant-dernier chiffre est 0 et ainsi de suite jusquà ce que vous obteniez un quotient de 0.

Pour convertir de la base 2 en nimporte quel base, tout ce que vous avez à faire est dans cette base, commencez par 0, puis pour chaque chiffre binaire allant de gauche à droite, doublez dans cette base si ce chiffre est 0 et doublez puis ajoutez 1 dans cette base si ce chiffre est 1.

Commentaires

• 2 is so easy to multiply or divide by in any base. Je ne ‘ t voir cela pour les bases impaires qui sont plus dune de toute puissance de deux (11 et 13, pour commencer).

Vous pouvez convertir de la base n en base 10 sans aucune conversion vers une base intermédiaire.

Pour convertir de la base n en base 9, par exemple, vous prenez lalgorithme de conversion en base 10, et remplacez «10» par «9». Idem pour toute autre base.