Matematikken bak konvertering fra hvilken som helst base til hvilken som helst base uten å gå gjennom base 10?

Dette virker som et veldig grunnleggende spørsmål for meg, så unnskyld meg hvis jeg foreleser litt. Det viktigste for deg å lære her er at et tall ikke er dets sifferrepresentasjon . Et tall er et abstrakt matematisk objekt, mens dets sifferrepresentasjon er en konkret ting, nemlig en sekvens av symboler på et papir (eller en sekvens av biter i beregningsminnet, eller en sekvens av lyder som du lager når du kommuniserer et tall). Det som forvirrer deg er det faktum at du aldri ser et tall, men alltid dets sifferrepresentasjon. Så du ender opp med å tenke at tallet er representasjonen.

Derfor er det riktige spørsmålet ikke å stille » hvordan konverterer jeg fra en base til en annen » men heller » hvordan finner jeg ut hvilket tall som er representert med en gitt streng med sifre » og » hvordan finner jeg sifferrepresentasjonen av et gitt tall «.

Så la oss produsere to funksjoner i Python, en for å konvertere en sifferrepresentasjon til et tall, og et annet for å gjøre det motsatte. Merk: når vi kjører funksjonen vil Python selvfølgelig skrive ut på skjermen tallet det fikk i base 10. Men dette betyr ikke at datamaskinen holder tallene i basen 10 (det er ikke «t). Det er irrelevant hvordan datamaskinen representerer 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 

La oss 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æpnet med konverteringsfunksjoner, løses problemet ditt enkelt:

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] 

Merk: vi gjorde ikke gå gjennom base 10-representasjon! Vi konverterte basen $ b $ representasjon til tallet, og deretter tallet til basen $ c $ . Antallet var ikke i noen representasjon. (Egentlig var det datamaskinen måtte representere det på en eller annen måte, og det representerte det ved hjelp av elektriske signaler og funky ting som skjer i sjetonger, men absolutt de som er ikke 0 «og 1» s.)

Kommentarer

• Dette overbeviser ikke ‘ t meg 100%. Faktisk konverterte du nummeret til en eller annen representasjon (selv om du kan hevde at du ikke vet hva det er) fordi datamaskiner ikke er platoniske matematikere og algoritmen din ikke kan konvertere en vilkårlig sekvens av sifre i base $ b_1 $ til base $ b_2 $; den kan bare konvertere sekvenser som kan representeres av betongmaskinen. Python er sjarmerende fleksibel; C ville ikke ha vært så tilgivende. Det er helt gyldig å spørre hvordan man konverterer vilkårlige strenger fra $ b_1 $ til $ b_2 $; dette er imidlertid bare mulig i lineær tid bortsett fra med visse basekombinasjoner (f.eks. 2 < – > 16)
• Det er gyldig å stille spørsmålet, men for å finne riktig svar er det best å være klar over det faktum at tall er abstrakte enheter.
• Dette passerer tallet gjennom base 10-representasjon, da fromDigits returnerer tallet i base 10.
• @anorton: Nei, absolutt gjør det ikke . Python skriver ut tallet på skjermen i base 10-sifret representasjon, men selve nummeret er ikke lagret på den måten. Det jeg prøver å komme over er at det er irrelevant hvordan tallene implementeres inne i Python. Det betyr ikke noe. Det eneste som betyr noe er at de oppfører seg som tall.
• Endelig en generell løsning for enhver base og ikke begrenset til spesielle brukssaker, baser mindre enn 36, eller tilfeller der du kan komme med nok unike symboler .

Jeg tror den beste måten å forstå dette på er i diskusjon med en fremmed (minst som en analogi).

Definisjon $ x $ er et tall i basen $ b $ betyr at $ x $ er en streng med sifre $ < b $.

Eksempler Sifferstrengen 10010011011 er et tall i base 2, strengen 68416841531 er et tall i base 10, BADCAFE er et tall i base 16.

Nå Anta at jeg vokste opp på planeten QUUX hvor alle blir lært å jobbe i $ q $ hele livet, og jeg møter deg som er vant til å basere $ b $. Så du viser meg et nummer, og hva gjør jeg? Jeg trenger en måte å tolke det på:

Definisjon Jeg kan tolke et tall i base $ b $ (Merk: $ b $ er et tall i base $ q $) med følgende formel

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

hvor $ \ epsilon $ betegner den tomme strengen, og $ \ bar sd $ betegner en streng som slutter på sifferet $ d $. Se mitt bevis på at tillegg legger til for en introduksjon til denne notasjonen.

Så hva skjedde her? Du har gitt meg et nummer i base $ b $ og jeg har tolket det til base $ q $ uten noen merkelig filosofi om hva tall virkelig er.

Tast Nøkkelen til dette er at $ \ times $ og $ + $ jeg har er funksjoner som fungerer på basis $ q $ tall. Dette er enkle algoritmer definert rekursivt på base $ q $ tall (strenger av sifre).

Dette kan virke litt abstrakt siden jeg har brukt variabler i stedet for faktiske tall hele tiden. Så la oss anta at du er en base 13 skapning (ved hjelp av symbolene $ 0123456789XYZ $) og jeg er pleide å basere 7 (som er mye mer fornuftig) ved å bruke symbolene $ \ alpha \ beta \ gamma \ delta \ rho \ zeta \ xi $.

Så jeg har sett alfabetet ditt og tabellert det slik:

$$ \ 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 vet at du jobber i base $ \ beta \ xi $, og jeg vet hvilken base 7 som nummerer et siffer du skriv tilsvarer.

Hvis vi nå diskuterte fysikk og du fortalte meg om grunnleggende konstanter (si) $ 60Z8 $ så jeg må tolke dette:

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

Så jeg begynner med å multiplisere $ \ beta \ zeta \ times \ beta \ xi $ men dette er grunnskole ting for meg, husker jeg:

Quux multiplikasjonstabell

$$ \ 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 å finne $ \ beta \ zeta \ times \ beta \ xi $ jeg gjø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 har 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} $$

Nå må jeg utføre tillegget ved hjelp av algoritmen som ble nevnt før:

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

so

$$ \ 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 fortsetter på denne måten får jeg $$ [\! [60Z8] \!] = \ zeta \ delta \ xi \ gamma \ rho. $$

I sammendrag: Hvis jeg har min egen oppfatning av antall når det gjelder basis $ q $ strenger av sifre, så har jeg måte å tolke tallene dine fra base $ b $ inn i mitt eget system, basert på de grunnleggende aritmetiske operasjonene – som fungerer naturlig i base $ q $.

Kommentarer

• Vel, det var en god del kvisete linjer. Hvordan skulle jeg få datamaskinen til å gjøre det skjønt?
• @Griffin, jeg tror du stiller det (rare) spørsmålet for tidlig. Du velger et programmeringsspråk og skriver ut algoritmen for addisjon og multiplikasjon på q-basetall (representert som lister over sifre), og definerer deretter en funksjon for å tolke base b-sifre til base q-tall og tolke base b-tall i base q-tall. Jeg ‘ har forklart alt dette.
• Tingen er at jeg kjenner konseptet du prøver å skildre. Problemet mitt er at datamaskinen min ikke kan ‘ ikke bruke de svirrende linjene dine.
• Jeg vet hva du forklarte, men det er mye vanskeligere å sette det i praksis. Du ser å definere disse sifrene ikke ‘ t så enkelt.
• Også hvorfor droppet du alfasifret i den mest betydningsfulle posisjonen? Siden 6 = & xi ;, Ville ‘ t 7 = & alpha; & alpha ;?

Dette er en refactoring (Python 3) av Andrej «s -kode. Mens i Andrej er kodenumre representert gjennom en liste med sifre (skalarer), i de følgende kodenumrene er representert gjennom en liste med vilkårlige symboler hentet fra en tilpasset 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) 

Slik utfører du en konvertering fra verdi til representasjon i en tilpasset base:

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

For å utføre en konvertering fra representasjon (i en tilpasset base) til verdi :

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

Slik utfører du en basekonvertering fra en egen base til en annen:

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

Kommentarer

• Velkommen til siden og takk for ditt bidrag. Å produsere godt optimalisert kildekode er imidlertid ikke ‘ t hva dette nettstedet egentlig handler om. Andrej ‘ s kode gjør begrepene klare, som er det som trengs for svaret hans, men å forbedre koden utover det er et spørsmål om programmering, i stedet for datalogi > i>.
• @ DavidRicherby Jeg er delvis enig, men dette bidraget var for langt til en kommentar, og det beste stedet å være er et sted nær Andrej ‘ s svar, at ‘ hvorfor jeg la det ut her. Uansett hvis du synes det ‘ er bedre, kunne jeg konvertere det til en kommentar med en lenke til koden, men ville ikke ‘ t være det et overskudd av purisme?
• Til tross for @David ‘ s » site-purist » innvendinger, jeg fant svaret ditt nyttig fordi det understreker det faktum at basene som er involvert kan tenkes mer abstrakte som » alfabeter » av vilkårlige symboler av varierende lengde – og ikke begrenset til det vanlige området på 2-36 tegn. Du kan faktisk vurdere strømmer av byte som » sifre » av 256 256 heltallverdier.

Grunnleggende drift av basiskonvertering er toDigits() -operasjonen til @AndrejBauer-svaret. For å gjøre det er det imidlertid ikke nødvendig å lage et tall i den interne representasjonen av tallene, som i utgangspunktet er en konvertering fra og til base 2-representasjon.Du kan utføre de nødvendige operasjonene i den opprinnelige basisrepresentasjonen.

Så det første trinnet er å utføre repetitiv modulo-delingsoperasjon

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 

Ettersom den interne representasjonen er sifre, må man lage en spesifikasjon funksjon for testing av null

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

Til slutt må man gjøre modulo_div-operasjonen som faktisk er standardinndelingen etter destinasjonsbase slik vi lærte på 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 testkontroll for å bekrefte at koden er riktig:

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

• Takk for innlegget, men vær oppmerksom på at vi ‘ ikke er et kodingssted, så en stor blokk med kode er ikke ‘ t passende som svar her. Spesielt når spørsmålet eksplisitt sier, » Jeg trenger ikke ‘ t trenger kode, jeg trenger bare grunnleggende matematikk bak den. »
• @ DavidRicherby Jeg prøvde å legge til tekst.
• Takk. Og jeg ser der ‘ en hel masse kode på denne siden, til tross for det jeg sa!
• @ David: FWIW, jeg tror dette svarer på OP ‘ spørsmålet best, da det viser hvordan du konverterer mellom de to basene uten først å konvertere representasjonen av originalen til en mellomform, og deretter konvertere den til destinasjonsbasen.
• Fint forsøk, men d er fremdeles i base 10, så du trekker faktisk ut en mindre del av n og konverterer den til base 10, og konverterer den deretter til ønsket base og samler dem inn i det endelige resultatet.

Jeg vet en enkel måte å gjøre basekonvertering som ikke krever et dataprogram. Det er ved å definere en måte å konvertere fra hvilken som helst base til base 2 og omvendt og deretter skjule fra en base til en annen base ved først å konvertere fra den første basen til base 2 og deretter konvertere fra base 2 til den andre basen. 2 er så lett å multiplisere eller dele med i en hvilken som helst base.

For å konvertere fra en hvilken som helst base til base 2, er alt du trenger å gjøre å gjenkjenne det for et hvilket som helst tall, hvis du tar base 2-notasjonen og starter fra 0 og deretter for hvert siffer i rekkefølge fra venstre til høyre dobbelt hvis det tallet er null og dobbelt enn å legge til 1 hvis tallet er 1, kommer du til selve tallet. Nå gitt tallet i en hvilken som helst base, kan du dele med 2 i den basen for å få et kvotient og en rest. Hvis resten er 1, er det siste binære sifferet 1, og hvis resten er 0, er det siste binære sifferet 0. Del med 2 igjen. Hvis resten er 1, er det siste siste sifferet 1 og hvis resten er 0, er det nest siste sifferet 0 og så videre til du får en kvotient på 0.

Å konvertere fra base 2 til hvilken som helst base, alt du trenger å gjøre er i den basen, start fra 0, så for hvert binære siffer som går fra venstre til høyre, dobler du i basen hvis tallet er 0 og dobbelt så legg til 1 i den basen hvis tallet er 1.

Kommentarer

• 2 is so easy to multiply or divide by in any base. Jeg don ‘ t se det for odde baser som er mer enn en fra hvilken som helst styrke på to (11 og 13, til å begynne med).