Matematiken bakom att konvertera från vilken bas som helst till vilken bas som helst utan att gå igenom bas 10?

Detta verkar vara en mycket grundläggande fråga för mig, så ursäkta mig om jag föreläser dig lite. Den viktigaste punkten för dig att lära dig här är att ett tal inte är dess siffrorepresentation . Ett tal är ett abstrakt matematiskt objekt, medan dess siffrorepresentation är en konkret sak, nämligen en sekvens av symboler på ett papper (eller en sekvens av bitar i beräkningsminnet eller en sekvens av ljud som du gör när du kommunicerar ett nummer). Det som förvirrar dig är det faktum att du aldrig ser ett nummer utan alltid dess siffra. Så du slutar tänka att siffran är representationen.

Därför är den rätta frågan inte att ställa till ” hur konverterar jag från en bas till en annan ” utan snarare ” hur får jag reda på vilket nummer som representeras av en viss sträng siffror ” och ” hur hittar jag sifferrepresentationen för ett givet nummer ”.

Så låt oss producera två funktioner i Python, en för att konvertera en sifferrepresentation till ett nummer och ett annat för att göra motsatsen. Obs: när vi kör funktionen Python kommer naturligtvis att skrivas ut på skärmen numret det fick i bas 10. Men detta betyder inte att datorn håller siffror i basen 10 (det är inte ”t). Det är irrelevant hur datorn representerar siffrorna.

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 

Låt oss testa dessa:

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

Beväpnad med konverteringsfunktioner löses ditt problem 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) 

Ett test :

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

Obs: vi gjorde inte gå igenom bas 10-representation! Vi konverterade basen $ b $ -representation till numret och sedan siffran till basen $ c $ . Numret var inte i någon representation. (Egentligen var det datorn som måste representera det på något sätt och det representerade det med hjälp av elektriska signaler och funky saker som händer i marker, men säkert de med är inte 0 ”och 1”.)

Kommentarer

• Detta övertygar inte ’ mig 100%. Faktum är att du konverterade numret till viss representation (även om du kan hävda att du inte vet vad det är) eftersom datorer inte är platoniska matematiker och din algoritm inte kan konvertera en godtycklig sekvens av siffror i bas $ b_1 $ till bas $ b_2 $; det kan bara konvertera sekvenser som kan representeras av betongmaskinen. Python är charmigt flexibel; C skulle inte ha varit så förlåtande. Det är helt giltigt att fråga hur man konverterar godtyckliga strängar från $ b_1 $ till $ b_2 $; detta är emellertid endast möjligt i linjär tid förutom med vissa baskombinationer (t.ex. 2 < – > 16)
• Det är giltigt att ställa frågan, men för att hitta rätt svar är det bäst att vara medveten om det faktum att siffror är abstrakta enheter.
• Detta passerar numret genom bas 10-representation, eftersom fromDigits returnerar siffran i bas 10.
• @anorton: Nej, definitivt gör det inte . Python skriver ut siffran på skärmen i bas 10-siffrig representation, men själva numret lagras inte på det sättet. Vad jag försöker komma över är att det är irrelevant hur siffrorna implementeras i Python. Det spelar ingen roll. Det enda som är viktigt är att de beter sig som siffror.
• Äntligen en allmän lösning för alla baser och inte begränsat till särskilda användningsfall, baser mindre än 36 eller tillfällen där du kan komma med tillräckligt med unika symboler .

Jag tror att det bästa sättet att förstå detta är i diskussion med en utomjording (åtminstone som en analogi).

Definition $ x $ är ett tal i bas $ b $ betyder att $ x $ är en sträng med siffror $ < b $.

Exempel Siffran 10010011011 är ett tal i bas 2, strängen 68416841531 är ett tal i bas 10, BADCAFE är ett tal i bas 16.

Nu Antag att jag växte upp på planeten QUUX där alla lärs ut att arbeta i $ q $ under hela sitt liv, och jag träffar dig som är van att basera $ b $. Så du visar mig ett nummer, och vad gör jag? Jag behöver ett sätt att tolka det:

Definition Jag kan tolka ett tal i bas $ b $ (Obs: $ b $ är ett tal i bas $ q $) med följande formel

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

där $ \ epsilon $ betecknar den tomma strängen och $ \ bar sd $ betecknar en sträng som slutar med siffran $ d $. Se mitt bevis på att tillägg lägger till för en introduktion till denna notation.

Så vad har hänt här? Du har gett mig ett nummer i bas $ b $ och jag har tolkat det till bas $ q $ utan någon konstig filosofi om vad siffror verkligen är.

Knapp Nyckeln till detta är att $ \ times $ och $ + $ I har funktioner som fungerar på bas $ q $ siffror. Dessa är enkla algoritmer definierade rekursivt på bas $ q $ nummer (strängar siffror).

Detta kan verka lite abstrakt eftersom jag har använt variabler snarare än faktiska siffror hela tiden. Så låt oss anta att du är en bas 13-varelse (med symbolerna $ 0123456789XYZ $) brukade basera 7 (vilket är mycket klokare) med symbolerna $ \ alpha \ beta \ gamma \ delta \ rho \ zeta \ xi $.

Så jag har sett ditt alfabet och tabulerat det så:

$$ \ 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å jag vet att du arbetar i bas $ \ beta \ xi $, och jag vet vilken bas 7 som är nummer varje siffra du skriv motsvarar.

Om vi nu diskuterade fysik och du berättade för mig om grundläggande konstanter (säg) $ 60Z8 $ så jag måste tolka detta:

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

Så jag börjar med att multiplicera $ \ beta \ zeta \ times \ beta \ xi $ men det här är grundskolan för mig, jag minns:

Quux-multiplikationstabell

$$ \ 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å för att hitta $ \ beta \ zeta \ times \ beta \ xi $ I do:

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

så jag har kommit så långt

$$ \ 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 måste jag utföra tillägget med algoritmen som nämndes tidigare:

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

så

$$ \ börjar {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} $ $

och fortsätter så här får jag $$ [\! [60Z8] \!] = \ zeta \ delta \ xi \ gamma \ rho. $$

I sammanfattning: Om jag har min egen uppfattning om antal i termer av bas $ q $ strängar av siffror, så har jag sätt att tolka dina siffror från bas $ b $ i mitt eget system, baserat på de grundläggande aritmetiska operationerna – som fungerar inbyggt i basera $ q $.

Kommentarer

• Det var en hel del snurrande linjer. Hur skulle jag få datorn att göra det dock?
• @Griffin, jag tror att du frågar den (konstiga) frågan i förtid. Du väljer ett programmeringsspråk och skriver ut algoritmen för addition och multiplicering på q-basnummer (representerade som siffror) och definierar sedan en funktion för att tolka bas-b-siffror till bas-q-tal och tolka bas-b-siffror till bas-q-tal. Jag ’ har förklarat allt detta.
• Saken är att jag känner till konceptet du försöker skildra. Mitt problem är att min dator ’ inte kan använda dina snurrande linjer.
• Jag vet vad du förklarade, men det är mycket svårare att omsätta det i praktiken. Du ser att det är enkelt att definiera dessa siffror ’ t.
• Varför släppte du alfasiffran i den mest betydelsefulla positionen? Eftersom 6 = & xi ;, Skulle ’ t 7 = & alfa; & alpha ;?

Detta är en refactoring (Python 3) av Andrej ”s-kod. Medan Andrej” s kodnummer representeras genom en lista med siffror (skalarer) representeras följande kodnummer genom en lista med godtyckliga symboler från en anpassad sträng:

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) 

Så här utför du en konvertering från värde till representation i en anpassad bas:

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

För att utföra en konvertering från representation (i en anpassad bas) till värde :

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

Så här utför du en baskonvertering från en kundbas till en annan:

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

Kommentarer

• Välkommen till sajten och tack för ditt bidrag. Att producera väloptimerad källkod är dock inte ’ t vad den här webbplatsen egentligen handlar om. Andrej ’ s kod gör begreppen tydliga, vilket är vad som behövs för hans svar, men att förbättra koden utöver det är en fråga om programmering, snarare än datavetenskap > i>.
• @ DavidRicherby Jag håller delvis med, men detta bidrag var för långt för en kommentar och det bästa stället att vara är någonstans nära Andrej ’ svar, att ’ varför jag publicerade det här. Hur som helst om du tycker att det ’ är bättre kan jag konvertera det till en kommentar med en länk till koden, men skulle inte ’ t ett överskott av purism?
• Trots @David ’ s ” site-purist ” invändningar, jag tyckte att ditt svar var användbart eftersom det betonar det faktum att de inblandade baserna kan ses i mer abstrakta termer som ” alfabet ” av godtyckliga symboler av varierande längd – och inte begränsat till det vanliga intervallet på 2-36 tecken. Du kan faktiskt överväga bytesströmmar som ” siffror ” av 256 256 heltalsvärden.

Grundläggande funktion av baskonvertering är toDigits() operation av @AndrejBauer-svaret. Men för att göra det finns det inget behov av att skapa ett nummer i den interna representationen av siffrorna, vilket i grunden är en omvandling från och till bas 2-representation.Du kan utföra nödvändiga operationer i den ursprungliga basrepresentationen.

Så det första steget är att göra repetitiv modulopdelningsoperation

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 

Eftersom den interna representationen är siffror måste man göra en speciliserad funktion för att testa noll

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

Så småningom måste man göra modulo_div-operationen som faktiskt är standardindelningen efter destinationsbas som vi lärde oss i skolan.

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 

bara en testkontroll för att verifiera att koden är 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

• Tack för inlägget men observera att vi ’ inte är en kodningswebbplats, så ett stort kodblock är inte ’ är inte lämpligt som svar här. Speciellt när frågan uttryckligen säger, ” Jag behöver ’ t behöver kod, jag behöver bara den grundläggande matematiken bakom den. ”
• @ DavidRicherby Jag försökte lägga till text.
• Tack. Och jag ser där ’ en hel del kod på den här sidan, trots vad jag sa!
• @ David: FWIW, jag tror att det här svarar på OP ’ är bäst eftersom den visar hur man konverterar mellan de två baserna utan att först konvertera originalets representation till någon mellanliggande form och sedan konvertera den till destinationsbasen.
• Trevligt försök men d är fortfarande i bas 10, så du extraherar i själva verket en mindre del av n och konverterar den till bas 10 och konverterar sedan den till önskad bas och samlar in dem till slutresultatet.

Jag vet ett enkelt sätt att göra baskonvertering som inte kräver ett datorprogram. Det är genom att definiera ett sätt att konvertera från valfri bas till bas 2 och vice versa och därefter täcka från en bas till en annan bas genom att först konvertera från den första basen till basen 2 och sedan konvertera från basen 2 till den andra basen. 2 är så lätt att multiplicera eller dela med i vilken bas som helst.

För att konvertera från vilken bas som helst till bas 2 behöver du bara känna igen det för valfritt tal, om du tar dess bas 2-notering och startar från 0 och sedan för varje siffra i ordning från vänster till höger dubbelt om den siffran är noll och dubbel än lägg till 1 om den siffran är 1, kommer du till det numret självt. Med tanke på det numret i vilken bas som helst kan du dela med 2 i basen för att få en kvot och återstoden. Om resten är 1 är den sista binära siffran 1 och om resten är 0 är den sista binära siffran 0. Dela med 2 igen. Om resten är 1, är den sista siffran 1 och om resten är 0, är den sista siffran 0 och så vidare tills du får en kvot på 0.

Att konvertera från bas 2 till valfri bas, allt du behöver göra är i den basen, börja från 0, sedan för varje binär siffra som går från vänster till höger, dubbla i den basen om den siffran är 0 och dubbel lägg sedan till 1 i den basen om den siffran är 1.

Kommentarer

• 2 is so easy to multiply or divide by in any base. Jag don ’ t se det för udda baser som är mer än en från vilken effekt som helst på två (11 och 13, till att börja med).