Ми всі знайомі з округленням чисел у десятковій системі числення. Округлення в двійковій системі аналогічне, але все одно може викликати певну плутанину. Найбільшою проблемою є округлення дробів. Наприклад, може бути не відразу зрозуміло, чому округлення дробу 0,11101 до 2 знаків після коми призводить до цілого числа 1. У цій статті пояснюються загальні правила округлення двійкових дробів і пояснюється, звідки вони беруться. Ці ж правила застосовуються до округлення двійкових цілих чисел.

Існує п’ять методів округлення, як визначено стандартом IEEE-754, і більшість із них досить прості. Перші два округлюються до найближчого значення (порівняється з рівнем і зрівняється з нулем); інші називаються спрямованими округленнями: до нуля, до позитивної нескінченності та до негативної нескінченності. Ці правила легше зрозуміти на прикладі десяткової системи:

Спрямовані округлення досить прості. У цій статті ми детально розглянемо ‘округлення до найближчого; зв’язки з парним’ правилом. Це режим за замовчуванням для двійкових чисел з плаваючою комою та рекомендований режим за замовчуванням для десяткових. І зазвичай це не так легко зрозуміти, як спрямовані округлення.

У наведених нижче прикладах використовуються невід’ємні числа. Для від’ємного значення округлення до найближчого округліть його величину, а потім відновіть знак; округлення величини в більшу сторону робить результат зі знаком більш негативним.

Загальне правило при округленні двійкових дробів до n-го розряду наказує перевіряти цифру, що стоїть після n-го розряду в числі. Якщо це 0, то число завжди слід округляти в меншу сторону. Якщо натомість цифра дорівнює 1, а будь-яка з наступних цифр також дорівнює 1, тоді число слід округлити в більшу сторону. Проте, якщо всі наступні цифри є 0, тоді має бути застосовано правило визначення рівності, і зазвичай це «порівняється з парним». Це правило говорить, що ми повинні округлити до числа, яке має 0 на n-му місці.

Щоб продемонструвати ці правила в дії, давайте округлимо деякі числа до 2 знаків після точки основи:

• 0,11001 — округляє до 0,11, тому що цифра на 3 місці 0
• 0,11101 — округлює до 1,00, оскільки цифра на 3-му місці дорівнює 1, а наступні цифри 1 (5-е місце)
• 0,11100 — застосуйте правило розриву рівності й округліть у більшу сторону, оскільки цифра на 3-му місці дорівнює 1, а всі наступні цифри — 0.

Якщо ви схожі на мене, то з першого погляду може бути не дуже зрозуміло, звідки беруться ці правила. Здається, жодна стаття про округлення, яку я читав, не пояснює ці правила дуже детально за допомогою візуального представлення — але це саме те, що, на мою думку, потрібно для чіткого пояснення.

Параметри округлення

Коли ми округлюємо числа, ми маємо вибрати один із двох можливих варіантів: або округлити до найближчого числа, яке є меншим за вихідне, або округлити до найближчого числа, яке є більшим. Ці два числа не повинні мати більше знаків після коми, ніж отримане після округлення число.

Щоб продемонструвати, як ми ідентифікуємо ці числа, давайте округлимо десяткове число 0,42385 до 2 знаків. До яких чисел його можна округлити? Це легко побачити, якщо ми розмістимо це число на числовій прямій разом із дробовими числами, які мають два місця:

Ця діаграма показує, що наше вихідне число знаходиться в межах від 0,42 до 0,43. Оскільки 0,42385 = 0,42 + 0,00385, а наше найменше число дорівнює 0,42, ми можемо зробити висновок, що, щоб знайти менше число, ми можемо просто обрізати дробову частину після другого місця. А щоб знайти більше число, ми можемо використати вже визначене нижче число та збільшити його на один ULP, додавши 1 до останнього розряду. Або, дивлячись під іншим кутом, це означає, що ми повинні додати до нижчого числа 0,01 — яке 1 помножено на 10 у від’ємному ступені 2, оскільки ми округляємо до 2 розрядів. Якби ми округлили до 3 знаків, ми б взяли менше число для 3 знаків і додали б 1, помножене на 10, до від’ємного ступеня 3.

Ми можемо узагальнити це правило пошуку варіантів округлення:

Для невід’ємного дробу, округленого до n розрядів в основі b, обріжте після n-го розряду, щоб знайти молодшого кандидата. Верхній кандидат на одну одиницю на останньому місці (ULP) вище: додайте b⁻ⁿ. Якщо вихідне число вже є точним із такою точністю, залиште його без змін.

Тепер давайте знайдемо варіанти округлення для двійкового числа 0,11011. Знову округлимо до 2 місць. Якщо ми дотримуємося тієї самої схеми, описаної для десяткових дробів, ми отримаємо 0,11 для меншого числа, оскільки 0,11011 = 0,11 + 0,00011. Тоді ми можемо знайти більше число, додавши 0,01, яке 1 помножено на 2 до від’ємного степеня 2, оскільки ми використовуємо двійкову систему, отже, основа дорівнює 2, і округливши до 2 знаків. Результатом цього обчислення є 0,11+0,01=1,00.

Пошук найкоротшої відстані

Правило округлення «округлення до найближчого» говорить, що ми повинні округлити до числа, яке найменше відрізняється від вихідного числа. На числовій прямій це означає, що відстань між початковим і двома можливими округленими числами найменша. Отже, якщо ми розмістимо початкове число та можливі варіанти на рядку чисел і позначимо відстані як x, нам потрібно знайти, який x є меншим:

Це досить легко зробити за допомогою віднімання:

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

Тут ясно, що x1 менше, ніж x2, і тоді ми повинні округлити до 0,11. Але що, якби ми хотіли округлити нескінченний двійковий код? У цьому випадку віднімання не було б такою простою операцією. Як виявилося, є набагато простіший підхід.

Порівняння з серединою

Інший простіший підхід полягає в тому, щоб визначити, чи вихідне число більше або менше, ніж середина між двома варіантами округлення. Давайте подивимося на цю діаграму:

Якщо число вище середини, воно ближче до верхнього кандидата; якщо нижче, то ближче до нижчого кандидата. На середині обидва кандидати однаково близькі, і нам потрібне правило визначення нічиїх результатів.

Отже, як знайти середину між двома варіантами округлення? Ми знаємо, що відстань між 0,11 і 1,00 дорівнює 0,01. Тому нам просто потрібно знайти половину 0,01 і додати її до нижчого числа. Половина дорівнює 0,001, і коли її додати до нижчого числа, виходить 0,111 = 0,11 + 0,001. По суті, це еквівалентно простому додаванню 1 до кінця нижчого числа. Ось діаграма з відповідними числами, розміщеними на числовій прямій:

Тепер залишилося лише порівняти початкове число з середнім:

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

Використовуючи побітове порівняння лексикографічного порядку, стає зрозуміло, що 0,11011 менше середини. Отже, ми маємо округлити до 0,11, і це той самий результат, який ми отримали під час обчислення відстані.

Зв’язки з навіть

Іноді відстань між початковим числом і кожним параметром округлення однакова, тому правило «округлення до найближчого» не може бути застосоване. Припустімо, ми округлюємо число 0,11011 до 4 знаків після точки основи. Ми знаємо, що нам потрібно знайти два варіанти округлення і середину для порівняння. Отже, щоб знайти спочатку менше число, ми просто обрізаємо решту цифр після 4-го місця, що дає нам 0,1101. Тепер ми можемо знайти середину, додавши 1 до кінця нижчого числа, і отримаємо 0,11011. І останнє, давайте знайдемо більше число, додавши 1 ULP до меншого числа — 0,1101+0,0001 = 0,1110.

Отже, ми маємо:

• вихідний номер — 0.11011
• число для округлення до — 0,1101
• число для округлення — 0,1110
• середнє число між варіантами округлення — 0,11011.

Вихідне число дорівнює середині, тому нам потрібне правило розрізнення результатів. Тут «парний» стосується цілого числа, утвореного збереженими бітами, або, еквівалентно, збереженого останнього біта 0. З 0,1101 і 0,1110 останнє закінчується на 0, тому ми округлюємо до 0,1110.

Виведення загальних правил округлення

Чи потрібно порівнювати кожну цифру? Вихідне число та середина мають спільні перші n дробові цифри. Тоді середня точка має 1 у позиції n+1, за якою йдуть нулі, тому порівняння починається з n+1.

Отже, загальні правила округлення, наведені на початку статті, виходять із порівняння вихідного числа та середини між двома варіантами округлення. Я ще раз повторю ці правила:

Загальне правило при округленні до n-го розряду наказує перевіряти цифру, наступну за n-м розрядом у числі. Якщо це 0, то число завжди слід округляти в меншу сторону. Якщо замість цього цифра дорівнює 1, а будь-яка з наступних цифр також дорівнює 1, тоді число слід округлити в більшу сторону. Проте, якщо всі наступні цифри дорівнюють 0, тоді має бути застосовано правило визначення рівності, і зазвичай це «рівняння рівних». Це правило говорить, що ми повинні округлити до числа, яке має 0 на n-му місці.