Matematyka stojąca za konwersją z dowolnej bazy na dowolną bez przechodzenia przez bazę 10?

Wydaje mi się to bardzo podstawowe pytanie, więc przepraszam, jeśli cię trochę pouczam. Najważniejszą rzeczą do nauczenia się w tym miejscu jest to, że liczba nie jest reprezentacją cyfrową . Liczba jest abstrakcyjnym obiektem matematycznym, podczas gdy jej reprezentacja cyfrowa jest konkretną rzeczą, a mianowicie sekwencją symboli na papierze (lub sekwencją bitów w pamięci obliczeniowej lub sekwencją dźwięków, które wydajesz, gdy podajesz liczbę). Wprawia Cię w zakłopotanie fakt, że nigdy nie widzisz liczby, ale zawsze jest ona cyfrowa. W końcu myślisz, że liczba jest reprezentacją.

Dlatego właściwe pytanie, które należy zadać, nie brzmi: ” jak konwertować z jednej zasady na inną „, ale raczej ” jak sprawdzić, która liczba jest reprezentowana przez dany ciąg cyfr ” i ” jak znaleźć cyfrową reprezentację podanej liczby „.

Stwórzmy dwie funkcje w Pythonie, jedną do konwersji reprezentacji cyfr na liczbę, a drugą odwrotnie. Uwaga: kiedy uruchomimy funkcję, Python oczywiście wypisze na ekranie liczbę otrzymaną w bazie 10. Ale to nie oznacza, że komputer przechowuje liczby w bazie 10 (to nie jest „t). Nie ma znaczenia , w jaki sposób komputer przedstawia liczby.

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 

Przetestujmy to:

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

Dzięki funkcjom konwersji Twój problem jest łatwo rozwiązany:

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] 

Uwaga: zrobiliśmy nie przechodzą przez reprezentację o podstawie 10! Przekonwertowaliśmy podstawową reprezentację $ b $ na liczbę, a następnie liczbę na podstawową $ c $ . Liczba była nie w żadnej reprezentacji. (Właściwie to była, komputer musiał ją w jakiś sposób reprezentować i reprezentował ją za pomocą sygnałów elektrycznych i funky rzeczy, które dzieje się w frytkach, ale z pewnością te w Nie ma 0 „si 1”.)

Komentarze

• To nie ' nie przekonuje ja w 100%. W rzeczywistości przekonwertowałeś liczbę na jakąś reprezentację (chociaż możesz twierdzić, że nie wiesz, co to jest), ponieważ komputery nie są matematykami platonicznymi, a twój algorytm nie może przekształcić dowolnej sekwencji cyfr o podstawie $ b_1 $ na podstawę $ b_2 $; może konwertować tylko sekwencje reprezentowane przez konkretną maszynę. Python jest uroczo elastyczny; C nie byłby tak wyrozumiały. Dobrze jest zapytać, jak przekonwertować dowolne ciągi z $ b_1 $ na $ b_2 $; jest to jednak możliwe tylko w czasie liniowym, z wyjątkiem pewnych kombinacji podstawowych (np. 2 < – > 16)
• Zadawanie pytania jest poprawne, ale aby znaleźć właściwą odpowiedź, najlepiej zdawać sobie sprawę z faktu, że liczby są abstrakcyjnymi bytami.
• To przekazuje liczbę do reprezentacji o podstawie 10, ponieważ fromDigits zwraca liczbę o podstawie 10.
• @anorton: Nie, z całą pewnością nie . Python wyświetla liczbę na ekranie w 10-cyfrowej reprezentacji, ale sama liczba nie jest przechowywana w ten sposób. Próbuję zrozumieć, że nieistotne jest to, w jaki sposób liczby są implementowane w Pythonie. Nie ważne. Jedyną rzeczą, która ma znaczenie, jest to, że zachowują się jak liczby.
• Wreszcie ogólne rozwiązanie dla dowolnej bazy, nieograniczone do konkretnych przypadków użycia, baz mniejszych niż 36 lub przypadków, w których można wymyślić wystarczającą liczbę unikalnych symboli .

Myślę, że najlepszym sposobem na zrozumienie tego jest dyskusja z obcym (przynajmniej w analogia).

Definicja $ x $ to liczba w bazie $ b $ oznacza, że $ x $ to ciąg cyfr $ < b $.

Przykłady Ciąg cyfr 10010011011 to liczba o podstawie 2, ciąg 68416841531 to liczba o podstawie 10, BADCAFE to liczba o podstawie 16.

Teraz Przypuśćmy, że dorastałem na planecie QUUX, na której wszyscy uczą się pracować w $ q $ przez całe życie i spotykam cię, który zwykł opierać się na $ b $. Więc pokazujesz mi liczbę i co mam zrobić? Potrzebuję sposobu, aby to zinterpretować:

Definicja Potrafię interpretować liczba o podstawie $ b $ (Uwaga: $ b $ to liczba o podstawie $ q $) według następującego wzoru

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

gdzie $ \ epsilon $ oznacza pusty ciąg, a $ \ bar sd $ oznacza ciąg kończący się cyfrą $ d $. Zobacz mój dowód, że dodatek dodaje jako wprowadzenie do tego zapisu.

Więc co się tutaj stało? Dałeś mi numer w bazie $ b $ i „zinterpretowałem to jako podstawę $ q $ bez żadnej dziwnej filozofii na temat tego, czym naprawdę są liczby.

Klucz Kluczem do tego jest to, że $ \ razy $ i $ + $, które mam, to funkcje działające na liczbach o podstawie $ q $. Są to proste algorytmy zdefiniowane rekurencyjnie na liczbach podstawowych $ q $ (łańcuchach cyfr).

Może się to wydawać trochę abstrakcyjne, ponieważ używałem zmiennych zamiast rzeczywistych liczb. Załóżmy więc, że jesteś stworzeniem o podstawie 13 (używając symboli $ 0123456789XYZ $) i jestem używany do podstawy 7 (co jest znacznie bardziej rozsądne) przy użyciu symboli $ \ alpha \ beta \ gamma \ delta \ rho \ zeta \ xi $.

Widziałem więc twój alfabet i zestawiłem go w ten sposób:

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

Więc wiem, że pracujesz w bazie $ \ beta \ xi $, i wiem, jaka liczba podstawowa 7 oznacza dowolną cyfrę pisać odpowiada.

Gdybyśmy teraz dyskutowali o fizyce i mówiłeś mi o podstawowych stałych (powiedzmy) 60Z8 $, więc muszę to zinterpretować:

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

Więc zaczynam od pomnożenia $ \ beta \ zeta \ times \ beta \ xi $ ale to są dla mnie rzeczy ze szkoły podstawowej, przypominam sobie:

Tabliczka mnożenia Quux

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

aby znaleźć $ \ beta \ zeta \ times \ beta \ xi $ Robię:

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

więc dotarłem już 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 {array} $$

Teraz muszę wykonać dodawanie za pomocą algorytmu, który wspomniano wcześniej:

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

więc

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

i kontynuując w ten sposób otrzymuję $$ [\! [60Z8] \!] = \ zeta \ delta \ xi \ gamma \ rho. $$

W Podsumowanie: Jeśli mam własną koncepcję liczby w kategoriach bazowych $ q $ ciągów cyfr, to mam sposób na zinterpretowanie twoich liczb z podstawy $ b $ do własnego systemu, w oparciu o podstawowe operacje arytmetyczne – które działają natywnie w base $ q $.

Komentarze

• Cóż, to była duża porcja falistych linii. Jak mam jednak skłonić komputer do tego?
• @Griffin, myślę, że zadajesz to (dziwne) pytanie przedwcześnie. Wybierasz język programowania i wpisujesz algorytm dodawania i mnożenia na podstawie liczb q (przedstawionych jako listy cyfr), a następnie definiujesz funkcję, która interpretuje podstawowe b cyfry na podstawowe q liczby i interpretuje podstawowe b liczb na podstawowe q liczby. ' wyjaśniłem to wszystko.
• Rzecz w tym, że znam koncepcję, którą próbujesz przedstawić. Mój problem polega na tym, że mój komputer nie może ' używać twoich falistych linii.
• Wiem, co wyjaśniłeś, ale wprowadzenie tego w życie jest znacznie trudniejsze. Widzisz, że zdefiniowanie tych cyfr nie jest ' t takie proste.
• Poza tym, dlaczego upuściłeś cyfrę alfa na najbardziej znaczącej pozycji? Ponieważ 6 = & xi ;, Wouldn ' t 7 = & alpha; & alpha ;?

To jest refaktoryzacja (Python 3) kodu Andrej „s . Podczas gdy w kodzie Andreja numery kodów są reprezentowane przez listę cyfr (skalarów), w poniższych numerach kodowych są reprezentowane przez lista dowolnych symboli pobranych z niestandardowego ciągu:

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) 

Aby przeprowadzić konwersję z wartości do przedstawienia w niestandardowej bazie:

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

Aby przeprowadzić konwersję z reprezentacji (w niestandardowej bazie) na wartość :

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

Aby wykonać konwersję podstawową z jednej bazy niestandardowej na inną:

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

Komentarze

• Witamy w serwisie i dziękujemy za Twój wkład. Jednak tworzenie dobrze zoptymalizowanego kodu źródłowego nie jest ' tym, o czym tak naprawdę jest ta witryna. Kod Andreja ' wyjaśnia koncepcje, co jest potrzebne do jego odpowiedzi, ale ulepszenie kodu wykraczające poza to jest kwestią programowania, a nie informatyki .
• @DavidRicherby Częściowo się zgadzam, ale ten wkład był zbyt długi na komentarz, a jego najlepszym miejscem jest gdzieś w pobliżu odpowiedzi Andreja ', dlatego ' dlatego opublikowałem to tutaj. W każdym razie, jeśli uważasz, że ' lepiej, mógłbym zamienić to na komentarz z linkiem do kodu, ale nie ' nie nadmiar puryzmu?
• Pomimo @David ' s ” site-purist ” obiekcje, Twoja odpowiedź była dla mnie użyteczna, ponieważ podkreśla fakt, że odnośne zasady można traktować bardziej abstrakcyjnie jako ” alfabety ” dowolnych symboli o różnych długościach – nie ograniczonych do zwykłego zakresu 2-36 znaków. W rzeczywistości strumienie bajtów można traktować jako ” cyfry ” podstawowych 256 wartości całkowitych.

Podstawową operacją konwersji bazy jest operacja toDigits() odpowiedzi @AndrejBauer. Jednak aby to zrobić, nie ma potrzeby tworzenia liczby w wewnętrznej reprezentacji liczb, która jest w zasadzie konwersją zi do reprezentacji o podstawie 2.Możesz wykonać potrzebne operacje w oryginalnej reprezentacji bazowej.

Więc pierwszym krokiem jest wykonanie powtarzalnej operacji dzielenia 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 

Ponieważ wewnętrzna reprezentacja to cyfry, należy określić wyspecyfikowaną funkcja do testowania zera

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

Ostatecznie należy wykonać operację modulo_div, która jest w rzeczywistości standardowym dzieleniem przez bazę docelową, czego nauczyliśmy się w szkole.

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 

tylko testowe sprawdzenie, czy kod jest poprawny:

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] 

Komentarze

• Dziękujemy za wysłanie, ale pamiętaj, że ' nie jesteśmy witryną kodującą, więc duży blok kodu to nie ' nie jest odpowiednia jako odpowiedź tutaj. Zwłaszcza, gdy pytanie wyraźnie mówi, ” Nie ' nie potrzebuję kodu, potrzebuję tylko podstawowej matematyki. ”
• @DavidRicherby Próbowałem dodać tekst.
• Dzięki. I widzę tam ', mimo tego, co powiedziałem, jest bardzo dużo kodu na tej stronie!
• @David: FWIW, myślę, że to odpowiada na OP Pytanie ' jest najlepsze, ponieważ pokazuje, jak konwertować między dwiema bazami bez wcześniejszej konwersji reprezentacji oryginału na jakąś formę pośrednią, a następnie konwertowania tego na bazę docelową.
• Niezła próba, ale d nadal znajduje się w bazie 10, więc w efekcie wyodrębniasz mniejszą część n, konwertując ją na podstawę 10, a następnie konwertując ją na żądaną podstawę i zbierając z nich wynik końcowy.

Znam prosty sposób na konwersję bazy, która nie wymaga programu komputerowego. Jest to zdefiniowanie sposób konwersji z dowolnej bazy na podstawę 2 i odwrotnie, a następnie przekształcenie z jednej podstawy na drugą, najpierw przekształcając pierwszą podstawę w podstawę 2, a następnie przekształcając z bazy 2 na drugą. 2 jest tak łatwe do pomnożenia lub podzielenia przez dowolną podstawę.

Aby przekonwertować z dowolnej podstawy na podstawę 2, wszystko, co musisz zrobić, to rozpoznać, że dla dowolnej liczby, jeśli weźmiesz jej notację o podstawie 2 i zaczniesz od 0, a następnie dla każdej cyfry w kolejności od lewej do prawej podwójnie, jeśli ta cyfra jest równa zeru i podwójnie niż dodać 1, jeśli ta cyfra to 1, dostaniesz się do samej liczby. Teraz, mając tę liczbę w dowolnej podstawie, możesz podzielić przez 2 w tej podstawie, aby otrzymać iloraz i resztę. Jeśli reszta to 1, ostatnia cyfra binarna to 1, a jeśli reszta to 0, ostatnia cyfra binarna to 0. Ponownie podziel przez 2. Jeśli reszta to 1, przedostatnia cyfra to 1, a jeśli reszta to 0, przedostatnia cyfra to 0 i tak dalej, aż uzyskasz iloraz 0.

Aby przekonwertować z podstawy 2 na dowolną podstawa, wszystko, co musisz zrobić, to w tej podstawie zacząć od 0, a następnie dla każdej cyfry binarnej od lewej do prawej, podwoić tę podstawę, jeśli ta cyfra wynosi 0, i podwójnie, a następnie dodać 1 do tej podstawy, jeśli ta cyfra wynosi 1.

Komentarze

• 2 is so easy to multiply or divide by in any base. Nie ' t zobacz, że dla nieparzystych baz, które są więcej niż jedna z dowolnej potęgi dwóch (11 i 13, na początek).

Możesz dokonać konwersji z podstawy n na podstawę 10 bez jakiejkolwiek konwersji na jakąś pośrednią podstawę.

Aby na przykład dokonać konwersji z podstawy n do podstawy 9, bierzesz algorytm konwersji do podstawy 10 i zamieniasz „10” na „9”. To samo dotyczy każdej innej bazy.