Ułamki

Jak reprezentować liczby rzeczywiste? W tym przypadku mamy jeszcze większy problem, gdyż nie dość, że jest ich nieskończenie wiele, nie dość, że tworzą zbiór gęsty, to jeszcze jest ich nieprzeliczalnie wiele. Stoimy zatem przed problemem, jak wybrać skończony ich podzbiór tak, żeby jak najlepiej reprezentował nasze potrzeby. Działania, które będziemy wykonywali dadzą wyniki tylko w ramach tego podzbioru, więc może się zdarzyć, że wynik będzie odbiegał od rzeczywistości. Fenomen ten znamy dobrze z doświadczeń z kalkulatorami: zwykle, jeśli najpierw podzielimy jedynkę przez trzy, a potem pomnożymy wynik przez 3, otrzymamy coś w rodzaju \( 0,99999999 \). Błąd się wziął stąd, że w zestawie wartości reprezentowanych przez kalkulator brakuje jednej trzeciej. Zamiast niej mamy jej przybliżenie \( 0,33333333 \), które pomnożone przez \( 3 \) daje właśnie to, co widzimy na wyświetlaczu. Dzieje się tak nie tylko dlatego, że kalkulatory są prymitywnymi urządzeniami. Duże komputery cierpią na te same dolegliwości (choć akurat powyższe działanie mogą wykonać lepiej). Zajmiemy się teraz doborem właściwego podzbioru reprezentującego liczby rzeczywiste (a tak naprawdę wymierne, bo to takich wartości nasz podzbiór się będzie ograniczał).

Zacznijmy od reprezentacji binarnej ułamków. Podobnie jak w systemie dziesiętnym korzystamy z ujemnych potęg dziesiątki po przecinku, tak tu będziemy rozważali binarne rozwinięcia ułamków za pomocą ujemnych potęg dwójki. Zatem po kropce binarnej, oddzielającej część całkowitą od ułamkowej, kolejne pozycje będą odpowiadały bitom reprezentującym kolejno wartości \( \frac{1}{2},\frac{1}{4},\frac{1}{8},\ldots \). Liczba \( \frac{1}{2} \) będzie zatem miała przedstawienie \( 0.1 \), liczba \( \frac{1}{4} \) będzie miała przedstawienie \( 0.01 \), liczba \( \frac{3}{4} \) będzie miała przedstawienie \( 0.11 \) itd. Wszystko jest proste, jeśli w mianowniku ułamka są potęgi dwójki. Wystarczy bowiem zapisać licznik binarnie, a następnie kropkę binarną przesunąć w prawo o tyle pozycji, ile wynosi potęga dwójki w mianowniku. Na przykład \( \frac{5}{16} \) ma przedstawienie \( 0.0101 \): jest to po prostu \( 5 \) czyli \( 101 \) przesunięte o 4 pozycje w prawo.

Co jednak począć z mianownikami niebędącymi potęgami dwójki? W systemie dziesiętnym mamy podobny problem. Jeśli jedynymi dzielnikami mianownika są \( 5 \) i \( 2 \), to otrzymujemy skończone rozwinięcie ułamka. W przeciwnym razie rozwinięcia są nieskończone i dla liczb wymiernych okresowe (można się umówić, że wszystkie rozwinięcia liczb wymiernych są okresowe, tylko niektóre mają okres złożony z samego zera!).

Jak zatem znajdować binarne rozwinięcia ułamków wymiernych? Oto algorytm, którego nieskomplikowany (ale i nieoczywisty) dowód poprawności można przeprowadzić indukcyjnie, i który działa również dla systemu dziesiętnego (oczywiście rolę dwójki pełni tam dziesiątka) – proszę sprawdzić.

Algorytm przedstawiania ułamka \( u \) w binarnym systemie pozycyjnym. 
Założenie: \( 0\le u  < 1 \). 
Napisz \( 0 \).. Kolejne cyfry rozwinięcia binarnego będziemy generować w następujący sposób: 
Dopóki otrzymujesz nienapotkane wcześniej wartości \( u \) wykonuj 
1. Pomnóż \( u \) przez 2 
2. Jeżeli otrzymana wartość jest mniejsza od 1, to dopisz cyfrę \( 0 \) 
3. Jeżeli otrzymana wartość jest równa co najmniej 1, dopisz cyfrę  \( 1 \) i odejmij od wyniku 1. Z chwilą, gdy powtórzy się wartość \( u \), zakończ procedurę; wypisany ciąg jest okresowy, a jego okresem jest ciąg bitów między powtórzeniami.

bity	wartość
0. 0 1 0 0	\( \frac{2}{7} \) \( \frac{4}{7} \) \( \frac{1}{7} \) \( \frac{2}{7} \) \( \frac{4}{7} \)

Binarne rozwinięcie \( \frac{2}{7}=0.(010) \)

Widzimy, że \( \frac{2}{7} \) ma rozwinięcie binarne \( 0.010010010\ldots \). Okresem jest \( (010) \).
Spróbujmy znaleźć jeszcze rozwinięcie binarne dla \( \frac{1}{10} \).

bity	wartość
0. 0 0 0 1 1	\( \frac{1}{10} \) \( \frac{2}{10} \) \( \frac{4}{10} \) \( \frac{8}{10} \) \( \frac{6}{10} \) \( \frac{2}{10} \)

Binarne rozwinięcie \( \frac{1}{10}=0.0(0011) \)

Zauważmy jeden wstrząsający fakt: nawet tak prosta liczba jak \( \frac{1}{10} \) ma nieskończone binarne rozwinięcie okresowe. Oczywiście takie rozwinięcia mają także \( \frac{2}{10},\frac{3}{10},\frac{4}{10}\frac{6}{10}\frac{7}{10},\frac{8}{10}\frac{9}{10} \). I rzeczywiście, gdy chcemy w komputerze (a nawet w kalkulatorach) reprezentować \( \frac{1}{10} \), jesteśmy zmuszeni do zaokrąglenia tej wartości i w rzeczywistości otrzymujemy tylko coś koło jednej dziesiątej. Przynajmniej tak to widzi komputer.