Matematyka związana z konwersją z dowolnej bazy na dowolną bazę bez przechodzenia przez bazę 10?

Patrzyłem na matematykę dotyczącą konwersji z dowolnej bazy na dowolną bazę. Chodzi bardziej o potwierdzenie moich wyników niż cokolwiek innego. Znalazłem moją odpowiedź na mathforum.org, ale nadal nie jestem pewien, czy mam rację. Mam konwersję z większej bazy na mniejszą bazę w porządku, ponieważ jest to po prostu pierwsza cyfra pomnożona przez bazę, którą chcesz dodać kolejną cyfrę. Mój problem pojawia się podczas konwersji z mniejszej bazy na większą. Robiąc to, rozmawiają o tym, jak trzeba przekonwertować większą bazę, którą chcesz, na mniejszą. Przykładem może być przejście z bazy 4 na bazę 6, w której musisz przekonwertować liczbę 6 na bazę 4, uzyskując 12. Następnie robisz to samo, co podczas konwersji z dużej na małą. Trudność z tym jest taka, że ​​wydaje się, że musisz wiedzieć, co jest jedną liczbą w drugiej bazie. Chciałbym więc wiedzieć, co to jest 6 w bazie 4. Stwarza to duży problem w mojej głowie, ponieważ wtedy potrzebowałbym stołu. Czy ktoś wie, jak to zrobić w lepszy sposób?

Myślałem, że podstawowa konwersja pomoże, ale nie mogę znaleźć żadnej takiej pracy. I ze strony, którą znalazłem, wydaje się, że pozwala ci na konwersję z bazy na bazę bez przechodzenia przez bazę 10, ale najpierw musisz wiedzieć, jak przekonwertować pierwszą liczbę z bazy na bazę. To sprawia, że ​​jest to trochę bezcelowe.

Komentatorzy mówią, że muszę być w stanie przekonwertować literę na liczbę. Jeśli tak, to już to wiem. To jednak nie mój problem. Mój problem polega na przekonwertowaniu dużej bazy na małą bazę. Najpierw muszę przekonwertować numer bazy, który mam, na numer bazy, który chcę. Robiąc to, pokonałem cel, ponieważ jeśli mam możliwość konwersji tych baz na inne, już rozwiązałem swój problem.

Edycja: Zorientowałem się, jak przekonwertować z baz mniejszych lub równych 10 na inne bazy mniejsze lub równe 10. Mogę również przejść z bazy większej niż 10 na dowolną bazę, która ma 10 lub mniej. Problem zaczyna się, gdy konwertujesz z podstawy większej niż 10 na inną bazę większą niż 10. Lub przechodząc z bazy mniejszej niż 10 do bazy większej niż 10. Nie potrzebuję kodu, potrzebuję tylko podstawowej matematyki, która może być zastosowane do kodu.

Wydaje mi się to bardzo podstawowym pytaniem, więc przepraszam, jeśli trochę was nauczę. Najważniejszą rzeczą, którą musisz się tutaj nauczyć, jest to, że liczba nie jest jej cyfrową reprezentacją . Liczba jest abstrakcyjnym obiektem matematycznym, podczas gdy jej cyfrowa reprezentacja jest czymś konkretnym, 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ę). Mylące jest to, że nigdy nie widzisz liczby, ale zawsze jej cyfrowa reprezentacja. W rezultacie myślisz, że liczba jest reprezentacją.

Dlatego poprawnym pytaniem jest nie „jak przekonwertować z jednej bazy na drugą”, ale „jak dowiedzieć się, która liczba jest reprezentowana przez dany ciąg cyfr” i „jak znaleźć cyfrową reprezentację podany numer ”.

Stwórzmy więc dwie funkcje w Pythonie, jedną do konwersji cyfrowej reprezentacji na liczbę, a drugą do odwrotnego działania. Uwaga: kiedy uruchomimy funkcję, Python wydrukuje oczywiście na ekranie liczbę, którą otrzymał w bazie 10. Ale to nie znaczy, że komputer zachowuje liczby w bazie 10 (nie jest). Nie ma znaczenia, w jaki sposób komputer reprezentuje 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 te:

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

Uzbrojony w funkcje konwersji problem można łatwo rozwiązać:

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: my nie przechodzą przez podstawę 10 reprezentacji! Przekształciliśmy bazę na liczbę, a następnie liczbę na bazę c . Numer był$b$$c$ nie reprezentowany. (Właściwie tak było, komputer musiał jakoś to reprezentować, i reprezentował to za pomocą sygnałów elektrycznych i funky, które zdarzają się w układach scalonych, ale z pewnością nie były to 0 i 1).

Myślę, że najlepszym sposobem na zrozumienie tego jest dyskusja z kosmitą (przynajmniej analogicznie).

Definicja jest liczbą w bazie $x$$b$ oznacza, że jest ciągiem cyfr < $x$$<b$ .

Przykłady Ciąg cyfr 10010011011 jest liczbą w podstawie 2, ciąg 68416841531 jest liczbą w podstawie 10, BADCAFE jest liczbą w podstawie 16.

Załóżmy teraz Dorastałem na planecie QUUX gdzie każdy uczy się pracy w przez całe swoje życie, a ja cię poznać, który jest stosowany do podstawowego $q$$b$ . Więc pokaż mi numer i co mam zrobić? Potrzebuję sposobu, aby to zinterpretować:

Definicja Mogę zinterpretować liczbę w podstawie (Uwaga: b jest liczbą w podstawie q ) według następującego wzoru$b$$b$$q$

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

gdzie oznacza ciąg pusty, a ˉ s d oznacza ciąg kończący się w cyfrowym d . Zobacz mój dowód, że dodatek stanowi wprowadzenie do tej notacji.$\epsilon$$\bar s d$$d$

Co się tu stało? Podałeś mi liczbę w podstawie a ja zinterpretowałem ją w podstawie q bez jakiejkolwiek dziwnej filozofii na temat tego, jakie naprawdę są liczby.$b$$q$

Klucz Kluczem do tego jest to, że i + I są funkcjami, które działają na bazowychliczbach q . Są to proste algorytmy zdefiniowane rekurencyjnie na podstawie q liczb (ciągów cyfr).$\times$$+$$q$$q$

---

Może się to wydawać nieco abstrakcyjne, ponieważ przez cały czas używałem zmiennych, a nie liczb rzeczywistych. Załóżmy więc, że jesteś stworzeniem podstawowym 13 (używając symboli ), a ja jestem przyzwyczajony do bazy 7 (co jest znacznie bardziej rozsądne), używając symboli α β γ δ ρ ζ ξ .$0123456789XYZ$$\alpha \beta \gamma \delta \rho \zeta \xi$

Widziałem twój alfabet i zestawiłem go tak:

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

$\beta\xi$

$60Z8$

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

Zacznę od pomnożenia $\beta \zeta \times \beta\xi$

Tabela mnożenia Quuxa

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

$\beta \zeta \times \beta\xi$

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

więc mam 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, o którym była mowa 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}$$

$$[\![60Z8]\!] = \zeta\delta\xi\gamma\rho.$$

---

$q$$b$$q$

To tylko refaktoryzacja (Python 3) Andreja kodu . W kodzie Andreja liczby są reprezentowane przez listę cyfr (skalary), natomiast w poniższym kodzie numery są reprezentowane przez listę 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 wykonać konwersję wartości do reprezentacji w bazie niestandardowej:

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

Aby wykonać 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ę bazy z jednej bazy klienta do innej:

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

Podstawową operacją konwersji podstawowej jest toDigits()operacja odpowiedzi @AndrejBauer. Jednak aby to zrobić, nie ma potrzeby tworzenia liczby w wewnętrznej reprezentacji liczb, co jest w zasadzie konwersją zi do reprezentacji 2 bazowej. Możesz wykonać niezbędne operacje w oryginalnej reprezentacji bazowej.

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ętrzną reprezentacją są cyfry, należy wykonać specjalną funkcję do testowania zera

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

W końcu należy wykonać operację modulo_div, która jest tak naprawdę standardowym podziałem według bazy docelowej, jak uczyliś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 test sprawdzający, 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]

Znam prosty sposób na konwersję podstawową, która nie wymaga programu komputerowego. Jest to poprzez zdefiniowanie sposobu konwersji z dowolnej bazy na bazę 2 i odwrotnie, a następnie pokrycie z jednej bazy na inną bazę poprzez najpierw konwersję z pierwszej bazy na bazę 2, a następnie konwersję z bazy 2 na drugą bazę. 2 jest bardzo łatwy do pomnożenia lub podzielenia przez dowolną bazę.

Aby przekonwertować z dowolnej bazy na bazę 2, wystarczy, że rozpoznasz to dla dowolnej liczby, jeśli weźmiesz jej notację podstawy 2 i zaczniesz od 0, a następnie dla każdej cyfry w kolejności od lewej do prawej podwójnie, jeśli cyfra jest równa zero i podwójnie niż dodaj 1, jeśli ta cyfra to 1, dostaniesz się do tej liczby. Biorąc pod uwagę tę liczbę w dowolnej bazie, możesz podzielić przez 2 w tej bazie, 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, druga ostatnia cyfra to 1, a jeśli reszta to 0, druga ostatnia cyfra to 0 i tak dalej, aż otrzymasz iloraz 0.

Aby przekonwertować z bazy 2 na dowolną bazę, wszystko co musisz zrobić, to w tej bazie rozpocząć od 0, a następnie dla każdej cyfry binarnej przechodzącej od lewej do prawej, podwój w tej bazie, jeśli ta cyfra to 0, a następnie dodaj 1 w tej podstawa, jeśli cyfra to 1.

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

Aby na przykład przekonwertować bazę n na bazę 9, weź algorytm konwersji na bazę 10 i zamień „10” na „9”. To samo dla każdej innej bazy.