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

He estado investigando las matemáticas detrás de la conversión de cualquier base a cualquier base. Esto se trata más de confirmar mis resultados que de nada. Encontré lo que parece ser mi respuesta en mathforum.org pero todavía no estoy seguro de tener la respuesta correcta. La conversión de una base más grande a una base más pequeña está bien porque es simplemente tomar el primer dígito multiplicar por la base que desea agregar la repetición del siguiente dígito. Mi problema surge al convertir de una base más pequeña a una más grande. Al hacer esto, hablan sobre cómo necesita convertir la base más grande que desea en la base más pequeña que tiene. Un ejemplo sería pasar de la base 4 a la base 6, necesita convertir el número 6 en la base 4 obteniendo 12. Luego, simplemente hace lo mismo que cuando convertía de grande a pequeño. La dificultad que tengo con esto es que parece que necesitas saber cuál es un número en la otra base. Por lo tanto, habría necesitado saber qué es 6 en la base 4. Esto crea un gran problema en mi mente porque necesitaría una tabla. ¿Alguien sabe una manera de hacer esto de una mejor manera?

Pensé que una conversión de base ayudaría, pero no puedo encontrar ninguna que funcione. Y desde el sitio que encontré parece que te permite convertir de base a base sin pasar por la base 10, pero primero debes saber cómo convertir el primer número de base a base. Eso lo hace un poco inútil.

Los comentaristas dicen que necesito poder convertir una letra en un número. Si es así, ya lo sé. Sin embargo, ese no es mi problema. Mi problema es para convertir una base grande en una base pequeña. Primero necesito convertir el número base que tengo en el número base que quiero. Al hacerlo, rechazo el propósito porque si tengo la capacidad de convertir estas bases a otras bases, ya he resuelto mi problema.

Editar: He descubierto cómo convertir de bases menores o iguales a 10 en otras bases menores o iguales a 10. También puedo pasar de una base mayor que 10 a cualquier base que sea 10 o menor. El problema comienza cuando se convierte de una base mayor que 10 a otra base mayor que 10. O al pasar de una base menor que 10 a una base mayor que 10. No necesito código, solo necesito las matemáticas básicas detrás de él que pueden ser aplicado al código.

Esto me parece una pregunta muy básica, así que discúlpeme si le doy un poco de clase. 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 algo concreto, 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 haces cuando comunicas un número). Lo que te confunde es el hecho de que nunca ves un número, sino siempre su representación en dígitos. Entonces terminas pensando que el número es la representación.

Por lo tanto, la pregunta correcta no es "cómo convertir de una base a otra", sino más bien "cómo averiguo qué número está representado por una cadena de dígitos determinada" 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 en un número y otra para hacer lo contrario. Nota: cuando ejecutamos la función Python, por supuesto, imprimirá en la pantalla el número que obtuvo en la base 10. Pero esto no significa que la computadora mantenga los números en la base 10 (no lo está). 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 estos:

>>> 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: ¡ no pasamos por la representación de base 10! Convertimos la representación de la base al número, y luego el número a la base . El número no estaba en ninguna representación. (En realidad lo fue, la computadora tuvo que representarlo de alguna manera, y lo hizo usando señales eléctricas y cosas funky que ocurren en los chips, pero ciertamente no eran 0 y 1).$b$$c$

Creo que la mejor manera de entender esto es discutiendo con un alienígena (al menos como analogía).

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

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

Ahora supongamos que crecí en el planeta QUUX, donde a todos se les enseña a trabajar en durante toda su vida, y me encuentro con ustedes que están acostumbrados a la base . Entonces me muestras un número y ¿qué hago? Necesito una forma de interpretarlo:$q$$b$

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

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

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

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

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

---

Esto puede parecer un poco abstracto ya que he estado usando variables en lugar de números reales en todo momento. Supongamos que eres una criatura base 13 (usando los símbolos ) y estoy acostumbrado a la base 7 (que es mucho más sensible) usando símbolos .$0123456789XYZ$$\alpha \beta \gamma \delta \rho \zeta \xi$

Así que he visto tu alfabeto y lo he tabulado 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 , y sé a qué número de base 7 corresponde cualquier dígito que escribas.$\beta\xi$

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

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

Así que empiezo multiplicando pero esto es algo de la escuela primaria para mí, recuerdo:$\beta \zeta \times \beta\xi$

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

para encontrar hago:$\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}$$

así que llegué tan lejos

$$\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 adición usando el algoritmo que se mencionó antes:

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

asi que

$$\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 así 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 de base , entonces tengo forma de interpretar sus números desde la base en mi propio sistema, en función de las operaciones aritméticas fundamentales, que operan de forma nativa en la base .b $q$$b$$q$

Esto es solo una refactorización (Python 3) del código de Andrej . En los números de código de Andrej se representan a través de una lista de dígitos (escalares), mientras que en los siguientes números de código se representan a través de una lista de símbolos 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 de base de una base personalizada a otra:

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

La operación fundamental de la conversión de base es la toDigits()operación de 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.

Entonces, el primer paso es hacer una operación de división de módulo repetitiva

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 función especificada 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 en realidad es 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 prueba de verificación 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]

Conozco una manera fácil de hacer una conversión base que no requiere un programa de computadora. Es definiendo una forma de convertir de cualquier base a la base 2 y viceversa y luego convirtiendo de una base a otra base, primero convirtiendo 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 tiene que hacer es reconocer eso para cualquier número, si toma su notación de base 2 y comienza desde 0 y luego para cada dígito en orden de izquierda a derecha, doble si ese dígito es cero y el doble de sumar 1 si ese dígito es 1, obtienes 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 el 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. Divida nuevamente entre 2. Si el resto es 1, el segundo último dígito es 1 y si el resto es 0, el segundo último dígito es 0 y así sucesivamente hasta obtener un cociente de 0.

Para convertir de la base 2 a cualquier base, todo lo que tiene que hacer es en esa base, comience desde 0, luego, para cada dígito binario que vaya de izquierda a derecha, doble en esa base si ese dígito es 0 y doble, luego agregue 1 en ese base si ese dígito es 1.

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

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