Matematika za převodem z libovolné základny na libovolnou základnu, aniž byste prošli základnou 10?

Zdá se mi to velmi základní otázka, omluvte mě, pokud vám trochu přednáším. Nejdůležitějším bodem, který se zde musíte naučit, je to, že číslo není jeho číselným vyjádřením . Číslo je abstraktní matematický objekt, zatímco jeho číslicová reprezentace je konkrétní věc, jmenovitě posloupnost symbolů na papíře (nebo posloupnost bitů ve výpočetní paměti nebo posloupnost zvuků, které vydáváte, když sdělujete číslo). Matoucí je skutečnost, že nikdy nevidíte číslo, ale vždy jeho číselné vyjádření. Nakonec si tedy myslíte, že číslo je reprezentace.

Správná otázka tedy není “ jak převádím z jedné základny na druhou “ ale spíše “ jak zjistím, které číslo představuje daný řetězec číslic “ a “ jak najdu číselné vyjádření daného čísla „.

Vytvořme tedy v Pythonu dvě funkce, jednu pro převod číselné reprezentace na číslo a další za opak. Poznámka: když spustíme funkci, Python samozřejmě vytiskne na obrazovku číslo, které dostal v základně 10. To ale neznamená , že počítač udržuje čísla v základně 10 (není to „t). Je irelevantní , jak počítač reprezentuje čísla.

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 

Vyzkoušejme je:

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

Vyzbrojen konverzními funkcemi je váš problém snadno vyřešen:

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

Test :

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

Poznámka: udělali jsme ne projít reprezentací základny 10! Převedli jsme základní $ b $ reprezentaci na číslo a poté číslo na základnu $ c $ . Toto číslo nebylo v žádné reprezentaci. (Ve skutečnosti to bylo, počítač to musel nějak reprezentovat a reprezentovalo to pomocí elektrických signálů a funky věci, které se dějí v žetonech, ale určitě ty w Není 0 a 1.)

Komentáře

• To ‚ nepřesvědčuje já 100%. Ve skutečnosti jste číslo převedli na nějakou reprezentaci (i když můžete tvrdit, že nevíte, o co jde), protože počítače nejsou platoničtí matematici a váš algoritmus nemůže převést libovolnou sekvenci číslic v základu $ b_1 $ na základnu $ b_2 $; dokáže převést pouze sekvence reprezentovatelné konkrétním strojem. Python je okouzlující flexibilní; C by nebyl tak shovívavý. Je naprosto platné se ptát, jak převést libovolné řetězce z $ b_1 $ na $ b_2 $; to je však možné pouze v lineárním čase, s výjimkou určitých základních kombinací (např. 2 < – > 16)
• Položit otázku je platné, ale pro nalezení správné odpovědi je nejlepší si uvědomit, že čísla jsou abstraktní entity.
• Toto předává číslo prostřednictvím reprezentace základny 10, protože fromDigits vrací číslo v základně 10.
• @anorton: Ne, rozhodně to není . Python vytiskne číslo na obrazovce v základní 10místné reprezentaci, ale samotné číslo se tak neukládá. Snažím se narazit na to, že je irelevantní , jak jsou čísla implementována uvnitř Pythonu. Na tom nezáleží. Důležité je jen to, že se chovají jako čísla.
• Konečně obecné řešení pro libovolnou základnu, které se neomezuje na konkrétní případy použití, základny menší než 36 nebo případy, kdy můžete přijít s dostatkem jedinečných symbolů .

Myslím, že nejlepší způsob, jak tomu porozumět, je diskuse s mimozemšťanem (alespoň analogie).

Definice $ x $ je číslo v základu $ b $ znamená, že $ x $ je řetězec číslic $ < b $.

Příklady Řetězec číslic 10010011011 je číslo v základu 2, řetězec 68416841531 je číslo v základu 10, BADCAFE je číslo v základně 16.

Nyní Předpokládejme, že jsem vyrostl na planetě QUUX, kde je každý naučen pracovat v $ q $ po celý svůj život, a potkám vás, kdo je zvyklý zakládat $ b $. Ukážeš mi tedy číslo a co mám dělat? Potřebuji způsob, jak to interpretovat:

Definice Mohu interpretovat číslo v základu $ b $ (Poznámka: $ b $ je číslo v základu $ q $ $) podle následujícího vzorce

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

kde $ \ epsilon $ označuje prázdný řetězec a $ \ bar sd $ označuje řetězec končící číslicí $ d $. Úvod do této notace najdete v mém důkazu, že přidání přidává .

Takže co se tady stalo? Dali jste mi číslo v base $ b $ a já jsem to interpretoval do base $ q $ bez jakékoli podivné filozofie o tom, jaká čísla skutečně jsou.

Klíč Klíčem k tomu je, že $ \ times $ a $ + $, které mám, jsou funkce, které fungují na základních číslech $ q $ $. Jedná se o jednoduché algoritmy definované rekurzivně na základních číslech $ q $ (řetězce číslic).

To se může zdát trochu abstraktní, protože v celém textu používám spíše proměnné než skutečná čísla. Předpokládejme tedy, že jste stvoření základní 13 (používající symboly $ 0123456789XYZ $) a já jsem slouží k základu 7 (což je mnohem rozumnější) pomocí symbolů $ \ alpha \ beta \ gamma \ delta \ rho \ zeta \ xi $.

Takže jsem viděl vaši abecedu a uvedl ji do tabulky takto:

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

Takže vím, že pracujete v základně $ \ beta \ xi $ a vím, jaké číslo základny 7 vám jakoukoli číslici zápis odpovídá.

Nyní, když jsme hovořili o fyzice a vy jste mi říkal o základních konstantách (řekněme) $ 60Z8 $, tak to musím interpretovat:

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

Začnu tedy vynásobením $ \ beta \ zeta \ times \ beta \ xi $, ale toto je pro mě základní škola, vzpomínám si:

Násobilka Quux

$$ \ begin {pole} {| 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 {pole} $$

takže najdu $ \ beta \ zeta \ times \ beta \ xi $, které dělám:

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

takže jsem se dostal tak daleko

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

Teď musím provést přidání pomocí algoritmu, který bylo zmíněno dříve:

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

tak

$$ \ begin {pole} {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 {pole} $ $

a pokračováním tímto způsobem dostanu $$ [\! [60Z8] \!] = \ zeta \ delta \ xi \ gamma \ rho. $$

V Shrnutí: Pokud mám vlastní pojetí čísla, pokud jde o základní $ q $ řetězce číslic, pak mám způsob, jak interpretovat vaše čísla ze základního $ b $ do mého vlastního systému na základě základních aritmetických operací – které nativně fungují v base $ q $.

Komentáře

• No, to byla spousta klikatých čar. Jak bych však přiměl počítač, aby to udělal?
• @Griffin, myslím, že se této (podivné) otázky ptáte předčasně. Vyberete si programovací jazyk a napíšete algoritmus pro sčítání a násobení na základních číslech q (představovaných jako seznamy číslic), poté definujete funkci k interpretaci číslic základního b do čísel základního q a interpretaci čísel základního b do základních čísel q. To vše jsem ‚ vysvětlil.
• Věc je, že znám koncept, který se snažíte vykreslit. Mým problémem je, že můj počítač ‚ t nemůže použít vaše zakroucené řádky.
• Vím, co jste vysvětlili, ale jeho zavedení do praxe je mnohem těžší. Definování těchto číslic není ‚ t tak snadné.
• Proč jste tedy umístili alfanumerickou pozici na nejvýznamnější pozici? Protože 6 = & xi ;, nebylo by ‚ t 7 = & alfa; & alpha ;?

Toto je refaktoring (Python 3) Andrejova kódu. Zatímco v Andrejově kódu jsou čísla reprezentována seznamem číslic (skalárů), v následujících číslech kódu jsou reprezentována prostřednictvím seznam libovolných symbolů převzatých z vlastního řetězce:

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) 

Provedení převodu z hodnoty na reprezentaci ve vlastní základně:

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

Provedení převodu z reprezentace (ve vlastní základně) na hodnotu :

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

Provedení základní konverze z jedné vlastní základny do druhé:

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

Komentáře

• Vítejte na webu a děkujeme za váš příspěvek. Produkce dobře optimalizovaného zdrojového kódu však ‚ není to, o čem tento web opravdu je. Andrej ‚ s kód objasňuje koncepty, což je to, co je pro jeho odpověď zapotřebí, ale zdokonalení kódu nad rámec toho je spíše záležitostí programování než počítačové vědy .
• @DavidRicherby Částečně souhlasím, ale tento příspěvek byl příliš dlouhý na komentář a jeho nejlepší místo je někde poblíž odpovědi Andrej ‚, to je ‚ důvod, proč jsem to sem zveřejnil. Každopádně, pokud si myslíte, že je to ‚ lepší, mohl bych jej převést na komentář s odkazem na kód, ale ‚ by to nebylo přebytek purismu?
• Navzdory @David ‚ s “ site-purist “ námitky, shledal jsem vaši odpověď užitečnou, protože zdůrazňuje skutečnost, že použité základny lze považovat za abstraktnější pojmy jako “ abecedy “ libovolných symbolů různé délky – bez omezení na obvyklý rozsah 2–36 znaků. Ve skutečnosti byste mohli bajty považovat za “ číslic “ základních 256 celočíselných hodnot.

Základní operací základní konverze je toDigits() operace odpovědi @AndrejBauer. Aby to však bylo možné, není třeba vytvářet číslo v interní reprezentaci čísel, což je v zásadě převod z a na reprezentaci základny 2.Potřebné operace můžete provést v původní základní reprezentaci.

Prvním krokem je tedy opakovaná operace dělení modulo

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 

Protože interní reprezentace je číslice, je třeba provést specifikovaný funkce pro testování nuly

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

Nakonec je třeba provést operaci modulo_div, což je vlastně standardní dělení podle cílové základny, jak jsme se to naučili ve škole.

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 

pouze testovací kontrola k ověření správnosti kódu:

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] 

Komentáře

• Děkujeme za zveřejnění příspěvku, ale uvědomte si, že ‚ nejsme kódovací web, takže velký blok kódu není ‚ zde není vhodná odpověď. Zvláště když otázka výslovně říká: “ Nepotřebuji ‚ kód, stačí mi za ním základní matematika. “
• @DavidRicherby Zkoušel jsem přidat text.
• Díky. A vidím tam ‚ sakra spoustu kódu na této stránce, navzdory tomu, co jsem řekl!
• @David: FWIW, myslím, že to odpovídá OP ‚ s otázkou nejlépe, protože ukazuje, jak převádět mezi dvěma základnami, aniž by se nejprve převedla reprezentace originálu na nějakou střední formu a poté se převede na cílovou základnu.
• Pěkný pokus, ale d je stále v základně 10, takže ve skutečnosti extrahujete nějakou menší část n a převádíte ji na základnu 10, pak ji převádíte na požadovanou základnu a shromažďujete je do konečného výsledku.

Znám snadný způsob základní konverze, který nevyžaduje počítačový program. Je to definováním způsob převodu z libovolné základny na základnu 2 a naopak a poté krytí z jedné základny na druhou základnu nejprve převedením z první základny na základnu 2 a poté převodem ze základny 2 na druhou základnu. 2 je tak snadné znásobit nebo rozdělit na libovolnou základnu.

Chcete-li převést z libovolné základny na základnu 2, musíte pouze uznat, že pro libovolné číslo, pokud vezmete jeho základnu 2 a začnete od 0 a potom pro každou číslici v pořadí zleva doprava zdvojnásobit, pokud je tato číslice nula a zdvojnásobit, než přidat 1, pokud je tato číslice 1, dostanete se k tomuto číslu samotnému. Nyní dané číslo v libovolné základně, můžete vydělit 2 v této základně, abyste získali podíl a zbytek. Pokud je zbytek 1, poslední binární číslice je 1 a pokud je zbytek 0, poslední binární číslice je 0. Vydělte znovu 2. Pokud je zbytek 1, druhá poslední číslice je 1 a pokud je zbytek 0, druhá poslední číslice je 0 atd., Dokud nezískáte kvocient 0.

Převod ze základny 2 na libovolnou základna, vše, co musíte udělat, je v této základně, začít od 0, pak pro každou binární číslici, která jde zleva doprava, zdvojnásobit v této základně, pokud je tato číslice 0 a zdvojnásobit, pak přidat 1 do této základny, pokud je tato číslice 1.

Komentáře

• 2 is so easy to multiply or divide by in any base. Ne ‚ t podívejte se na to pro liché báze, které jsou více než jednou z libovolné síly dvou (pro začátek 11 a 13).

Můžete převádět ze základny n na základnu 10 bez převodu na nějakou střední základnu.

Chcete-li například převést ze základny n na základnu 9, použijete algoritmus pro převod na základnu 10 a „10“ nahradíte „9“. Totéž pro jakoukoli jinou základnu.