¿Las matemáticas detrás de la conversión de cualquier base a cualquier base sin pasar por la base 10?

Esta me parece una pregunta muy básica, así que discúlpeme si le doy un poco de sermón. El punto más importante que debe aprender aquí es que un número no es su representación de dígitos . Un número es un objeto matemático abstracto, mientras que su representación de dígitos es una cosa concreta, es decir, una secuencia de símbolos en un papel (o una secuencia de bits en la memoria de cálculo, o una secuencia de sonidos que hace cuando comunica un número). Lo que te confunde es el hecho de que nunca ves un número sino siempre su representación de dígitos. Entonces terminas pensando que el número es la representación.

Por lo tanto, la pregunta correcta no es » cómo convierto de una base a otra » sino en lugar de » ¿cómo averiguo qué número está representado por una determinada cadena de dígitos » y » ¿cómo encuentro la representación de dígitos de un número dado «.

Así que produzcamos dos funciones en Python, una para convertir una representación de dígitos a un número y otro para hacer lo contrario. Nota: cuando ejecutamos la función Python, por supuesto, imprimirá en la pantalla el número que obtuvo en base 10. Pero esto no significa que la computadora está manteniendo los números en base 10 (no es «t). Es irrelevante cómo la computadora representa los números.

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 

Probemos lo siguiente:

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

Armado con funciones de conversión, su problema se resuelve fácilmente:

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

Una prueba :

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

Nota: hicimos ¡no pasar a través de la representación base 10! Convertimos la representación $ b $ base al número, y luego el número a la base $ c $ . El número no estaba en ninguna representación. (En realidad, lo era, la computadora tenía que representarlo de alguna manera, y lo representó usando señales eléctricas y funky cosas que pasan en chips, pero ciertamente esos w No hay 0 «sy 1».)

Comentarios

• Esto no ‘ no convence yo 100%. De hecho, convirtió el número en alguna representación (aunque puede afirmar que no sabe qué es) porque las computadoras no son matemáticos platónicos y su algoritmo no puede convertir una secuencia arbitraria de dígitos en base $ b_1 $ a base $ b_2 $; sólo puede convertir secuencias representables por la máquina de hormigón. Python es encantadoramente flexible; C no habría sido tan indulgente. Es perfectamente válido preguntar cómo convertir cadenas arbitrarias de $ b_1 $ a $ b_2 $; sin embargo, esto solo es posible en tiempo lineal excepto con ciertas combinaciones de bases (por ejemplo, 2 < – > 16)
• Es válido hacer la pregunta, pero para encontrar la respuesta correcta es mejor ser consciente del hecho de que los números son entidades abstractas.
• Esto sí pasa el número a través de la representación en base 10, ya que fromDigits devuelve el número en base 10.
• @anorton: No, definitivamente no . Python imprime el número en la pantalla en una representación de base de 10 dígitos, pero el número en sí no se almacena de esa manera. Lo que estoy tratando de entender es que es irrelevante cómo se implementan los números dentro de Python. No importa. Lo único que importa es que se comportan como números.
• Finalmente, una solución general para cualquier base y no se limita a casos de uso particulares, bases menores a 36 o instancias en las que se pueden encontrar suficientes símbolos únicos .

Creo que la mejor manera de entender esto es en una discusión con un extraterrestre (al menos una analogía).

Definición $ x $ es un número en base $ b $ significa que $ x $ es una cadena de dígitos $ < b $.

Ejemplos La cadena de dígitos 10010011011 es un número en base 2, la cadena 68416841531 es un número en base 10, BADCAFE es un número en base 16.

Ahora Supongamos que crecí en el planeta QUUX, donde a todos se les enseña a trabajar en $ q $ durante toda su vida, y te conozco, que estás acostumbrado a basar $ b $. Entonces muéstrame un número y ¿qué hago? Necesito una forma de interpretarlo:

Definición Puedo interpretar un número en la base $ b $ (Nota: $ b $ es un número en la base $ q $) por la siguiente fórmula

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

donde $ \ epsilon $ denota la cadena vacía, y $ \ bar sd $ denota una cadena que termina en el dígito $ d $. Vea mi prueba de que la adición agrega para una introducción a esta notación.

Entonces, ¿qué sucedió aquí? Me ha dado un número en base $ b $ y lo he interpretado en base $ q $ sin ninguna filosofía extraña sobre lo que realmente son los números.

Clave La clave es que $ \ times $ y $ + $ que tengo son funciones que operan en números base $ q $. Estos son algoritmos simples definidos recursivamente en números base $ q $ (cadenas de dígitos).

Esto puede parecer un poco abstracto ya que he estado usando variables en lugar de números reales en todo momento. Así que supongamos que eres una criatura de base 13 (usando símbolos $ 0123456789XYZ $) y yo soy utilizado para la base 7 (que es mucho más sensato) usando símbolos $ \ alpha \ beta \ gamma \ delta \ rho \ zeta \ xi $.

Así que he visto su alfabeto y lo tabulé así:

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

Entonces sé que trabajas en base $ \ beta \ xi $, y sé qué número en base 7 cualquier dígito escribe corresponde a.

Ahora, si estuviéramos hablando de física y me estuvieras hablando sobre constantes fundamentales (digamos) $ 60Z8 $, entonces necesito interpretar esto:

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

Entonces empiezo multiplicando $ \ beta \ zeta \ times \ beta \ xi $ pero esto es cosa de la escuela primaria para mí, lo recuerdo:

Tabla de multiplicar de 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} $$

así que para encontrar $ \ beta \ zeta \ times \ beta \ xi $ lo hago:

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

así que he llegado hasta aquí

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

Ahora necesito realizar la suma usando el algoritmo que se mencionó anteriormente:

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

entonces

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

y continuando de esta manera obtengo $$ [\! [60Z8] \!] = \ zeta \ delta \ xi \ gamma \ rho. $$

En resumen: si tengo mi propia concepción del número en términos de cadenas de dígitos base $ q $, entonces tengo una forma de interpretar sus números desde la base $ b $ en mi propio sistema, basado en las operaciones aritméticas fundamentales, que operan de forma nativa en base $ q $.

Comentarios

• Bueno, eso fue una buena cantidad de líneas onduladas. Sin embargo, ¿cómo conseguiría que la computadora hiciera eso?
• @Griffin, creo que estás haciendo esa (extraña) pregunta prematuramente. Usted elige un lenguaje de programación y escribe el algoritmo para sumar y multiplicar en números base q (representados como listas de dígitos), luego define una función para interpretar dígitos base b en números base q e interpretar números base b en números base q. ‘ he explicado todo esto.
• La cosa es que conozco el concepto que estás tratando de representar. Mi problema es que mi computadora no puede ‘ usar sus líneas onduladas.
• Sé lo que explicó, pero ponerlo en práctica es mucho más difícil. Considera que definir esos dígitos no es ‘ t tan fácil.
• Además, ¿por qué dejó caer el dígito alfabético en la posición más significativa? Dado que 6 = & xi ;, wouldn ‘ t 7 = & alpha; & alpha ;?

Esta es una refactorización (Python 3) del código de Andrej «s . Mientras que en el código de Andrej los números se representan mediante una lista de dígitos (escalares), en los siguientes números de código se representan mediante una lista de símbolos arbitrarios tomados de una cadena personalizada:

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) 

Para realizar una conversión de valor a representación en una base personalizada:

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

Para realizar una conversión de representación (en una base personalizada) a valor :

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

Para realizar una conversión base de una base personalizada a otra:

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

Comentarios

• Bienvenido al sitio y gracias por su contribución. Sin embargo, producir un código fuente bien optimizado no es ‘ t de lo que realmente se trata este sitio. El código de Andrej ‘ aclara los conceptos, que es lo que se necesita para su respuesta, pero mejorar el código más allá de eso es una cuestión de programación, en lugar de informática ciencia .
• @DavidRicherby Estoy parcialmente de acuerdo, pero esta contribución fue demasiado larga para un comentario y el mejor lugar para estar es en algún lugar cerca de la respuesta de Andrej ‘, esa ‘ es la razón por la que lo publiqué aquí. De todos modos, si crees que es ‘ mejor, podría convertirlo en un comentario con un enlace al código, pero no ‘ un exceso de purismo?
• A pesar de @David ‘ s » site-purist » objeciones, encontré su respuesta útil porque enfatiza el hecho de que las bases involucradas se pueden considerar en términos más abstractos como » alfabetos » de símbolos arbitrarios de diferentes longitudes, y no restringidos al rango habitual de 2 a 36 caracteres. De hecho, podría considerar los flujos de bytes como los » dígitos » de valores enteros base 256.

La operación fundamental de la conversión base es la toDigits() de la respuesta @AndrejBauer. Sin embargo, para hacerlo no es necesario crear un número en la representación interna de los números, que es básicamente una conversión desde y hacia la representación de base 2.Puede realizar las operaciones necesarias en la representación base original.

Así que el primer paso es realizar una operación repetitiva de división de módulo

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 

Como la representación interna son dígitos, uno tiene que hacer una especificación función para probar cero

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

Eventualmente uno tiene que hacer la operación modulo_div que es en realidad la división estándar por base de destino como aprendimos en la escuela.

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 

solo una verificación de prueba para verificar que el código sea correcto:

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] 

Comentarios

• Gracias por publicar, pero tenga en cuenta que ‘ no somos un sitio de codificación, por lo que un gran bloque de código no es ‘ t apropiado como respuesta aquí. Especialmente cuando la pregunta dice explícitamente, » No ‘ no necesito código, solo necesito las matemáticas básicas. »
• @DavidRicherby Traté de agregar texto.
• Gracias. Y veo allí ‘ una gran cantidad de código en esta página, ¡a pesar de lo que dije!
• @David: FWIW, creo que esto responde al OP ‘ s pregunta mejor, ya que muestra cómo convertir entre las dos bases sin convertir primero la representación del original en una forma intermedia y luego convertirla en la base de destino.
• Buen intento, pero d todavía está en base 10, por lo que en efecto está extrayendo una porción más pequeña de n convirtiéndola en base 10, luego convirtiéndola en la base deseada y reuniéndola en el resultado final.

Conozco una forma sencilla de realizar conversiones base que no requiere un programa informático. Es definiendo una forma de convertir de cualquier base a base 2 y viceversa y luego convertir de una base a otra base convirtiendo primero de la primera base a la base 2 y luego convirtiendo de la base 2 a la otra base. 2 es tan fácil de multiplicar o dividir en cualquier base.

Para convertir de cualquier base a base 2, todo lo que tienes que hacer es reconocerlo para cualquier número, si tomas su notación de base 2 y comienzas de 0 y luego para cada dígito en orden de izquierda a derecha, doble si ese dígito es cero y doble que sumar 1 si ese dígito es 1, se obtiene ese número en sí. Ahora, dado ese número en cualquier base, puede dividir por 2 en esa base para obtener un cociente y un resto. Si el resto es 1, el último dígito binario es 1 y si el resto es 0, el último dígito binario es 0. Dividir por 2 nuevamente. Si el resto es 1, el penúltimo dígito es 1 y si el resto es 0, el penúltimo dígito es 0 y así sucesivamente hasta obtener un cociente de 0.

Para convertir de base 2 a cualquier base, todo lo que tienes que hacer es en esa base, comenzar desde 0, luego, para cada dígito binario que vaya de izquierda a derecha, duplicar en esa base si ese dígito es 0 y duplicar, luego agregar 1 en esa base si ese dígito es 1.

Comentarios

• 2 is so easy to multiply or divide by in any base. No ‘ t vea eso para bases impares que sean más de uno de cualquier potencia de dos (11 y 13, para empezar).

Puede convertir de base n a base 10 sin ninguna conversión a una base intermedia.

Para convertir de base n a base 9, por ejemplo, se toma el algoritmo de conversión a base 10 y se reemplaza «10» por «9». Lo mismo para cualquier otra base.