A matemática por trás da conversão de qualquer base para qualquer base sem passar pela base 10?

Esta parece uma pergunta muito básica para mim, então me desculpe se eu lhe der um pequeno sermão. O ponto mais importante para você aprender aqui é que um número não é sua representação em dígitos . Um número é um objeto matemático abstrato, enquanto sua representação de dígitos é uma coisa concreta, ou seja, uma sequência de símbolos em um papel (ou uma sequência de bits na memória do computador, ou uma sequência de sons que você emite quando comunica um número). O que o confunde é o fato de nunca ver um número, mas sempre sua representação em dígitos. Então você acaba pensando que o número é a representação.

Portanto, a pergunta correta a fazer não é ” como faço para converter de uma base para outra “, mas em vez disso, ” como faço para descobrir qual número é representado por uma determinada sequência de dígitos ” e ” como faço para encontrar a representação de dígitos de um determinado número “.

Então, vamos produzir duas funções em Python, uma para converter uma representação de dígitos para um número e outro para fazer o oposto. Observação: quando executamos a função Python, é claro, imprimirá na tela o número obtido na base 10. Mas isso não significa que o computador está mantendo os números na base 10 (não é “t). É irrelevante como o computador representa os 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 

Vamos testar:

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

Armado com funções de conversão, seu problema é resolvido facilmente:

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

Um teste :

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

Observação: nós fizemos não passa pela representação de base 10! Convertemos a representação de base $ b $ em número e, em seguida, o número em $ c $ . O número não em nenhuma representação. (Na verdade, era, o computador tinha que representá-lo de alguma forma, e ele o representou usando sinais elétricos e funky coisas que acontecem em chips, mas certamente aqueles não são 0 “se 1” s.)

Comentários

• Isso não ‘ convence eu 100%. Na verdade, você converteu o número em alguma representação (embora possa alegar não saber o que é) porque os computadores não são matemáticos platônicos e seu algoritmo não pode converter uma sequência arbitrária de dígitos na base $ b_1 $ na base $ b_2 $; ele só pode converter sequências representáveis pela máquina concreta. Python é encantadoramente flexível; C não teria sido tão indulgente. É perfeitamente válido perguntar como converter strings arbitrárias de $ b_1 $ para $ b_2 $; no entanto, isso só é possível em tempo linear, exceto com certas combinações de base (por exemplo, 2 < – > 16)
• É válido fazer a pergunta, mas para encontrar a resposta certa é melhor estar ciente do fato de que os números são entidades abstratas.
• Isso não passa o número por meio da representação de base 10, já que fromDigits retorna o número na base 10.
• @anorton: Não, definitivamente não . Python imprime o número na tela em uma representação de base de 10 dígitos, mas o próprio número não é armazenado dessa forma. O que estou tentando entender é que é irrelevante como os números são implementados dentro do Python. Isso não importa. A única coisa que importa é que eles se comportam como números.
• Finalmente, uma solução geral para qualquer base e não limitada a casos de uso específicos, bases com menos de 36 ou instâncias em que você pode encontrar símbolos únicos suficientes .

Acho que a melhor maneira de entender isso é discutindo com um alienígena (pelo menos como uma analogia).

Definição $ x $ é um número na base $ b $ significa que $ x $ é uma string de dígitos $ < b $.

Exemplos A string de dígitos 10010011011 é um número na base 2, a string 68416841531 é um número na base 10, BADCAFE é um número na base 16.

Agora Suponha que eu cresci no planeta QUUX, onde todos aprendem a trabalhar em $ q $ por toda a vida, e eu encontrei você que costuma basear $ b $. Então você me mostra um número e o que eu faço? Preciso de uma maneira de interpretar:

Definição Posso interpretar um número na base $ b $ (Observação: $ b $ é um número na base $ q $) pela seguinte fórmula

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

onde $ \ epsilon $ denota a string vazia e $ \ bar sd $ denota uma string que termina no dígito $ d $. Veja minha prova de que a adição adiciona para uma introdução a esta notação.

Então, o que aconteceu aqui? Você me deu um número na base $ b $ e eu interpretei na base $ q $ sem nenhuma filosofia estranha sobre o que os números realmente são.

Chave A chave para isso é que $ \ times $ e $ + $ I são funções que operam na base $ q $ números. Estes são algoritmos simples definidos recursivamente na base $ q $ números (strings de dígitos).

Isso pode parecer um pouco abstrato, pois tenho usado variáveis em vez de números reais. Então, vamos supor que você seja uma criatura de base 13 (usando os símbolos $ 0123456789XYZ $) e eu sou usado na base 7 (que é muito mais sensato) usando símbolos $ \ alpha \ beta \ gamma \ delta \ rho \ zeta \ xi $.

Então, eu vi seu alfabeto e tabulei-o assim:

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

Então, eu sei que você trabalha na base $ \ beta \ xi $, e sei qual número de base 7, qualquer dígito você escrever corresponde a.

Agora, se estivéssemos discutindo física e você estivesse me contando sobre constantes fundamentais (digamos) $ 60Z8 $, então preciso interpretar isso:

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

Então, começo multiplicando $ \ beta \ zeta \ times \ beta \ xi $ mas isso é coisa do ensino fundamental para mim, eu me lembro:

Tabela de multiplicação 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 $ \ beta \ zeta \ times \ beta \ xi $ sim:

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

então cheguei até aqui

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

Agora preciso realizar a adição usando o algoritmo que foi mencionado antes:

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

então

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

e continuando assim eu obtenho $$ [\! [60Z8] \!] = \ zeta \ delta \ xi \ gamma \ rho. $$

Em resumo: Se eu tenho minha própria concepção de número em termos de sequências de dígitos de $ q $ de base, então tenho uma maneira de interpretar seus números de $ b $ de base em meu próprio sistema, com base nas operações aritméticas fundamentais – que operam nativamente em base $ q $.

Comentários

• Bem, eram muitas linhas irregulares. Mas como eu faria o computador fazer isso?
• @Griffin, acho que você está fazendo essa pergunta (estranha) prematuramente. Você escolhe uma linguagem de programação e digita o algoritmo para adição e multiplicação em números de base q (representados como listas de dígitos) e, em seguida, define uma função para interpretar dígitos de base b em números de base q e interpretar números de base b em números de base q. Eu ‘ já expliquei tudo isso.
• O fato é que conheço o conceito que você está tentando retratar. Meu problema é que meu computador não pode ‘ usar suas linhas irregulares.
• Eu sei o que você explicou, mas colocá-lo em prática é muito mais difícil. Você vê que definir esses dígitos não é ‘ tão fácil.
• Além disso, por que você colocou o dígito alfa na posição mais significativa? Uma vez que 6 = & xi ;, Wouldn ‘ t 7 = & alpha; & alpha ;?

Esta é uma refatoração (Python 3) do código Andrej “s . Enquanto no código de Andrej os números são representados por uma lista de dígitos (escalares), nos códigos a seguir os números são representados por uma lista de símbolos arbitrários extraídos de uma string 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 uma conversão de valor para representação em uma base personalizada:

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

Para realizar uma conversão de representação (em uma base personalizada) para 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 uma conversão de base de uma base de custódia para outra:

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

Comentários

• Bem-vindo ao site e obrigado por sua contribuição. No entanto, produzir código-fonte bem otimizado não é ‘ o que este site realmente trata. O código de Andrej ‘ torna os conceitos claros, que é o que é necessário para sua resposta, mas melhorar o código além disso é uma questão de programação, e não de ciência .
• @DavidRicherby Concordo em parte, mas esta contribuição foi muito longa para um comentário e seu melhor lugar para estar é em algum lugar perto da resposta de Andrej ‘, foi ‘ por isso que o postei aqui. De qualquer forma, se você achar ‘ melhor, eu poderia convertê-lo em um comentário com um link para o código, mas não ‘ seria um excesso de purismo?
• Apesar de @David ‘ s ” purista do site ” objeções, achei sua resposta útil porque enfatiza o fato de que as bases envolvidas podem ser pensadas em termos mais abstratos como ” alfabetos ” de símbolos arbitrários de comprimentos variados – e não restritos ao intervalo usual de 2 a 36 caracteres. Na verdade, você poderia considerar fluxos de bytes como os ” dígitos ” de valores inteiros de base 256.

A operação fundamental da conversão de base é a toDigits() operação da resposta @AndrejBauer. Porém, para fazê-lo, não há necessidade de criar um número na representação interna dos números, que é basicamente uma conversão de e para a representação de base 2.Você pode fazer as operações necessárias na representação de base original.

Portanto, o primeiro passo é fazer a operação de divisão repetitiva do 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 a representação interna é composta por dígitos, deve-se fazer uma especificação especial função para testar zero

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

Eventualmente, é necessário fazer a operação modulo_div, que é na verdade a divisão padrão pela base de destino, conforme aprendemos na escola.

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 

apenas uma verificação de teste para verificar se o código está correto:

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] 

Comentários

• Obrigado por postar, mas observe que ‘ não somos um site de programação, então um grande bloco de código não é ‘ t apropriado como uma resposta aqui. Especialmente quando a pergunta diz explicitamente: ” Eu não ‘ não preciso do código, só preciso da matemática básica por trás dele. ”
• @DavidRicherby Tentei adicionar texto.
• Obrigado. E eu vejo que há ‘ uma grande quantidade de código nesta página, apesar do que eu disse!
• @David: FWIW, acho que isso responde ao OP A pergunta da ‘ s melhor, pois mostra como converter entre as duas bases sem primeiro converter a representação do original em alguma forma intermediária e depois convertê-la na base de destino.
• Boa tentativa, mas d ainda está na base 10, então você está extraindo uma porção menor de n, convertendo-a na base 10, convertendo-a na base desejada e coletando-a no resultado final.

Eu conheço uma maneira fácil de fazer a conversão de base que não requer um programa de computador. É definindo uma maneira de converter de qualquer base para a base 2 e vice-versa e, em seguida, converter de uma base para outra base, primeiro convertendo da primeira base para a base 2 e depois convertendo da base 2 para a outra base. 2 é tão fácil de multiplicar ou dividir por em qualquer base.

Para converter de qualquer base para a base 2, tudo que você precisa fazer é reconhecer que para qualquer número, se você pegar sua notação de base 2 e começar de 0 e, em seguida, para cada dígito na ordem da esquerda para a direita, dobre se esse dígito for zero e dobre do que adicionar 1 se esse dígito for 1, você obtém o próprio número. Agora, dado esse número em qualquer base, você pode dividir por 2 nessa base para obter um quociente e o resto. Se o resto for 1, o último dígito binário é 1 e se o resto for 0, o último dígito binário é 0. Divida por 2 novamente. Se o resto for 1, o penúltimo dígito é 1 e se o resto for 0, o penúltimo dígito é 0 e assim por diante até obter um quociente de 0.

Para converter da base 2 para qualquer base, tudo que você precisa fazer é nessa base, começar de 0, então para cada dígito binário indo da esquerda para a direita, dobre nessa base se o dígito for 0 e dobre então adicione 1 nessa base se esse dígito for 1.

Comentários

• 2 is so easy to multiply or divide by in any base. Eu não ‘ t veja isso para bases ímpares que são mais de um de qualquer potência de dois (11 e 13, para começar).

Você pode converter da base n para a base 10 sem qualquer conversão para alguma base intermediária.

Para converter da base n para a base 9, por exemplo, você pega o algoritmo de conversão para a base 10 e substitui “10” por “9”. O mesmo para qualquer outra base.