Wszyscy dobrze znamy zaokrąglanie liczb w systemie dziesiętnym. W systemie binarnym działa ono podobnie, ale i tak potrafi wprowadzić zamieszanie. Największym wyzwaniem są ułamki. Nie od razu widać na przykład, dlaczego ułamek 0.11101 zaokrąglony do 2 miejsc po przecinku daje liczbę całkowitą 1. Ten artykuł wyjaśnia ogólne reguły zaokrąglania ułamków binarnych oraz to, skąd te reguły pochodzą. Te same reguły stosują się do zaokrąglania binarnych liczb całkowitych.

Standard IEEE-754 definiuje pięć metod zaokrąglania i większość z nich jest dość prosta. Dwie pierwsze zaokrąglają do najbliższej wartości (remis do parzystej i remis od zera); pozostałe nazywamy zaokrągleniami kierunkowymi: do zera, do plus nieskończoności i do minus nieskończoności. Reguły te najłatwiej zrozumieć na przykładzie systemu dziesiętnego:

Zaokrąglenia kierunkowe są bardzo proste. W tym artykule przyjrzymy się dokładnie regule „do najbliższej; remis do parzystej”. Jest to tryb domyślny dla binarnej liczby zmiennoprzecinkowej i zalecany tryb domyślny dla dziesiętnej. I zwykle nie jest tak łatwy do zrozumienia jak zaokrąglenia kierunkowe.

Ogólna reguła zaokrąglania ułamków binarnych do n-tego miejsca każe sprawdzić cyfrę następującą po n-tym miejscu. Jeśli jest to 0, liczbę zawsze zaokrąglamy w dół. Jeśli natomiast cyfra ta wynosi 1 i któraś z kolejnych cyfr również jest 1, liczbę zaokrąglamy w górę. Jeśli jednak wszystkie kolejne cyfry to 0, trzeba zastosować regułę rozstrzygania remisów, a zwykle jest nią „remis do parzystej”. Reguła ta mówi, że należy zaokrąglić do liczby, która ma 0 na n-tym miejscu.

Aby zobaczyć te reguły w działaniu, zaokrąglijmy kilka liczb do 2 miejsc po przecinku pozycyjnym:

• 0.11001 — zaokrągla się w dół do 0.11, ponieważ cyfra na 3-cim miejscu to 0
• 0.11101 — zaokrągla się w górę do 1.00, ponieważ cyfra na 3-cim miejscu to 1 i dalej występują cyfry 1 (5-te miejsce)
• 0.11100 — stosujemy regułę rozstrzygania remisów „remis do parzystej” i zaokrąglamy w górę, ponieważ cyfra na 3-cim miejscu to 1, a wszystkie kolejne cyfry to 0.

Jeśli jesteś podobny do mnie, to skąd biorą się te reguły, może na pierwszy rzut oka nie być zbyt jasne. Wygląda na to, że żaden artykuł o zaokrąglaniu, jaki czytałem, nie wyjaśnia tych reguł szczegółowo i przy użyciu reprezentacji wizualnej — a właśnie tego moim zdaniem potrzeba do jasnego wyjaśnienia.

Opcje zaokrąglenia

Kiedy zaokrąglamy liczby, musimy wybrać jedną z dwóch możliwych opcji: albo zaokrąglić w dół do najbliższej liczby mniejszej od pierwotnej, albo w górę do najbliższej większej. Te dwie liczby nie powinny mieć więcej miejsc po przecinku niż wynik zaokrąglenia.

Aby pokazać, jak je znaleźć, zaokrąglijmy liczbę dziesiętną 0.42385 do 2 miejsc. Do jakich liczb można ją zaokrąglić? Łatwo to zobaczyć, umieszczając ją na osi liczbowej wraz z ułamkami mającymi dwa miejsca:

Diagram pokazuje, że nasza pierwotna liczba mieści się między 0.42 a 0.43. Ponieważ 0.42385 = 0.42 + 0.00385, a naszą mniejszą liczbą jest 0.42, możemy wywnioskować, że aby znaleźć liczbę mniejszą, wystarczy obciąć część ułamkową po drugim miejscu. Aby zaś znaleźć liczbę większą, możemy wziąć już wyznaczoną liczbę mniejszą i zwiększyć ją o jeden ULP, dodając 1 do cyfry na ostatnim miejscu. Albo, patrząc z innej strony, oznacza to, że do mniejszej liczby powinniśmy dodać 0.01 — czyli 1 pomnożone przez 10 do potęgi minus 2, ponieważ zaokrąglamy do 2 miejsc. Gdybyśmy zaokrąglali do 3 miejsc, wzięlibyśmy liczbę mniejszą dla 3 miejsc i dodali 1 pomnożone przez 10 do potęgi minus 3.

Możemy uogólnić tę regułę znajdowania opcji zaokrąglenia:

Zaokrąglając liczbę ułamkową do n miejsc, najpierw znajdź liczbę mniejszą, odrzucając część ułamkową po n-tym miejscu, a następnie użyj jej do znalezienia liczby większej, dodając do niej jeden ULP — 1 pomnożone przez podstawę systemu liczbowego do potęgi n.

Teraz znajdźmy opcje zaokrąglenia dla liczby binarnej 0.11011. Znów zaokrąglamy do 2 miejsc. Idąc tym samym schematem co dla ułamków dziesiętnych, otrzymujemy 0.11 jako liczbę mniejszą, ponieważ 0.11011 = 0.11 + 0.00011. Następnie możemy znaleźć liczbę większą, dodając 0.01, czyli 1 pomnożone przez 2 do potęgi minus 2, ponieważ używamy systemu binarnego, więc podstawa wynosi 2, a zaokrąglamy do 2 miejsc. Wynikiem tego obliczenia jest 0.11+0.01=1.00.

Szukanie najkrótszej odległości

Reguła zaokrąglania „do najbliższej” mówi, że powinniśmy zaokrąglić do tej liczby, której różnica z liczbą pierwotną jest najmniejsza. Na osi liczbowej oznacza to, że odległość między liczbą pierwotną a jedną z dwóch możliwych liczb zaokrąglonych jest najmniejsza. Jeśli więc umieścimy liczbę pierwotną i możliwe opcje na osi liczbowej i oznaczymy odległości jako x, musimy ustalić, które x jest mniejsze:

Zrobienie tego przez odejmowanie jest całkiem proste:

$$x_1 = |0.11 - 0.110110| = 0.000110$$ $$x_2 = |1.00 - 0.110110| = 0.001010$$

Widać tu wyraźnie, że x1 jest mniejsze niż x2, a zatem powinniśmy zaokrąglić do 0.11. Ale co, gdybyśmy chcieli zaokrąglić nieskończony ułamek binarny? W takim przypadku odejmowanie nie byłoby już tak prostą operacją. Jak się okazuje, istnieje znacznie łatwiejsze podejście.

Porównanie ze środkiem

Innym, łatwiejszym podejściem jest ustalenie, czy liczba pierwotna jest większa, czy mniejsza od środka między dwiema opcjami zaokrąglenia. Spójrzmy na ten diagram:

Nietrudno wywnioskować, że jeśli liczba jest większa od środka, to jest bliżej większej liczby zaokrąglonej, w przeciwnym razie jest bliżej mniejszej.

Jak więc znaleźć ten środek między dwiema opcjami zaokrąglenia? Wiemy, że odległość między 0.11 a 1.00 wynosi 0.01. Wystarczy więc znaleźć połowę z 0.01 i dodać ją do liczby mniejszej. Połowa to 0.001, a dodana do liczby mniejszej daje 0.111 = 0.11 + 0.001. W istocie jest to równoważne z samym dopisaniem 1 na końcu liczby mniejszej. Oto diagram z odpowiednimi liczbami naniesionymi na oś liczbową:

Pozostaje już tylko porównać liczbę pierwotną ze środkiem:

$$0.11011 > 0.111 \quad or \quad 0.11011 < 0.111$$

Stosując bitowe porównanie w porządku leksykograficznym, widać wyraźnie, że 0.11011 jest mniejsze od środka. Powinniśmy więc zaokrąglić w dół do 0.11 — i jest to ten sam wynik, który otrzymaliśmy, licząc odległości.

Remis do parzystej

Czasem odległość między liczbą pierwotną a każdą z opcji zaokrąglenia jest równa, więc reguły „do najbliższej” nie da się zastosować. Załóżmy, że zaokrąglamy liczbę 0.11011 do 4 miejsc po przecinku pozycyjnym. Wiemy, że musimy znaleźć dwie opcje zaokrąglenia oraz środek do porównania. Aby znaleźć najpierw liczbę mniejszą, po prostu obcinamy pozostałe cyfry po 4-tym miejscu, co daje nam 0.1101. Teraz możemy znaleźć środek, dopisując 1 na końcu liczby mniejszej — otrzymujemy 0.11011. I na koniec znajdźmy liczbę większą, dodając 1 ULP do liczby mniejszej: 0.1101+0.0001 = 0.1110.

Mamy zatem:

• liczba pierwotna — 0.11011
• liczba do zaokrąglenia w dół — 0.1101
• liczba do zaokrąglenia w górę — 0.1110
• środek między opcjami zaokrąglenia — 0.11011.

Przechodząc przez porównanie bit po bicie, widzimy, że liczba pierwotna i środek są równe, co pokazuje, że liczba pierwotna leży dokładnie pomiędzy dwiema opcjami zaokrąglenia. To dokładnie ta sytuacja, w której musimy zastosować drugą część reguły — „remis do parzystej”. Liczba binarna jest parzysta, jeśli kończy się na 0, więc przy naszych opcjach zaokrąglenia parzysta jest liczba większa i reguła nakazuje zaokrąglić w górę, do 0.1110.

Wyprowadzanie ogólnych reguł zaokrąglania

Czy naprawdę musimy porównywać cyfry na wszystkich miejscach? Jak można się domyślić z reguł przedstawionych na początku artykułu — nie musimy. W poprzednim akapicie pokazałem, że liczba środkowa zawsze kończy się na 1 na miejscu n+1, gdzie n to liczba miejsc, do której zaokrąglamy. Liczba pierwotna i środek zawsze będą równe aż do miejsca n+1 — oznacza to, że właśnie od tego miejsca powinniśmy zacząć porównywanie.

Ogólne reguły zaokrąglania przedstawione na początku artykułu biorą się więc z porównania liczby pierwotnej ze środkiem między dwiema opcjami zaokrąglenia. Powtórzę je tutaj jeszcze raz:

Ogólna reguła zaokrąglania do n-tego miejsca każe sprawdzić cyfrę następującą po n-tym miejscu. Jeśli jest to 0, liczbę zawsze zaokrąglamy w dół. Jeśli natomiast cyfra ta wynosi 1 i któraś z kolejnych cyfr również jest 1, liczbę zaokrąglamy w górę. Jeśli jednak wszystkie kolejne cyfry to 0, trzeba zastosować regułę rozstrzygania remisów, a zwykle jest nią „remis do parzystej”. Reguła ta mówi, że należy zaokrąglić do liczby, która ma 0 na n-tym miejscu.