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

36

Eu estive olhando para a matemática por trás da conversão de qualquer base para qualquer base. Trata-se mais de confirmar meus resultados do que qualquer coisa. Encontrei o que parece ser minha resposta no mathforum.org, mas ainda não tenho certeza se estou certo. Eu tenho a conversão de uma base maior para uma base menor abaixo ok, porque é simplesmente multiplicar o primeiro dígito por base que você deseja adicionar a repetição do próximo dígito. Meu problema surge ao converter de uma base menor para uma base maior. Ao fazer isso, eles falam sobre como você precisa converter a base maior que você deseja na base menor que você possui. Um exemplo seria da base 4 para a base 6. Você precisa converter o número 6 na base 4, obtendo 12. Você então faz o mesmo que fazia ao converter de grande para pequeno. A dificuldade que tenho com isso é que parece que você precisa saber qual é o número na outra base. Então, eu precisaria saber o que 6 está na base 4. Isso cria um grande problema em minha mente, porque então eu precisaria de uma tabela. Alguém sabe uma maneira de fazer isso de uma maneira melhor.

Eu pensei que uma conversão de base ajudaria, mas não consigo encontrar nenhum que funcione. E pelo site que achei, parece que você pode converter da base para a base sem passar pela base 10, mas primeiro você precisa saber como converter o primeiro número da base para a base. Isso faz com que seja meio inútil.

Os comentaristas estão dizendo que preciso converter uma letra em um número. Se sim, eu já sei disso. Esse não é o meu problema, no entanto. Meu problema é que, para converter uma base grande em uma base pequena, preciso primeiro converter o número de base que tenho no número de base que desejo. Ao fazer isso, derroto o objetivo, porque, se tenho a capacidade de converter essas bases em outras, já resolvi o meu problema.

Edit: Eu descobri como converter de bases menores ou iguais a 10 em outras bases menores ou iguais a 10. Eu também posso ir de uma base maior que 10 para qualquer base que seja 10 ou menor. O problema começa ao converter de uma base maior que 10 para outra base maior que 10. Ou passar de uma base menor que 10 para uma base maior que 10. Não preciso de código, só preciso da matemática básica por trás disso. aplicado ao código.

Griffin
fonte
11
Esta questão está no tópico deste fórum?
11133 Andrej Bauer
2
O procedimento é trivial, desde que você possa fazer adição e multiplicação na base de destino. Se não puder, não acho possível.
Karolis Juodelė
9
Griffin deve primeiro ser informado do que muitos alunos precisam ouvir: os números existem sem serem representados em uma base . Então a resposta é clara: precisamos de algoritmos, um para converter uma representação de um número em uma determinada base para o número (isto é, algo que recebe ae stringretorna a int) e um algoritmo que pega um número e retorna sua representação em uma determinada base.
21313 Andrej Bauer
11
@AndrejBauer A questão é sobre CS: mesmo que não seja redigida dessa maneira, é uma pergunta sobre um algoritmo para converter entre representações numéricas. [Nota não relacionada: excluí vários comentários confusos. Griffin: edite sua pergunta para atualizá-la. Outros: por favor, leve-o para conversar .]
Gilles 'SO- stop be evil'
11
@Griffin já faz muito tempo desde a sua pergunta original. Espero que você tenha encontrado sua resposta. Nesse caso, talvez seja uma ótima idéia atualizar e aceitar uma resposta ou postar a sua. Enquanto isso, encontrei algumas idéias muito boas (falando sobre implementação em C ++) nos arquivos do Code Jam do Google. Algumas soluções para este problema são muito criativos code.google.com/codejam/contest/32003/dashboard
IsaacCisneros

Respostas:

45

Esta parece uma pergunta muito básica para mim, então com licença se eu lhe der um 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 em dígitos é uma coisa concreta, a saber, uma sequência de símbolos em um papel (ou uma sequência de bits na memória computacional ou uma sequência de sons que você produz quando comunica um número). O que o confunde é o fato de você 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 ser feita não é "como converter de uma base para outra", mas "como descobrir qual número é representado por uma determinada sequência de dígitos" e "como 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 em um número e outra para fazer o oposto. Nota: quando executamos a função, o Python obviamente imprimirá na tela o número obtido na base 10. Mas isso não significa que o computador esteja mantendo os números na base 10 (não é). É 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 estes:

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

Nota: nós fizemos não passar por base 10 representação! Convertemos a representação da base no número e, em seguida, o número na base c . O número não estava em nenhuma representação. (Na verdade, o computador tinha que representá-lo de alguma forma, e representava usando sinais elétricos e coisas estranhas que acontecem em chips, mas certamente esses não eram zeros e zeros).bc

Andrej Bauer
fonte
4
Isso não me convence 100%. De fato, 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 na base b 2 ; só pode converter seqüências representáveis ​​pela máquina de concreto. Python é charmosamente flexível; C não teria sido tão perdoador. É perfeitamente válido perguntar como converter seqüências arbitrárias de b 1 para b 2 ; no entanto, isto só é possível no tempo linear, excepto com certas combinações de bases (por exemplo, 2. <-> 16)b1 1b2b1 1b2
rici
11
É 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.
Andrej Bauer
2
Isto faz passar o número de base 10 através de representação, como os fromDigitsretornos do número na base 10.
apnorton
8
@ anorton: Não, definitivamente não . Python imprime o número na tela na representação de 10 dígitos da base, mas o número em si não é armazenado dessa maneira. O que estou tentando entender é que é irrelevante como os números são implementados no Python. Isso não importa. A única coisa que importa é que eles se comportem como números.
Andrej Bauer
3
Finalmente, uma solução geral para qualquer base e não se limitando a casos de uso específicos, bases inferiores a 36 ou instâncias em que você pode criar símbolos exclusivos suficientes.
J.Money
21

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

A definição é um número na base bxb significa que é uma sequência de dígitos < b .x<b

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

Agora, suponha que eu tenha crescido no planeta QUUX, onde todos são ensinados a trabalhar em por toda a vida, e encontro você que está acostumado a basear b . Então você me mostra um número, e o que eu faço? Eu preciso de uma maneira de interpretá-lo:qb

Definição Eu posso interpretar um número na base (Nota: b é um número na base q ) pela seguinte fórmulabbq

[[ϵ]]=0 0[[s¯d]]=[[s¯]]×b+d

onde denota a string vazia e ˉ s d indica uma string que termina no dígito d . Veja minha prova de que a adição acrescenta uma introdução a essa notação.ϵs¯dd

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

Tecla A chave para isso é que o e + eu tenho são funções que operam nos números base q . Estes são algoritmos simples definidos recursivamente nos números base q (sequências de dígitos).×+qq


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 base 13 (usando os símbolos ) e eu estou acostumado com a base 7 (que é muito mais sensível) usando os símbolos α β γ δ ρ ζ ξ .0123456789XYZαβγδρζξ

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

0 0α1 1β2γ3δ4ρ5ζ6ξ7βα8ββ9βγXβδYβρZβζ

βξ

60Z8

[[60Z8]]=ξ(βξ)3+α(βξ)2+βζ(βξ)+ββ

βζ×βξ

Tabela de multiplicação Quux

×βγδρζξββγδρζξγγρξβββδβζδδξβγβζγβγρρρβββζγγγξδδζζβδγβγξδρργξξβζγρδδργζββαβαγαδαραζαξα

βζ×βξ

βζ×βξξγρβζδβγγ

então eu cheguei tão longe

[[60Z8]]=ξ(βξ)3+α(βξ)2+βζ(βξ)+ββ=ξ(βξ)3+α(βξ)2+δβγ+ββ

Agora eu preciso executar a adição usando o algoritmo mencionado anteriormente:

δβγββδγδ

então

[[60Z8]]=ξ(βξ)3+α(βξ)2+βζ(βξ)+ββ=ξ(βξ)3+α(βξ)2+δβγ+ββ=ξ(βξ)3+α(βξ)2+δγδ

[[60Z8]]=ζδξγρ.

qbq

Lagarto discreto
fonte
11
Bem, isso foi um bom número de linhas onduladas. Como eu faria o computador fazer isso?
Griffin
11
@ 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 nos números da base q (representados como listas de dígitos), depois define uma função para interpretar os dígitos da base b nos números da base q e interpreta os números da base b nos números da base q. Eu expliquei tudo isso.
O fato é que eu conheço o conceito que você está tentando retratar. Meu problema é que meu computador não pode usar suas linhas onduladas.
Griffin
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.
Griffin
11
Além disso, por que você soltou o dígito alfa na posição mais significativa? Como 6 = & xi ;, não seria 7 = & alpha; & alpha ;?
Giovanni Botta 30/09
9

Esta é apenas uma refatoração (Python 3) do código de Andrej . No Andrej, os números de código são representados através de uma lista de dígitos (escalares), enquanto no seguinte, os números de código são representados através de uma lista de símbolos obtidos de uma sequência 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 executar uma conversão de valor em representação em uma base personalizada:

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

Para executar uma conversão de representação (em uma base personalizada) em 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 executar uma conversão básica de uma base custome para outra:

>>> b2b('1120','012','01')
'101010'
>>> b2b('100','01','0123456789')
'4'
>>> b2b('100','0123456789ABCDEF','01')
'100000000'
mmj
fonte
11
Bem-vindo ao site e obrigado por sua contribuição. No entanto, produzir código-fonte bem otimizado não é o que realmente interessa a este site. O código de Andrej torna os conceitos claros, 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 da computação .
experiência
11
@DavidRicherby Eu concordo parcialmente, mas essa contribuição foi longa demais para um comentário e seu melhor lugar para se estar é algo próximo da resposta de Andrej, por isso eu o publiquei aqui. Enfim, se você acha que é melhor eu poderia convertê-lo em um comentário com um link para o código, mas não seria um excesso de purismo?
mmj
1

A operação fundamental da conversão de base é a toDigits()operação da resposta @AndrejBauer. No entanto, para fazer isso, 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 da base 2. Você pode fazer as operações necessárias na representação base original.

Portanto, o primeiro passo é realizar operações repetitivas de divisão de módulos

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 é um dígito, é necessário criar uma função especificada para testar zero

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

Eventualmente, é preciso fazer a operação modulo_div, que na verdade é a divisão padrão por base de destino, como 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]
Xavier Combelle
fonte
Obrigado por postar, mas observe que não somos um site de codificação, portanto, um grande bloco de código não é apropriado como resposta aqui. Especialmente quando a pergunta diz explicitamente: "Não preciso de código, só preciso da matemática básica por trás disso".
David Richerby
@DavidRicherby Tentei adicionar texto.
Xavier Combelle
Obrigado. E vejo que há muito código nesta página, apesar do que eu disse!
David Richerby
0

Conheço uma maneira fácil de fazer a conversão básica 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, cobrindo 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 qualquer base.

Para converter de qualquer base para a base 2, tudo o que você precisa fazer é reconhecer que, para qualquer número, se você pegar a notação de base 2 e começar de 0 e, em seguida, para cada dígito, da esquerda para a direita, o dobro se esse dígito for zero e dobrar do que adicionar 1 se esse dígito for 1, você chega a esse número. Agora, considerando esse número em qualquer base, você pode dividir por 2 nessa base para obter um quociente e o restante. Se o restante for 1, o último dígito binário é 1 e se o restante for 0, o último dígito binário será 0. Divida por 2 novamente. Se o restante for 1, o segundo último dígito será 1 e se o restante for 0, o segundo último dígito será 0 e assim sucessivamente até você obter um quociente de 0.

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

Timothy
fonte
2 is so easy to multiply or divide by in any base. Não vejo isso para bases ímpares que são mais do que uma de qualquer potência de duas (11 e 13, para começar).
greybeard
0

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

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

gnasher729
fonte