Matematikken bag konvertering fra en hvilken som helst base til en hvilken som helst base uden at gå gennem base 10?

Dette forekommer mig et meget grundlæggende spørgsmål, så undskyld mig, hvis jeg forelæser dig lidt. Det vigtigste for dig at lære her er, at et tal ikke er dets cifferrepræsentation . Et tal er et abstrakt matematisk objekt, hvorimod dets cifferrepræsentation er en konkret ting, nemlig en sekvens af symboler på et papir (eller en sekvens af bits i beregningshukommelsen eller en sekvens af lyde, du laver, når du kommunikerer et nummer). Hvad der forvirrer dig er det faktum, at du aldrig ser et tal, men altid dets cifferrepræsentation. Så du ender med at tro, at tallet er repræsentationen.

Derfor er det rigtige spørgsmål at stille ikke ” hvordan konverterer jeg fra en base til en anden ” men snarere ” hvordan finder jeg ud af, hvilket nummer der er repræsenteret af en given række cifre ” og ” hvordan finder jeg cifferrepræsentationen af et givet tal “.

Så lad os producere to funktioner i Python, en til konvertering af en cifferrepræsentation til et tal og et andet til at gøre det modsatte. Bemærk: når vi kører funktionen vil Python naturligvis udskrive på skærmen det nummer, den fik i base 10. Men det betyder ikke at computeren holder tal i basen 10 (det er ikke “t). Det er irrelevant hvordan computeren repræsenterer tallene.

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 

Lad os teste disse:

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

Bevæbnet med konverteringsfunktioner løses dit problem let:

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

En test :

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

Bemærk: vi gjorde ikke gennemgå base 10-repræsentation! Vi konverterede basen $ b $ repræsentation til antallet og derefter tallet til basen $ c $ . Antallet var ikke i nogen repræsentation. (Faktisk var det computeren skulle repræsentere det på en eller anden måde, og det repræsenterede det ved hjælp af elektriske signaler og funky ting der sker i chips, men bestemt de w der er ikke 0 “og 1” s.)

Kommentarer

• Dette overbeviser ikke ‘ t mig 100%. Faktisk konverterede du nummeret til en vis repræsentation (selvom du kan hævde ikke at vide hvad det er), fordi computere ikke er platoniske matematikere, og din algoritme kan ikke konvertere en vilkårlig rækkefølge af cifre i base $ b_1 $ til base $ b_2 $; det kan kun konvertere sekvenser, der kan repræsenteres af betonmaskinen. Python er charmerende fleksibel; C ville ikke have været så tilgivende. Det er helt gyldigt at spørge, hvordan man konverterer vilkårlige strenge fra $ b_1 $ til $ b_2 $; dette er dog kun muligt i lineær tid undtagen med visse basekombinationer (f.eks. 2 < – > 16)
• Det er gyldigt at stille spørgsmålet, men for at finde det rigtige svar er det bedst at være opmærksom på det faktum, at tal er abstrakte enheder.
• Dette passerer tallet gennem base 10-repræsentation, da fromDigits returnerer tallet i base 10.
• @anorton: Nej, det gør det bestemt ikke . Python udskriver nummeret på skærmen i en 10-cifret repræsentation, men selve nummeret er ikke gemt på den måde. Hvad jeg prøver at komme igennem, er, at det er irrelevant , hvordan tallene implementeres inde i Python. Det er lige meget. Det eneste der betyder noget er, at de opfører sig som tal.
• Endelig en generel løsning til enhver base og ikke begrænset til bestemte brugssager, baser mindre end 36 eller tilfælde, hvor du kan komme med nok unikke symboler .

Jeg tror, at den bedste måde at forstå dette er i diskussion med en fremmed (mindst som en analogi).

Definition $ x $ er et tal i basis $ b $ betyder, at $ x $ er en række cifre $ < b $.

Eksempler Strengen af cifre 10010011011 er et tal i base 2, strengen 68416841531 er et tal i base 10, BADCAFE er et tal i base 16.

Nu Antag, at jeg voksede op på planeten QUUX, hvor alle læres at arbejde i $ q $ hele deres liv, og jeg møder dig, der er vant til at basere $ b $. Så du viser mig et nummer, og hvad skal jeg gøre? Jeg har brug for en måde at fortolke det på:

Definition Jeg kan fortolke et tal i base $ b $ (Bemærk: $ b $ er et tal i base $ q $) med følgende formel

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

hvor $ \ epsilon $ angiver den tomme streng, og $ \ bar sd $ angiver en streng, der slutter med cifret $ d $. Se mit bevis på, at tilføjelse tilføjer for en introduktion til denne notation.

Så hvad er der sket her? Du har givet mig et nummer i base $ b $, og jeg har fortolket det til base $ q $ uden nogen underlig filosofi om hvad tal virkelig er.

Tast Nøglen til dette er, at $ \ times $ og $ + $ I har funktioner, der fungerer på basis $ q $ numre. Disse er enkle algoritmer defineret rekursivt på base $ q $ tal (strenge af cifre).

Dette kan virke lidt abstrakt, da jeg har brugt variabler snarere end faktiske tal igennem. Så lad os antage, at du er en basis 13-skabning (ved hjælp af symboler $ 0123456789XYZ $), og jeg er bruges til at basere 7 (hvilket er meget mere fornuftigt) ved hjælp af symboler $ \ alpha \ beta \ gamma \ delta \ rho \ zeta \ xi $.

Så jeg har set dit alfabet og tabuleret det således:

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

Så jeg ved, at du arbejder i base $ \ beta \ xi $, og jeg ved, hvilken base 7 nummererer et ciffer, du skriv svarer til.

Hvis vi nu diskuterede fysik, og du fortalte mig om grundlæggende konstanter (siger) $ 60Z8 $, så jeg skal fortolke dette:

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

Så jeg begynder med at gange $ \ beta \ zeta \ times \ beta \ xi $ men dette er grundskoleartikler for mig, jeg husker:

Quux-multiplikationstabel

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

så for at finde $ \ beta \ zeta \ times \ beta \ xi $ jeg gør:

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

så jeg er kommet så langt

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

Nu skal jeg udføre tilføjelsen ved hjælp af algoritmen, som blev nævnt før:

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

så

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

og fortsætter på denne måde får jeg $$ [\! [60Z8] \!] = \ zeta \ delta \ xi \ gamma \ rho. $$

I resume: Hvis jeg har min egen opfattelse af antal i form af base $ q $ strenge af cifre, så har jeg måde at fortolke dine tal fra base $ b $ ind i mit eget system, baseret på de grundlæggende aritmetiske operationer – som fungerer indbygget i base $ q $.

Kommentarer

• Nå, det var en hel del snurrende linjer. Hvordan kunne jeg få computeren til at gøre det dog?
• @Griffin, jeg tror du stiller det (mærkelige) spørgsmål for tidligt. Du vælger et programmeringssprog og skriver algoritmen til tilføjelse og multiplikation på basis q tal (repræsenteret som lister over cifre), og definer derefter en funktion til at fortolke base b cifre til base q tal og fortolke base b tal til base q tal. Jeg ‘ har forklaret alt dette.
• Sagen er, at jeg kender konceptet, du prøver at skildre. Mit problem er, at min computer ikke kan ‘ ikke bruge dine snoede linjer.
• Jeg ved hvad du forklarede, men det er langt sværere at omsætte det i praksis. Du ser, at definere disse cifre ikke er ‘ t så let.
• Også hvorfor droppede du alfabetallet i den mest betydningsfulde position? Da 6 = & xi ;, Ville ‘ t 7 = & alpha; & alpha ;?

Dette er en refactoring (Python 3) af Andrej “s -kode. Mens i Andrej er kodetal repræsenteret gennem en liste med cifre (skalarer), i de følgende kodetal er repræsenteret gennem en liste med vilkårlige symboler taget fra en brugerdefineret streng:

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) 

For at udføre en konvertering fra værdi til repræsentation i en brugerdefineret base:

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

For at udføre en konvertering fra repræsentation (i en brugerdefineret base) til værdi :

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

For at udføre en basekonvertering fra en base til en anden:

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

Kommentarer

• Velkommen til siden og tak for dit bidrag. At producere veloptimeret kildekode er dog ikke ‘ t, hvad dette websted egentlig handler om. Andrej ‘ s kode gør begreberne klare, hvilket er hvad der er nødvendigt for hans svar, men forbedring af koden ud over det er et spørgsmål om programmering snarere end computer science .
• @ DavidRicherby Jeg er delvis enig, men dette bidrag var for længe til en kommentar, og det bedste sted at være er et sted nær Andrej ‘ s svar, at ‘ hvorfor jeg sendte det her. Alligevel, hvis du synes, det ‘ er bedre, kunne jeg konvertere det til en kommentar med et link til koden, men ville det ikke være ‘ et overskud af purisme?
• På trods af @David ‘ s ” site-purist ” indvendinger, jeg fandt dit svar nyttigt, fordi det understreger det faktum, at de involverede baser kan betragtes i mere abstrakte termer som ” alfabeter ” af vilkårlige symboler af varierende længde – og ikke begrænset til det sædvanlige interval på 2-36 tegn. Du kan faktisk overveje strømme af bytes som ” cifre ” af basis 256 heltalværdier.

Grundlæggende funktion af basekonvertering er toDigits() operation af @AndrejBauer svar. For at gøre det er der imidlertid ikke behov for at oprette et nummer i den interne repræsentation af tallene, hvilket grundlæggende er en konvertering fra og til base 2-repræsentation.Du kan foretage de nødvendige operationer i den oprindelige basisrepræsentation.

Så det første trin er at udføre gentagne modulopdelingsoperationer

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 

Da den interne repræsentation er cifre, skal man lave en speciliseret funktion til test af nul

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

Til sidst er man nødt til at foretage modulo_div-operationen, som faktisk er standardinddelingen efter destinationsbase, som vi lærte i skolen.

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 

bare en testkontrol for at kontrollere, at koden er korrekt:

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] 

Kommentarer

• Tak for indlægget, men vær opmærksom på, at vi ‘ ikke er et kodningswebsted, så en stor blok kode er ikke ‘ t passende som svar her. Især når spørgsmålet udtrykkeligt siger, ” Jeg behøver ‘ ikke brug for kode, jeg har bare brug for den grundlæggende matematik bag den. ”
• @ DavidRicherby Jeg prøvede at tilføje tekst.
• Tak. Og jeg ser der ‘ en masse koder på denne side, på trods af hvad jeg sagde!
• @ David: FWIW, jeg tror, det svarer på OP ‘ s spørgsmål bedst, da det viser, hvordan man konverterer mellem de to baser uden først at konvertere repræsentationen af originalen til en mellemform, og derefter konvertere den til destinationsbasen.
• Godt forsøg, men d er stadig i base 10, så du udtrækker faktisk en mindre del af n, der konverterer den til base 10, og konverterer den derefter til den ønskede base og samler dem til det endelige resultat.

Jeg kender en nem måde at lave basiskonvertering på, der ikke kræver et computerprogram. Det er ved at definere en måde at konvertere fra en hvilken som helst base til base 2 og omvendt og derefter skjule fra en base til en anden base ved først at konvertere fra den første base til base 2 og derefter konvertere fra base 2 til den anden base. 2 er så let at multiplicere eller dele med i en hvilken som helst base.

For at konvertere fra en hvilken som helst base til base 2 er alt, hvad du skal gøre, at genkende det for ethvert tal, hvis du tager dets base 2-notation og starter fra 0 og derefter for hvert ciffer i rækkefølge fra venstre til højre dobbelt hvis dette ciffer er nul og dobbelt end tilføj 1 hvis dette ciffer er 1, kommer du til selve tallet. Nu givet dette tal i enhver base, kan du dele med 2 i denne base for at få en kvotient og en rest. Hvis resten er 1, er det sidste binære ciffer 1, og hvis resten er 0, er det sidste binære ciffer 0. Divider med 2 igen. Hvis resten er 1, er det næstsidste ciffer 1, og hvis resten er 0, er det næstsidste ciffer 0 og så videre, indtil du får en kvotient på 0.

At konvertere fra base 2 til en hvilken som helst base, alt hvad du skal gøre er i den base, start fra 0, så for hvert binært ciffer, der går fra venstre til højre, dobbelt i denne base, hvis cifret er 0 og dobbelt så tilføj 1 i den base, hvis dette ciffer er 1.

Kommentarer

• 2 is so easy to multiply or divide by in any base. Jeg don ‘ t se det for ulige baser, der er mere end en fra en hvilken som helst styrke på to (11 og 13, til at begynde med).