La matematica dietro la conversione da qualsiasi base a qualsiasi base senza passare per la base 10?

Questa mi sembra una domanda molto semplice, quindi scusami se ti faccio una piccola predica. Il punto più importante da imparare qui è che un numero non è la sua rappresentazione in cifre . Un numero è un oggetto matematico astratto, mentre la sua rappresentazione numerica è una cosa concreta, vale a dire una sequenza di simboli su un foglio (o una sequenza di bit nella memoria di calcolo, o una sequenza di suoni che si emette quando si comunica un numero). Ciò che ti confonde è il fatto che non vedi un numero ma sempre la sua rappresentazione in cifre. Quindi finisci per pensare che il numero sia la rappresentazione.

Pertanto, la domanda corretta da porre non è ” come faccio a convertire da una base allaltra ” ma piuttosto ” come faccio a sapere quale numero è rappresentato da una data stringa di cifre ” e ” come faccio a trovare la rappresentazione numerica di un dato numero “.

Quindi produciamo due funzioni in Python, una per convertire una rappresentazione numerica in un numero e un altro per fare il contrario. Nota: quando eseguiamo la funzione Python ovviamente stamperà sullo schermo il numero che ha ottenuto in base 10. Ma questo non significa che il computer sta mantenendo i numeri in base 10 (non è “t). È irrilevante il modo in cui il computer rappresenta i numeri.

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 

Testiamoli:

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

Grazie alle funzioni di conversione, il tuo problema si risolve 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) 

Un test :

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

Nota: labbiamo fatto non passare attraverso la rappresentazione in base 10! Abbiamo convertito la rappresentazione $ b $ di base nel numero, quindi il numero in base $ c $ . Il numero non era in nessuna rappresentazione. (In realtà lo era, il computer doveva rappresentarlo in qualche modo, e lo rappresentava usando segnali elettrici e funky cose che accadono nelle patatine, ma certamente quelle w non sono 0 “se 1”.)

Commenti

• Questo ‘ non convince io al 100%. In effetti, hai convertito il numero in una rappresentazione (sebbene tu possa affermare di non sapere cosa sia) perché i computer non sono matematici platonici e il tuo algoritmo non può convertire una sequenza arbitraria di cifre in base $ b_1 $ in base $ b_2 $; può convertire solo sequenze rappresentabili dalla macchina concreta. Python è incredibilmente flessibile; C non sarebbe stato così indulgente. È perfettamente valido chiedere come convertire stringhe arbitrarie da $ b_1 $ a $ b_2 $; tuttavia, questo è possibile solo in tempo lineare tranne con alcune combinazioni di base (ad es. 2 < – > 16)
• È valido porre la domanda, ma per trovare la risposta giusta è meglio essere consapevoli del fatto che i numeri sono entità astratte.
• Questo fa il numero attraverso la rappresentazione in base 10, poiché fromDigits restituisce il numero in base 10.
• @anorton: No, decisamente non . Python stampa il numero sullo schermo in una rappresentazione di 10 cifre in base, ma il numero stesso non viene memorizzato in questo modo. Quello che sto cercando di capire è che è irrilevante il modo in cui i numeri vengono implementati in Python. Non importa. Lunica cosa che conta è che si comportino come numeri.
• Finalmente una soluzione generale per qualsiasi base e non limitata a casi duso particolari, basi inferiori a 36 o istanze in cui puoi trovare un numero sufficiente di simboli univoci .

Penso che il modo migliore per capire questo sia discutere con un alieno (almeno come unanalogia).

Definizione $ x $ è un numero in base $ b $ significa che $ x $ è una stringa di cifre $ < b $.

Esempi La stringa di cifre 10010011011 è un numero in base 2, la stringa 68416841531 è un numero in base 10, BADCAFE è un numero in base 16.

Ora Supponiamo che io sia cresciuto sul pianeta QUUX dove a tutti viene insegnato a lavorare in $ q $ per tutta la vita e che io conosca te che è abituato a basare $ b $. Quindi mi mostri un numero e cosa faccio? Ho bisogno di un modo per interpretarlo:

Definizione So interpretare un numero in base $ b $ (Nota: $ b $ è un numero in base $ q $) con la seguente formula

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

dove $ \ epsilon $ denota la stringa vuota e $ \ bar sd $ denota una stringa che termina con la cifra $ d $. Vedi la mia prova che laggiunta aggiunge per unintroduzione a questa notazione.

Allora che cosa è successo qui? Mi hai dato un numero in base $ b $ e lho interpretato in base $ q $ senza alcuna strana filosofia su cosa siano veramente i numeri.

Chiave La chiave è che $ \ times $ e $ + $ ho sono funzioni che operano su $ q $ numeri di base. Questi sono semplici algoritmi definiti ricorsivamente su $ q $ numeri (stringhe di cifre).

Questo può sembrare un po astratto dato che ho sempre utilizzato variabili anziché numeri reali. Supponiamo quindi che tu sia una creatura di base 13 (usando i simboli $ 0123456789XYZ $) e io usato in base 7 (che è molto più sensato) usando i simboli $ \ alpha \ beta \ gamma \ delta \ rho \ zeta \ xi $.

Quindi ho visto il tuo alfabeto e lho tabulato così:

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

Quindi so che lavori in base $ \ beta \ xi $, e so quale numero in base 7 qualsiasi cifra tu write corrisponde a.

Ora, se stessimo discutendo di fisica e tu mi parlassi delle costanti fondamentali (diciamo) $ 60Z8 $, quindi ho bisogno di interpretare questo:

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

Quindi inizio moltiplicando $ \ beta \ zeta \ times \ beta \ xi $ ma questa è roba da scuola elementare per me, ricordo:

Tabella di moltiplicazione di 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} $$

quindi per trovare $ \ beta \ zeta \ times \ beta \ xi $ faccio:

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

quindi sono arrivato fin qui

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

Ora devo eseguire laddizione usando lalgoritmo che è stato menzionato prima:

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

quindi

$$ \ 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 in questo modo ottengo $$ [\! [60Z8] \!] = \ zeta \ delta \ xi \ gamma \ rho. $$

In riepilogo: se ho la mia concezione del numero in termini di stringhe di cifre di base $ q $, allora ho modo di interpretare i tuoi numeri dalla base $ b $ nel mio sistema, sulla base delle operazioni aritmetiche fondamentali – che operano in modo nativo in base $ q $.

Commenti

• Beh, quella era una buona dose di linee ondulate. Come potrei fare in modo che il computer lo faccia?
• @Griffin, penso che tu stia facendo quella (strana) domanda prematuramente. Scegli un linguaggio di programmazione e digita lalgoritmo per laddizione e la moltiplicazione sui numeri in base q (rappresentati come elenchi di cifre), quindi definisci una funzione per interpretare le cifre in base b in numeri in base q e interpretare i numeri in base b in numeri in base q. ‘ ho spiegato tutto questo.
• Il fatto è che conosco il concetto che stai cercando di rappresentare. Il mio problema è che il mio computer non può ‘ usare le tue linee ondulate.
• So cosa hai spiegato ma metterlo in pratica è molto più difficile. Come vedi, definire queste cifre non è ‘ così facile.
• Inoltre, perché hai lasciato cadere la cifra alfa nella posizione più significativa? Poiché 6 = & xi ;, ‘ t 7 = & alpha; & alpha ;?

Questo è un refactoring (Python 3) del codice Andrej “. Mentre in Andrej i numeri di codice sono rappresentati attraverso un elenco di cifre (scalari), nei seguenti numeri di codice sono rappresentati tramite un elenco di simboli arbitrari presi da una stringa personalizzata:

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) 

Per eseguire una conversione da valore a rappresentazione in una base personalizzata:

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

Per eseguire una conversione da rappresentazione (in una base personalizzata) a valore :

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

Per eseguire una conversione di base da una base personalizzata a unaltra:

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

Commenti

• Benvenuto nel sito e grazie per il tuo contributo. Tuttavia, produrre un codice sorgente ben ottimizzato non è ‘ ciò di cui si occupa veramente questo sito. Il codice di Andrej ‘ chiarisce i concetti, che è ciò che è necessario per la sua risposta, ma migliorare il codice oltre a questo è una questione di programmazione, piuttosto che di scienza .
• @DavidRicherby Sono in parte daccordo, ma questo contributo era troppo lungo per un commento e il suo posto migliore è da qualche parte vicino alla risposta di Andrej ‘, è per questo ‘ che lho pubblicato qui. Ad ogni modo, se pensi che ‘ sia meglio potrei convertirlo in un commento con un link al codice, ma ‘ non lo sarebbe un eccesso di purismo?
• Nonostante @David ‘ s ” site-purist ” obiezioni, ho trovato la tua risposta utile perché sottolinea il fatto che le basi coinvolte possono essere pensate in termini più astratti come ” alfabeti ” di simboli arbitrari di varie lunghezze – e non limitati al normale intervallo di 2-36 caratteri. Potresti infatti considerare flussi di byte come le ” cifre ” di 256 valori interi di base.

Loperazione fondamentale della conversione di base è loperazione toDigits() di @AndrejBauer answer. Tuttavia, per realizzarlo non è necessario creare un numero nella rappresentazione interna dei numeri, che è fondamentalmente una conversione da e verso la rappresentazione in base 2.È possibile eseguire le operazioni necessarie nella rappresentazione di base originale.

Quindi il primo passo è eseguire unoperazione di divisione modulo ripetitiva

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 

Poiché la rappresentazione interna è composta da cifre, si deve fare una specifica funzione per testare zero

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

Alla fine si deve eseguire loperazione modulo_div che in realtà è la divisione standard per base di destinazione come abbiamo imparato a scuola.

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 un controllo di prova per verificare che il codice sia corretto:

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] 

Commenti

• Grazie per la pubblicazione, ma tieni presente che ‘ non siamo un sito di codifica, quindi un grande blocco di codice non è ‘ t appropriato come risposta qui. Soprattutto quando la domanda dice esplicitamente, ” Non ‘ non ho bisogno di codice, ho solo bisogno della matematica di base dietro di esso. ”
• @DavidRicherby Ho provato ad aggiungere del testo.
• Grazie. E vedo ‘ un sacco di codice su questa pagina, nonostante quello che ho detto!
• @David: FWIW, penso che questo risponda allOP ‘ è la domanda migliore in quanto mostra come convertire tra le due basi senza prima convertire la rappresentazione delloriginale in una forma intermedia e poi convertirla nella base di destinazione.
• Bel tentativo ma d è ancora in base 10, quindi in effetti stai estraendo una porzione più piccola di n convertendola in base 10, quindi convertendola nella base desiderata e raccogliendola nel risultato finale.

Conosco un modo semplice per eseguire la conversione di base che non richiede un programma per computer. È definendo un modo per convertire da qualsiasi base a base 2 e viceversa e quindi convertire da una base a unaltra base convertendo prima dalla prima base alla base 2 quindi convertendo dalla base 2 allaltra base. 2 è così facile da moltiplicare o dividere per in qualsiasi base.

Per convertire da qualsiasi base a base 2, tutto ciò che devi fare è riconoscere che per qualsiasi numero, se prendi la sua notazione in base 2 e inizia da 0 e poi per ogni cifra in ordine da sinistra a destra doppia se quella cifra è zero e doppia di aggiungere 1 se quella cifra è 1, si arriva a quel numero stesso. Ora dato quel numero in qualsiasi base, puoi dividere per 2 in quella base per ottenere un quoziente e un resto. Se il resto è 1, lultima cifra binaria è 1 e se il resto è 0, lultima cifra binaria è 0. Dividi di nuovo per 2. Se il resto è 1, la penultima cifra è 1 e se il resto è 0, la penultima cifra è 0 e così via fino a ottenere un quoziente di 0.

Per convertire da base 2 a qualsiasi base, tutto quello che devi fare è in quella base, iniziare da 0, quindi per ogni cifra binaria che va da sinistra a destra, raddoppia in quella base se quella cifra è 0 e raddoppia quindi aggiungi 1 in quella base se quella cifra è 1.

Commenti

• 2 is so easy to multiply or divide by in any base. Non ‘ t osservalo per basi dispari che sono più di una da qualsiasi potenza di due (11 e 13, per cominciare).

Puoi convertire da base n a base 10 senza alcuna conversione in base intermedia.

Per convertire da base n a base 9, ad esempio, prendi lalgoritmo per la conversione in base 10 e sostituisci “10” con “9”. Lo stesso per qualsiasi altra base.