O konwersjach w 3 aktach

"Chciałem się dowiedzieć jak sie przelicza liczby rzeczywiste np. liczbę dziesiętną 92.41 w systemie {2, 8, 10, 16} ?", netbull

Proponuję przeprowadzić tok rozumowania, w którym zaczniemy od opisania konwersji [10]->[2], co następnie uogólnimy do przypadku [10]->[y], a w ostatnim kroku (tylko dla hardcorowców) rozpatrzymy przekształcenie [x]->[y].

Ta odrobina formalizmu jest naprawdę konieczna.
Dane wejściowe: Liczba wymierna a>0 zapisana w postaci skończonej reprezentacji pozycyjnego systemu liczbowego o podstawie q.
Wynik: Reprezentacja liczby a w systemie o podstawie p.
[i]q,p są liczbami naturalnymi większymi od 1[/i]

Kilka definicji też nie zaszkodzi:
System liczbowy: sposób zapisywania i nazywania liczb.
Pozycyjny system liczbowy: system zapisywania liczb, w którym jest ustalona podstawa q i pewien skończony zbiór znaków {0,1,...,q-1} zwany cyframi. Liczbę przedstawia się jako ciąg cyfr. Jeśli ciąg ten jest skończony, to mówimy że reprezentacja jest skończona.

Wprowadźmy umowny zapis: (rzeczywisty odrobinę się różni)
1001101 [2] oznacza liczbę zapisaną w systemie dwójkowym,
15302 [6] w systemie o podstawie 6, a ogólnie
56013 [q] oznacza, że liczba jest zapisana w systemie pozycyjnym o podstawie q.

Wartość cyfr w pozycyjnym systemie liczbowym zależy od pozycji np.
92.41 [10] oznacza 910+21+40.1+10.01 czyli
9*(10^1)+2*(100)+4*(10^-1)+1*(10-2).
Ogólnie ciąg a będący liczbą w systemie o podstawie q oznacza sumę a[k]*(q^k).

Temat nie należy do łatwych, dlatego nawet nie próbuję udawać że dostarczam wam gotowego algorytmu. Przedstawiam czysto matematyczny sposób radzenia sobie z tym problemem, który można przy odrobinie wysiłku przełożyć na algorytm i ostatecznie zaimplementować.

Część 1) W świecie zer i jedynek.
Wpierw rozważmy sytuację gdzie q=10, p=2, co oznacza że interesuje nas "konwersja" liczby a z systemu dziesiętnego w system dwójkowy. Wpierw rozważmy szczególnie prostą sytuację w której liczba a jest liczbą naturalną. Bardzo sprawna jest metoda podobna do algorytmu Euklidesa (znajdowanie NWD) np 13 [10] = x [2], szukamy ciągu x:

13=(2)6+1
6=(2)3+0
3=(2)1+1
1=(2)0+1
0=(2)0+0
0=(2)0+0
...

13 [10] = ...001101 [2] = 1101 [2].

Co właściwie robimy? Wykonujemy dzielenie całkowite z resztą, dzielimy zawsze przez 2, a wynik działania b=a/2 zapisujemy w postaci a=b*2+r (r=reszta). Pozostaje pytanie- co jest dzielną? Jest nią w pierwszym działaniu zadana liczba, a potem jest nią część całkowita z poprzedniego dzielenia. Jak odczytać wynik? Wynik jest ciągiem cyfr, odczytujemy go z kolejnych reszt dzielenia, zaczynając od ostatniego działania.
Czyli 13 [10] = ...001101 [2] = 1101 [2].

Ponieważ będziemy się zajmowali liczbą 92.41 to powtórzmy dla: 92 [10] = x [2]

92=(2)46+0
46=(2)23+0
23=(2)11+1
11=(2)5 +1
5=(2)2 +1
2=(2)1 +0
1=(2)0 +1
0=(2)0 +0
0=(2)*0 +0
...

92 [10] = ...001011100 [2] = 1011100 [2]

W takim razie potrafimy już dokonać konwersji a [10] -> a' [2] pod warunkiem że a jest liczbą naturalną. Rozszerzmy nasze możliwości. Niech a należy do liczb wymiernych których reprezentacja dziesiętna jest skończona.

Zanim zaczniemy bezlitośnie przeprowadzać [10] -> [2] upewnijmy się, że wszyscy tak samo rozumiemy zapis pozycyjny z kropką.

Np. ile wynosi w systemie dziesiętnym wartość 0.11 [2] ?
11/2 ? nie.
1/2+1/4? tak, czyli w zapisie pozycyjnym 0.11 [2] = 0.75 [10]

A wartość 0.0101 [2] ?
0*(1/2)+1*(1/4)+0*(1/8)+1*(1/16)=0.25+0.0625,
czyli 0.0101 [2]=0.3125 [10]

Świetnie. Spróbujmy odwrotnie, np
0.25 [10] = 0.01 [2]
0.625 [10] = 0.101 [2]
0.1 [10] = ? hmm, już widać że potrzebujemy metody.

Ponownie zacznę od przykładu, powiedzmy 0.625 [10] = ?
0.625 = 0.625 +0.
0.625*(2) = 1.25 = 0.25 +1
0.25*(2) = 0.5 = 0.5 +0
0.5*(2) = 1 = 0.0 +1
0.0*(2) = 0 = 0.0 +0
0.0*(2) = 0 = 0.0 +0
...

Co właściwie robimy? Mnożymy pewną liczbę zawsze przez 2 a następnie oddzielamy część całkowitą wyniku od części ułamkowej. Co mnożymy? Część ułamkową z poprzedniego wyniku. Jak odczytać rozwiązanie? Jest to ciąg cyfr odpowiadający kolejnym częścią całkowitym przy czym zaczynamy od części całkowitej liczby na wejściu, po której stawiamy kropkę "dziesiętną" (raczej "dwójkową").

0.625 [10] = 0.10100... [2] = 0.101 [2]

Znakomicie! mamy już metodę. Czemu jej nie zastosować do wspomnianego wcześniej 0.1 [10] = x [2] ?

                         0.1 = <b>0.1</b> + 0.

0.1*(2) = 0.2 = 0.2 + 0
0.2*(2) = 0.4 = 0.4 + 0
0.4*(2) = 0.8 = 0.8 + 0
0.8*(2) = 1.6 = 0.6 + 1
0.6*(2) = 1.2 = 0.2 + 1
0.2*(2) = 0.4 = 0.4 + 0
0.4*(2) = 0.8 = 0.8 + 0
0.8*(2) = 1.6 = 0.6 + 1
0.6*(2) = 1.2 = 0.2 + 1
... itd.

0.1 [10] = 0.00011(0011) [2] = 0.0(0011) [2]
Zasadzka! Jak widać, wychodząc ze skończonej reprezentacji możemy otrzymać wynik nie będący taką reprezentacją. Jest to kłopot z punktu widzenia implementacji, gdyż prawdopodobnie będziemy musieli posłużyć się pewnym przybliżeniem, niemniej matematycznie wszystko się zgadza.

Jesteśmy gotowi ostatecznie rozwiązać 92.41 [10] = x [2]

           92.41 = 0.41 + 92 [10] = 0.41 + 1011100 [2]

0.41*(2) = 0.82 = 0.82 + 0
0.82*(2) = 1.64 = 0.64 + 1
0.64*(2) = 1.28 = 0.28 + 1
0.28*(2) = 0.56 = 0.56 + 0
0.56*(2) = 1.12 = 0.12 + 1
0.12*(2) = 0.24 = 0.24 + 0
0.24*(2) = 0.48 = 0.48 + 0
0.48*(2) = 0.96 = 0.96 + 0
0.96*(2) = 1.92 = 0.92 + 1
0.92*(2) = 1.84 = 0.84 + 1
0.84*(2) = 1.68 = 0.68 + 1
0.68*(2) = 1.36 = 0.36 + 1
0.36*(2) = 0.72 = 0.72 + 0
0.72*(2) = 1.44 = 0.44 + 1
0.44*(2) = 0.88 = 0.88 + 0
0.88*(2) = 1.76 = 0.76 + 1
0.76*(2) = 1.52 = 0.52 + 1
0.52*(2) = 1.04 = 0.04 + 1
0.04*(2) = 0.08 = 0.08 + 0
0.08*(2) = 0.16 = 0.16 + 0
0.16*(2) = 0.32 = 0.32 + 0
0.32*(2) = 0.64 = 0.64 + 0

0.64*(2) = 1.28 = 0.28 + 1
... itd. (część ułamkowa 0.28 już była wcześniej ...)

He he, trochę tego jest (posłużyłem się językiem programowania Haskell, bo sam bym się pomylił kilka razy).

Ostatecznie:
92.41 [10] = 1011100.01(10100011110101110000) [2]

(nawiasem mówiąc długość najdłuższego możliwego okresu w tym przypadku to 100 cyfr)

Na koniec tej części wspomnę tylko o tym co przemilczałem. Otóż gdy odczytujemy wynik, przepisujemy kolejne części całkowite. Niemniej są one zapisane w postaci dziesiętnej, więc musimy zamienić je na postać dwójkową. Widać to w powyższym przykładzie gdy wpierw odczytujemy 92 [10]. Wcześniej nie musieliśmy się tym przejmować, gdyż szczęśliwie 1 [10] = 1 [2], a nie mieliśmy innych części całkowitych niż 1 lub 0.

Czemu ograniczać się do systemu dwójkowego?, starożytni Babilończycy posługiwali się systemem sześćdziesięciątkowym (którego pozostałością jest używany obecnie podział godziny na minuty i sekundy). Podróż do tego systemu opiszę w następnej części.

Część 2) Babilon.
Najwyższy czas odpowiedzieć na pytanie postawione w temacie.
Czyli teraz q=10, p jest dowolne.

Ponieważ będę rozważał system sześćdziesiątkowy, nie ma sensu używać liter (i tak by ich nie starczyło), dlatego cyfry będę oznaczał jako kolejne elementu zbioru który jest "alfabetem".

np. {12}{56} [60] = 1260+561= 776 [10]

przypominam że liczba w naszych rozważaniach jest traktowana jako napis (niekoniecznie skończony) nad niepustym alfabetem cyfr.

Ponownie rozważmy wpierw sytuację w której nasza liczba a jest całkowita. Jak obliczyć reprezentację a [10] w dowolnym innym systemie? Bardzo podobnie jak poprzednio:
np 92 [10] = ? [60]

92 = (60)1+32
1 = (60)0+1
0 = (60)0+0
0 = (60)0+0
...

odczytujemy od tyłu:

92 [10] = ... {0}{0}{1}{32} [60] = {1}{32} [60]

Czyli metoda polega na dzieleniu całkowitym z resztą przez liczbę p.

A jeśli liczba a jest wymierna?
np. 92.41 [10] = ? [60]

                           92.41=0.41+(92 [10]->{1}{31} [60] )

0.41*(60) =24.6=0.6 +(24 [10]->{24} [60] )
0.6*(60) =36= 0 +(36[10]->{36} [60] )
0= 0 + 0
...

92.41 [10] = {1}{31}.{24}{36} [60]

Koniec.

Został tylko przypadek dla prawdziwych hardcorowców, czyli q i p dowolne.

Część 3) Tylko dla hardcorowców
Ostrzegam, nie będzie łatwo. Będzie hardcorowo (1000 razy bardziej niż na stronach porno).

Wracamy do podstaw: Pozycyjny system liczbowy posiada ustaloną podstawę q i pewien skończony zbiór znaków {0,1,...q-1} zwanych cyframi.

Cyfra jest więc znakiem czyli literą. Natomiast czym jest liczba w pozycyjnym systemie liczbowym? Jest słowem nad alfabetem cyfr.

Jest rzeczą absolutnie kluczową, abyśmy wszyscy zgodzili się z tym że cyfra nie jest liczbą. Cyfra nie ma wartości liczbowej.

Następnie rozważmy kilka prostych operacji arytmetycznych.
a+b; a-b; a*b; a/b (dla b!=0)

jeśli a,b należą do dziesiętnego systemu pozycyjnego [10], nie mamy absolutnie żadnych trudności przy podawaniu wartości tych wyrażeń.

W jaki sposób wykonamy złożone dzielenie dwóch liczb dziesiętnych? Zrobimy to za pomocą algorytmu dzielenia "pod kreską". (Al Chwarizmi)

Stawiam pytanie - czy jeśli a,b należą jednocześnie do dowolnego systemu pozycyjnego [w], to czy jesteśmy w stanie podać wartość powyższych wyrażeń? Spróbujmy. niech [w]=[5], a=24[5], b=13[5].

Będziemy liczyć w analogiczny sposób do działań w systemie dziesiętnym, z tym że o ile tam przenosiliśmy "pełne" dziesiątki, to w tym przypadku będziemy przenosić "pełne" piątki:

24 [5]
+13 [5]
42 [5]

24 [5]
-13 [5]
11[5]

24 [5]
*13 [5]
132
24
422 [5]

1
24 :13 [5]
-13
11

Zwracam uwagę, że w przypadku dzielenia musimy być w stanie porównywać liczby (czyli wskazywać która z nich jest większa).

W takim razie otrzymaliśmy:
24[5]+13[5]=42[5]
24[5]-13[5]=11[5]
24[5]*13[5]=422[5]
24[5]/13[5]=1[5] reszty 11[5]

Czyli jesteśmy w stanie wykonać działania +-*/ dla dwóch liczb w dowolnym systemie pozycyjnym [w]. Nie musimy robić tego sprawnie (jesteśmy tak bardzo przywiązani do [10] że zmiana systemu przychodzi nam z wielkim trudem), wystarczy że znamy algorytm i jesteśmy w stanie przenieść go na komputer.

Będziemy rozważać ogólną klasę konwersji typu:
a[q]->a[p] wpierw niech a należy do liczb naturalnych > 1.

Oto nasze pierwsze zadanie:

• liczba 32 jest zapisana w systemie siódemkowym, jaka jest jej postać w systemie jedenastkowym.

Hura ! jesteśmy wolni od systemu [10]. Wygląda na to, że system dziesiętny mógłby zginąć w katastrofie, a my i tak potrafilibyśmy odpowiedzieć na powyższe pytanie.

Czy jest tak na pewno? Zapiszmy nasze zadanie w postaci formalnej:
32[7]->x[11]

Widzicie problem? Chociaż zamieniamy liczbę z systemu siódemkowego na system jedenastkowy, to wcale nie jesteśmy wolni od systemu dziesiętnego. Pytanie - gdzie się on pojawia. W którym miejscu go używamy ? Spróbujcie odpowiedzieć samodzielnie ...

Otóż gdy mówimy system "siódemkowy" albo "jedenastkowy", to używamy systemu dziesiętnego. Totalny Koszmar ! Makabra ! Barbara Streisand ! (he he). Jeśli wszyscy ludzie zapomną o tym co to jest system dziesiętny, to powyższe zadanie będzie nierozwiązywalne, gdyż nikt nie będzie wiedział co znaczy system "siódemkowy" (ponieważ jego nazwa jest liczbą dziesiętną).

Drogi czytelniku, jeśli właśnie uznałeś że jest ciężko, to wiedz że zaraz będzie jeszcze gorzej.

32 [7]-> x [11]

Świadomi tego, że tak naprawdę operujemy w trzech systemach, mianowicie [7], [11] i domyślnie systemie dziesiętnym w którym nazywamy "7" i "11", spróbujmy rozwiązać powyższe zadanie.

pierwszą rzeczą jest wykonanie prostej konwersji pomocniczej:
11[10]->x[7]

krótkie przypomnienie części 2:
11=(7)*1+4
1=(7)*0+1

odczytujemy od końca:
11[10]=14[7]

Następnie będziemy wykonywać dzielenie z resztą w systemie [7] (właśnie dlatego wspomniałem wcześniej o działaniach arytmetycznych w systemach nie-dziesiętnych). Dzielnikiem będzie 14[7], natomiast dzielną będzie w pierwszym kroku zadana liczba 32[7], a potem dzielną będzie część całkowita poprzedniego dzielenia.

32[7]=(14[7])*2[7]+1[7]
2[7]=(14[7])*0[7]+2[7]

odczytujemy od końca:
32[7]=21[11]

Spróbujmy uogólnić nasz sposób rozwiązania
a[q]->x[p]

1)p[10]->p[q]
2)dzielenie z resztą przez p[q]
3)odczytanie wyniku jako ciągu reszt czytanych od końca.

Szybkie i wydajne ... Jeśli jesteście zadowoleni z wyniku, to z pewnością następny przykład zmieni wasz nastrój. Spróbujcie go rozpisać samodzielnie.

1021[3]->[7]

rozwiązanie:

1. 7[10]=21[3]

1021[3]=(21[3])*11[3]+20[3]
11[3]=(21[3])*0[3]+11[3]

1021[3]=(11[3])(20[3]) [7] nie do końca to, o co nam chodziło ...

To jest najtrudniejszy moment całego wywodu. Musimy ponownie sięgnąć do podstaw. Czego się spodziewamy jako rozwiązania? Liczby. Czym jest liczba? jest słowem nad alfabetem cyfr.

musimy jedynie zinterpretować (11[3]) oraz (20[3]) jako cyfry. Obliczeniowo sprowadza się to do policzenia wartości w systemie dziesiętnym, czyli:
11[3]='4'
20[3]='6'
przy czym to nie jest kolejna konwersja, tylko zamiana cyfr. Skąd to się bierze? Otóż wyjściowy alfabet [3] jest mniej liczny od alfabetu [7], dlatego musimy go sztucznie rozszerzyć do takiego przejściowego alfabetu: {0,1,2,10,11,12,20}

wynik:
1021[3]=(11[3])(20[3]) [7]=46[7]

W tym momencie na pewno wszyscy myślą "kapustka oszalał, po prostu postanowił poszpanować i zrobić nam Barbarę Streisand z mózgu, wracam do swojej metody przeliczania wpierw na system dziesiętny, a potem na docelowy system". Zapewniam że cała ta dotychczasowa zabawa nie jest bezzasadna, na samym końcu pokażę dlaczego zamiana na "pomostowy" system dziesiętny w pewnych przypadkach jest grubym błędem.

Umiemy więc (aczkolwiek w pokrętny sposób) dokonać konwersji:
a[q]->a[p] dla a będącego liczbą naturalną > 1.

1)p[10]->p[q]
2)dzielenie z resztą przez p[q]
3)odczytanie wyniku jako ciągu reszt "zamienianych na system dziesiętny" i czytanych od końca.

zakręcone. Naturalne jest rozszerzenie problemu na liczby wymierne o skończonej reprezentacji:

32.4[7] -> x[11]

11[10]=14[7]

                               32.4[7]=0.4[7] + (32[7]->21[11])

0.4[7]*14[7]=6.2[7]=0.2[7] + (6[7]->6[11])
0.2[7]*14[7]=3.1[7]=0.1[7] + (3[7]->3[11])
0.1[7]*14[7]=1.4[7]=0.4[7] + (1[7]->1[11])
0.4[7] już było ...

32.4[7]=21.(631)[11]

Mam nadzieję że wytrwali czytelnicy doczytali do tego miejsca, gdyż było warto: oto przykład który uzasadnia całe to skomplikowane rozumowanie.

0.1[3]->x[6]

Pierwsza zaskakująca rzecz w tym przykładzie, to fakt że ułamek 1/3 ma skończone roziwnięcie w systemie pozycyjnym trójkowym.

0.33333(3)[10] = 0.1[3]

tym razem (wyjątkowo) obliczenia nie będą trudne:

1. 6[10]=20[3]

2.                                          0.1[3]=0.1[3] + (0.[3]->0.[6])
   

0.1[3]*(20[3]) = 2[3] = 0.0[3] + (2[3]->2[6])

czyli rozwiaznie:
0.1[3]=0.2[6]

piękna skończona reprezentacja! Zastanówmy się co by się stało, gdybyśmy przeszli przez "pomostową" reprezentację dziesiętną, wtedy w pierwszym kroku byśmy zamienili 0.1[3] na [10], czyli:
0.1[3]->0.333333(3)[10]

Czy widzicie problem? Zupełnie niepotrzebnie wpadamy w nieskończoną reprezentację dziesiętną. Właściwie to nawet nie za bardzo wiadomo co teraz trzeba zrobić, (prawdopodobnie musimy przybliżyć naszą liczbę).

Metoda którą tutaj zaproponowałem, jest trudna i mało intuicyjna, nie nadaje się do liczenia "na piechotę". Niemniej jeśli kiedykolwiek staniecie przed problemem programistycznej konwersji z dowolnego systemu [q] na dowolny system [p], polecam ją, gdyż jest generalnie szybsza (wynika to z faktu, że chociaż dokonujemy dwóch konwersji, to ta wstępna jest bardzo prosta) oraz jest niezawodna (gdyż unikamy wpadania w zbędną nieskończoną reprezentację).

Szczerze gratuluję tym hardcorowcom, którzy dotrwali do końca (nie sądzę żeby ktokolwiek to zrobił)

Pozdrawniam.