De wiskunde achter het converteren van elke basis naar elke basis zonder door basis 10 te gaan?

Dit lijkt me een heel basale vraag, dus neem me niet kwalijk als ik je een beetje les geef. Het belangrijkste punt dat u hier moet leren is dat een getal niet de cijferweergave is . Een getal is een abstract wiskundig object, terwijl de cijferweergave een concreet iets is, namelijk een reeks symbolen op een papier (of een reeks bits in het rekengeheugen, of een reeks geluiden die je maakt als je een getal communiceert). Wat je verwarrend is, is het feit dat je nooit een nummer ziet maar altijd de cijferweergave ervan. Dus je denkt uiteindelijk dat het getal de weergave is.

Daarom is de juiste vraag die moet worden gesteld niet ” hoe converteer ik van de ene basis naar de andere ” maar liever ” hoe kom ik erachter welk getal wordt vertegenwoordigd door een bepaalde reeks cijfers ” en ” hoe vind ik de cijferweergave van een bepaald getal “.

Laten we dus twee functies in Python produceren, een voor het converteren van een cijferweergave naar een nummer, en een ander om het tegenovergestelde te doen. Opmerking: wanneer we de functie uitvoeren, zal Python natuurlijk print op het scherm het nummer dat het in basis 10 heeft gekregen. Maar dit betekent niet dat de computer de nummers in de basis bijhoudt 10 (het is niet “t). Het is irrelevant hoe de computer de getallen weergeeft.

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 

Laten we deze testen:

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

Gewapend met conversiefuncties, is uw probleem eenvoudig op te lossen:

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

Een test :

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

Opmerking: we hebben niet passeren de weergave met grondtal 10! We hebben de $ b $ -weergave met grondtal omgezet naar het getal en vervolgens het getal naar $ c $ . Het nummer was in geen enkele weergave niet . (Eigenlijk moest de computer het op de een of andere manier weergeven, en het stelde het voor met behulp van elektrische signalen en funky dingen die in chips gebeuren, maar zeker die w ere niet 0 “s en 1” s.)

Reacties

• Dit ‘ kan niet overtuigen mij 100%. In feite heb je het getal geconverteerd naar een representatie (hoewel je kunt beweren niet te weten wat het is) omdat computers geen platonische wiskundigen zijn en je algoritme geen willekeurige reeks cijfers in basis $ b_1 $ kan omzetten naar $ b_2 $; het kan alleen reeksen converteren die door de betonmachine kunnen worden weergegeven. Python is charmant flexibel; C zou niet zo vergevingsgezind zijn geweest. Het is volkomen geldig om te vragen hoe willekeurige strings kunnen worden geconverteerd van $ b_1 $ naar $ b_2 $; dit is echter alleen mogelijk in lineaire tijd, behalve met bepaalde basiscombinaties (bijv. 2 < – > 16)
• Het is geldig om de vraag te stellen, maar om het juiste antwoord te vinden, is het het beste om je ervan bewust te zijn dat getallen abstracte entiteiten zijn.
• Dit geeft wel het getal door tot en met grondtal 10, aangezien de fromDigits het getal met grondtal 10 retourneert.
• @anorton: Nee, zeer zeker niet . Python drukt het nummer op het scherm af in een weergave van 10 cijfers, maar het nummer zelf wordt niet op die manier opgeslagen. Wat ik probeer over te brengen, is dat het irrelevant is hoe de getallen in Python worden geïmplementeerd. Dat maakt niet uit. Het enige dat telt, is dat ze zich gedragen als getallen.
• Eindelijk een algemene oplossing voor elke basis en niet beperkt tot specifieke use-cases, bases kleiner dan 36, of gevallen waarin je genoeg unieke symbolen kunt bedenken .

Ik denk dat de beste manier om dit te begrijpen is in een gesprek met een buitenaards wezen (tenminste als een analogie).

Definitie $ x $ is een getal in basis $ b $ betekent dat $ x $ een reeks cijfers is $ < b $.

Voorbeelden De reeks cijfers 10010011011 is een getal in basis 2, de reeks 68416841531 is een getal in basis 10, BADCAFE is een getal in basis 16.

Nu Stel dat ik ben opgegroeid op de planeet QUUX waar iedereen wordt geleerd om zijn hele leven in $ q $ te werken, en ik ontmoet je die gewend is $ b $ te baseren. Dus je laat me een nummer zien, en wat moet ik doen? Ik heb een manier nodig om het te interpreteren:

Definitie Ik kan interpreteren een getal in basis $ b $ (Opmerking: $ b $ is een getal in $ q $) door de volgende formule

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

waar $ \ epsilon $ geeft de lege string aan, en $ \ bar sd $ geeft een string aan die eindigt op het cijfer $ d $. Zie mijn bewijs dat deze toevoeging toevoegt voor een inleiding op deze notatie.

Dus wat is hier gebeurd? Je hebt me een nummer gegeven in basis $ b $ en ik “heb het geïnterpreteerd in basis $ q $ zonder enige rare filosofie over wat getallen werkelijk zijn.

Sleutel De sleutel hiervoor is dat de $ \ times $ en $ + $ die ik heb functies zijn die werken op basis $ q $ nummers. Dit zijn eenvoudige algoritmen die recursief zijn gedefinieerd op basis $ q $ nummers (strings van cijfers).

Dit lijkt misschien een beetje abstract, aangezien ik “variabelen in plaats van werkelijke getallen heb gebruikt. Stel dat je een wezen met basis 13 bent (met symbolen $ 0123456789XYZ $) en ik ben gebruikt om 7 te baseren (wat veel verstandiger is) met symbolen $ \ alpha \ beta \ gamma \ delta \ rho \ zeta \ xi $.

Dus ik heb je alfabet gezien en het als volgt in tabelvorm weergegeven:

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

Dus ik weet dat je werkt in basis $ \ beta \ xi $, en ik weet welk cijfer je wilt met basis 7 schrijven komt overeen met.

Als we het nu hadden over natuurkunde en je vertelde me over fundamentele constanten (zeg maar) $ 60Z8 $, dus ik moet dit interpreteren:

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

Dus ik begin met $ \ beta \ zeta \ times \ beta \ xi $ maar dit zijn dingen van de lagere school voor mij, ik herinner me:

Quux-tafel van vermenigvuldiging

$$ \ begin {array} {| c | cccccc |} \ hline \\ \ maal & \ 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} $$

dus om $ \ beta \ zeta \ times \ beta \ xi $ te vinden, doe ik:

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

dus ik ben zo ver

$$ \ 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 moet ik de optelling uitvoeren met het algoritme dat werd eerder genoemd:

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

dus

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

en zo doorgaand krijg ik $$ [\! [60Z8] \!] = \ zeta \ delta \ xi \ gamma \ rho. $$

In samenvatting: Als ik mijn eigen opvatting heb van getallen in termen van basis $ q $ cijferreeksen, dan heb ik een manier om uw getallen van basis $ b $ in mijn eigen systeem te interpreteren, op basis van de fundamentele rekenkundige bewerkingen – die standaard werken in base $ q $.

Opmerkingen

• Nou, dat waren nogal wat kronkelige lijnen. Maar hoe zou ik de computer zover krijgen om dat te doen?
• @Griffin, ik denk dat je die (vreemde) vraag voortijdig stelt. U kiest een programmeertaal en typt het algoritme voor optellen en vermenigvuldigen op basis q-getallen (weergegeven als lijsten met cijfers), en vervolgens definieert u een functie om basis b-cijfers te interpreteren in basis q-getallen en basis b-getallen te interpreteren in basis q-getallen. Ik ‘ heb dit allemaal uitgelegd.
• Ik ken het concept dat je probeert uit te beelden. Mijn probleem is dat mijn computer ‘ je kronkelende lijnen niet kan gebruiken.
• Ik weet wat je hebt uitgelegd, maar het in de praktijk brengen is veel moeilijker. Je ziet het definiëren van die cijfers isn ‘ t zo gemakkelijk.
• En waarom heb je het alfa-cijfer op de meest significante positie laten vallen? Aangezien 6 = & xi ;, Zoun ‘ t 7 = & alpha; & alpha ;?

Dit is een refactoring (Python 3) van Andrej “s code. Terwijl in Andrej” s codenummers worden weergegeven door middel van een lijst met cijfers (scalairen), worden in de volgende codenummers weergegeven door een lijst met willekeurige symbolen overgenomen uit een aangepaste tekenreeks:

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) 

Om een conversie uit te voeren van waarde naar representatie in een custom base:

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

Om een conversie uit te voeren van representatie (in een custom base) naar waarde :

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

Om een basisconversie van de ene klantenbasis naar de andere uit te voeren:

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

Reacties

• Welkom op de site en bedankt voor je bijdrage. Het produceren van goed geoptimaliseerde broncode is echter niet ‘ t waar deze site echt over gaat. Andrej ‘ s code maakt de concepten duidelijk, wat nodig is voor zijn antwoord, maar het verbeteren van de code verder is een kwestie van programmeren, in plaats van computer wetenschap .
• @DavidRicherby Ik ben het er gedeeltelijk mee eens, maar deze bijdrage was te lang voor commentaar en de beste plaats om te zijn is ergens in de buurt van Andrej ‘ s antwoord, dat ‘ is waarom ik het hier heb gepost. Hoe dan ook, als je denkt dat het ‘ beter is, zou ik het kunnen converteren naar een commentaar met een link naar de code, maar ‘ zou het niet zijn een overdaad aan purisme?
• Ondanks @David ‘ s ” site-purist ” bezwaren, ik vond je antwoord nuttig omdat het benadrukt dat de betrokken bases in meer abstracte termen kunnen worden gezien als ” alfabetten ” van willekeurige symbolen van verschillende lengtes – en niet beperkt tot het gebruikelijke bereik van 2-36 tekens. In feite zou je streams van bytes kunnen beschouwen als de ” cijfers ” van 256 basiswaarden.

Fundamentele werking van basisconversie is de toDigits() -bewerking van @AndrejBauer answer. Om het te maken, is het echter niet nodig om een nummer te maken in de interne weergave van de nummers, wat in feite een conversie is van en naar basis 2-weergave.U kunt de benodigde bewerkingen uitvoeren in de oorspronkelijke basisweergave.

Dus de eerste stap is om een herhaalde modulo-deelbewerking uit te voeren.

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 

Aangezien de interne representatie uit cijfers bestaat, moet men een gespecificeerde functie voor het testen van nul

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

Uiteindelijk moet men de bewerking modulo_div uitvoeren, wat eigenlijk de standaardindeling op basis van bestemming is, zoals we op school hebben geleerd.

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 

gewoon een testcontrole om te controleren of de code correct is:

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] 

Reacties

• Bedankt voor het posten, maar houd er rekening mee dat we ‘ geen coderingssite zijn, dus een groot codeblok is niet ‘ is hier niet geschikt als antwoord. Vooral als de vraag expliciet zegt: ” Ik heb ‘ geen code nodig, ik heb alleen de basis wiskunde erachter nodig. ”
• @DavidRicherby Ik heb geprobeerd tekst toe te voegen.
• Bedankt. En ik zie daar ‘ een heleboel code op deze pagina, ondanks wat ik zei!
• @David: FWIW, ik denk dat dit het OP beantwoordt ‘ s vraag het beste, omdat het laat zien hoe je tussen de twee bases kunt converteren zonder eerst de weergave van het origineel naar een tussenvorm te converteren en die vervolgens naar de bestemmingsbasis te converteren.
• Leuke poging, maar d staat nog in basis 10, dus je extraheert in feite een kleiner deel van n, converteert het naar basis 10, converteert dat naar de gewenste basis en verzamelt die in het eindresultaat.

Ik ken een gemakkelijke manier om basisconversie uit te voeren waarvoor geen computerprogramma nodig is. Het is door te definiëren een manier om van elke basis naar basis 2 te converteren en vice versa en vervolgens van de ene basis naar de andere basis te bedekken door eerst van de eerste basis naar basis 2 te converteren en vervolgens van basis 2 naar de andere basis. 2 is zo gemakkelijk te vermenigvuldigen of te delen met een grondtal.

Om van een grondtal naar een grondtal 2 te converteren, hoef je alleen maar te erkennen dat voor elk getal, als je de notatie met grondtal 2 neemt en begint vanaf 0 en dan voor elk cijfer in de volgorde van links naar rechts dubbel als dat cijfer nul is en dubbel dan 1 als dat cijfer 1 is, krijg je bij dat nummer zelf. Nu je dat getal in een willekeurige basis hebt gegeven, kun je in die basis delen door 2 om een quotiënt en de rest te krijgen. Als de rest 1 is, is het laatste binaire cijfer 1 en als de rest 0 is, is het laatste binaire cijfer 0. Deel opnieuw door 2. Als de rest 1 is, is het voorlaatste cijfer 1 en als de rest 0 is, is het voorlaatste cijfer 0 enzovoort, totdat je een quotiënt van 0 krijgt.

Om te converteren van grondtal 2 naar eender welke basis, alles wat je hoeft te doen is in die basis, begin bij 0, dan voor elk binair cijfer dat van links naar rechts gaat, verdubbel in die basis als dat cijfer 0 is en dubbel en tel dan 1 in die basis op als dat cijfer 1 is.

Reacties

• 2 is so easy to multiply or divide by in any base. Ik heb geen ‘ t zie dat voor oneven grondslagen die meer dan één zijn van een willekeurige macht van twee (om te beginnen 11 en 13).

U kunt van basis n naar basis 10 converteren zonder enige conversie naar een tussenliggende basis.

Om bijvoorbeeld van basis n naar basis 9 te converteren, neem je het algoritme voor conversie naar basis 10 en vervang je “10” door “9”. Hetzelfde geldt voor elke andere basis.