У цій статті ми продовжимо розгляд проблеми комп'ютерних обчислень десяткових чисел за допомогою двійкової арифметики, яка була порушена в попередньому топіку [1]. У статті йтиметься про помилки, які в літературі прийнято називати помилками округлення. І, зокрема, помилок, які породжуються в результаті ітераційного підсумовування великого числа однакових десяткових чисел, представлених у двійковому вигляді обмеженим розрядним простором. У результаті досліджень були отримані прості рекуррентні співвідношення, що дозволяють точно визначити помилку комп'ютерних ітераційних обчислень часткових сум будь-якої кількості однакових доданків, на будь-якому кроці ітерації.
Будемо розглядати дійсні позитивні двійкові числа з фіксованою кількістю L значущих цифр. Під фіксованою кількістю L значущих цифр будемо розуміти L цифр, відлік яких проводиться зліва направо, починаючи від старшої ненульової цифри. Відсутня кількість цифр до L в числі праворуч доповнюється нулями. Так, якщо кількість значущих цифр зафіксувати значенням L = 5, то число 0.0011 матиме такі значущі цифри: 11000. Якщо тепер записати наше число в 5-розрядний комп'ютер, як число з плаваючою точкою, то в область машинної мантиси буде записано: .11000. Це число буде представлено в комп'ютері в нормалізованому вигляді з експонентою, рівною 2 ^ -2.
Число з плаваючою точкою записується в машинному слові, як витвір дробової мантиси на експоненту, порядок якої вказує на положення точки в числі, представленому в природній формі. Якщо число цифр мантиси числа не збігається з кількістю L розрядів машинної мантиси, число нормалізують, зрушуючи мантісу в ту чи іншу сторону так, щоб старша ненульова цифра числа розташовувалася в старшому розряді машинної мантіси. При цьому порядок експоненти коригують на кількість зрушень.
Розгляньмо число у природній формі. Якщо кількість його значущих цифр перевищує деяку фіксовану кількість L цифр, то вона має бути перетворена таким чином, щоб кількість її значущих цифр стала дорівнювати L. Це досягається шляхом відкидання зайвих молодших цифр. При відкиданні молодших цифр, число може бути округлене до L розрядів, або в ньому просто усікаються зайві молодші цифри. Так, у разі усікання, двійкове число 10.0011, представлене в природному вигляді, для L = 5, буде записано як 10.001. Те ж число, записане в експоненційному нормалізованому вигляді, буде виглядати як 0.10001 * 2 ^ 2. Тут ми маємо два еквівалентні записи одного і того ж числа.
Наведення числа, представленого в природному вигляді, до числа з кількістю значущих цифр L, будемо називати оптимізацією. Ми вводимо це поняття, щоб відрізняти його від операції нормалізації чисел, записаних в експоненційному вигляді. З математичної точки зору це дві еквівалентні операції.
Далі будемо розглядати випадок усікання молодших цифр у двійковому числі без округлення. Числа будемо розглядати представленими в природному вигляді.
Нехай ми маємо деяке число 2. p. Z < 2 (p + 1), де p - ціле число зі знаком, рівне відстані від розділової точки до старшої ненульової цифри в числі Z, записаному в природному вигляді. Якщо старша ненульова цифра знаходиться ліворуч від точки, p > 0. Якщо цифра знаходиться праворуч від точки, p < 0. Так, для числа Z = 0.000101 матимемо p = -4 і для цього випадку: 2^(-4) ≤Z < 2^(-3).
Розгляньмо послідовність дійсних двійкових чисел X0, X1,... Xi..., що лежать в інтервалах:
2^p ≤ X0 < 2^(1+p) ≤ X1 < 2^(2+p);...; 2^(i+p) ≤ Xi < 2^(i+p+1)…
Наприклад, для p = -3 ми матимемо 2, p = 2, -3 = 0.001. Наша послідовність тоді виглядатиме як 0. 01. X0 < 0.01. X1 < 0.1,..., 2.
Візьмімо деяке дійсне число 2, (i + p). Xi < 2, (i + p + 1), що має обмежену кількість L значущих цифр. Візьмемо далі суму ki елементарних доданків: Z + Z +... = kiZ, де Z = X0, ki - ціле число. Виберіть ki таким чином, щоб 2. (i + p). Xi + kiZ < 2. (i + p + 1). У цій сумі максимальна кількість ki елементарних доданків Z, при якій значення суми не перевищить праву межу інтервалу, можна знайти за формулою ki = ^ (2 ^ (i + p + 1) -Xi )/Z.
Якщо тепер до Xi + kiZ додати ще один елементарний доданок Z, отримаємо Xi + 1 = Xi + kiZ + Z = Xi + Z (ki + 1). Значення знову отриманої суми перевищить або буде дорівнювати правому граничному значенню інтервалу. Тому кількість цифр серед Xi + 1 = Xi + Z (ki + 1) стане L + 1. Щоб виконати вимогу рівності кількості значущих цифр величиною L, отримане число треба оптимізувати, тобто привести до числа, в якому буде L значущих цифр. Для цього в ньому треба відкинути молодшу цифру. Операцію відкидання молодшої цифри в числі Xi будемо записувати як Xi-1. Наприклад, якщо в числі X = 10.0011 відкинути одну молодшу цифру, то воно буде записано як X ^ 1 = 10.001. У загальному випадку, запис X ^ t буде означати, що в числі X відкинуто t молодших розрядів.
Після того, як на певному ітераційному кроці часткова сума Xi + 1 = Xi + Z (ki + 1) перевищить значення 2 ^ (i + p + 1), яке ми будемо називати правим граничним значенням, старша ненульова цифра суми виявиться зміщеною відносно фіксованої точки вліво. Загальна кількість значущих цифр перевищить число L на одиницю і результат повинен бути оптимізований. Оскільки на i-му кроці ітерації в результаті оптимізації, в числі Xi молодша цифра відкидається, то число стає рівним Xi-1, тоді молодша цифра в складаному Z також може бути відкинута, тому що на подальші обчислення вона впливати не буде.
Наприклад. Нехай L = 5. Знайдемо суму двох чисел X = 1.10111 і Z = 0.10011. Оскільки кількість цифр в X перевищує величину L, вона має бути оптимізована. Після оптимізації отримаємо: X¬1=1.1011. Додамо до цього числа Z = 0.1001 * * 1 * *. Отримаємо X ^ 1 + Z = 1.1011 + 0.1001 * * 1 * * = 10.0100 * * 1 * *. Тут кількість цифр після коми в доданому X-1 менша за кількість цифр у складеному Z. Тому молодша цифра в Z, позначена жирним шрифтом, з одного боку, завжди складається з нулем, а з іншого, результат складання молодших цифр у цьому випадку виявляється поза діапазоном L значущих цифр і, отже, при усіченні, не впливає на загальну суму. Звідси випливає, що сума не зміниться, якщо її записати як X-1 + Z-1 = 1.1011 + 0.1001 = 10.0100. Оскільки в цій сумі кількість цифр перевищила величину L, то отримане число також має бути оптимізовано. Відкинувши молодшу цифру, ми отримаємо оптимізоване число 10.010 з L = 5 значущими цифрами.
Таким чином, значення часткових сум Xi і Xi + 1 відрізняються максимум на kiелементарних доданках. Кількість значущих цифр часткових сум, що лежать в інтервалі [Xi, Xi + 1) дорівнює L і тому їх значення обчислюються без округлень і, відповідно, не роблять помилок. Додавання (ki + 1) -ого доданого до часткової суми призводить до перевищення правого граничного значення або його рівності. Якщо часткова сума на якомусь кроці ітерації перевищує праве граничне значення або дорівнює йому, то кількість значущих цифр в сумі стає рівною L + 1 і потрібна оптимізація. Після кожного перевищення правого граничного значення, кількість значущих цифр елементарних доданків Z, які беруть участь в утворенні нових часткових сум зменшується на одиницю і після i-го правого граничного значення елементарне доданок стає рівним Z i.
Xi+1= (Xi+ (ki+1+1)Z¬i)¬1, X0=Z, i=0,1…
ki + 1 ='( 2'( p + i) -Xi )/Z i', p- ціле число зі знаком.
Номер кроку ітерації Ni + 1, на якому часткова сума Xi + 1 перевищила праве граничне значення можна визначити за рекуррентним співвідношенням:
Ni+1=(ki+1+1)+Ni.
Розглянемо тепер, яку помилку ми отримуємо при ітераційному підсумовуванні десяткових дійсних чисел, представлених у двійковому вигляді, в результаті операції усічення.
Відомо, що будь-яке десяткове число X, представлене в двійковому вигляді, після усікання кількості значущих цифр, може бути записано як X = B + g, де B- представлення десяткового числа X в двійковому вигляді з обмеженою фіксованою кількістю значущих цифр, g - абсолютна похибка подання числа в результаті усічення. Ця похибка може бути визначена як g = X-B, g ^ 0. При підсумовуванні i елементарних доданків ця помилка накопичується і стає рівною ig.
Однак, це не єдина помилка, яка утворюється при рекуррентному складанні однакових елементарних доданків. В результаті заокруглення або усікання, при рекуррентному обчисленні часткових сум, утворюються також помилки заокруглення.
Виведені нами рекуррентні співвідношення дозволяють на будь-якому кроці ітерації отримати точні значення помилки обчислення суми елементарних доданків, що мають однакові значення.
Розгляньмо для прикладу часткові суми елементарних доданків Z = 0.0011101, для яких L = 5. Для Z ми матимемо p = 0.001. У Таблиці 1 наведено результати складання 10 елементарних доданків для кожного кроку ітерації.
У стовпчику 1 таблиці представлені номери i часткових сум Xi, які перевищили або стали рівними правій межі інтервалу. У другому стовпчику наведено номери ітерацій j. У стовпчику 3 наведено позначення часткових сум Xi при певному значенні i. У стовпчику 4 таблиці наведено один під одним, відповідно, позначення часткових сум Sj і елементарних доданків Z ^ i для кожного кроку ітерації. У стовпчику 5 наведено один під одним, відповідно, значення часткових сум Sj і елементарних доданків Z i для кожного кроку ітерації. Червоним шрифтом позначено розряди чисел, які не беруть участь в утворенні часткових сум. У стовпчику 6 наведено значення коефіцієнтів ki + 1 + 1, які використовуються у нашій рекуррентній формулі для обчислення Xi + 1. У стовпчику 7 наведено один під одним, відповідно, значення часткових сум Sj і елементарних доданків Z i для кожного кроку ітерації в десятковому вигляді. У стовпчику 8 наведено теоретичні значення сум елементарних доданків Z за умови, що похибки округлення не враховуються. У стовпчику 9 представлені значення абсолютних похибок обчислення на кожному кроці ітерації, які розраховані за формулою ^ = (Sj) 10 - jZ ^ 0. У стовпчику 9 представлені значення відносних похибок, які обчислюються за формулою: δ= Δ/jZ¬0.
Як видно з наведеної таблиці, навіть за умови, що елементарні доданки представлені точно, без похибок уявлення, в процесі ітераційного підсумовування дуже швидко утворюється така величина похибки, що обчислення на певному кроці ітерації стають безглуздими. Причина цієї похибки криється в обмеженості машинного слова, а також у процедурі нормалізації, або, в нашому випадку, оптимізації подання чисел.
Нижче ми наводимо Таблицю 2, в якій представлені значення часткових сум при ітераційному підсумовуванні десятичного числа 0.1 в двійковому вигляді з фіксованою кількістю значущих цифр, для 51 розрядної мантиси. У таблиці наведено значення часткових сум у точках перевищення правих граничних значень. Числа, виділені жирним шрифтом у таблиці, є двійковими. Невиділені жирним шрифтом числа, це числа, представлені в десятковому коді. У цій таблиці наведено значення часткових сум Xi, значення коефіцієнтів ki + 1 + 1 для знаходження чергової часткової суми Xi + 1 відповідно до наших рекуррентних співвідношень.
Номер кроку ітерації Ni + 1, на якому чергова часткова сума перевищила праве граничне значення можна визначити за рекуррентним співвідношенням: Ni+1=(ki+1+1)+Ni.
Як видно з Таблиці 2, при числі ітерацій 5368712233 вже в 6 знаку часткової суми ми маємо невірну цифру. Абсолютна помилка обчислень для цього випадку становить ^ = 536871223.3- 536870912.084052 = 311.215948. А відносна помилка буде дорівнювать--------------------------------------------------------------------------------
Водночас, якщо обчислити похибку подання десятичного числа 0.1 у двійковому вигляді з 51 значущою цифрою, то ми будемо мати: 0.1=0.0001100110011001100110011001100110011001100110011001100≈ 0.09999999999999997779
Δ=0.1-0.09999999999999997779≈2.221*10^(-17),
δ=2.221*10^(-17)/0.1=2.221*10^(-16)=14*10^(-14)%.
На кроці ітерації, рівному 5368712233, сумарна абсолютна похибка уявлення приймає значення 5368712233 * 14 * 10 ^ (-18) ^ 0.000000075. Відносна ж похибка уявлення не змінюється при будь-якому кроці ітерації.
Як ми бачимо, абсолютна похибка уявлення виявляється мізерно малою порівняно з похибкою округлення при ітераційному підсумовуванні.
Представлені нами тут рекуррентні формули дозволили отримати точні розрахункові похибки округлення при ітераційному підсумуванні великої кількості однакових десяткових доданків, представлених у двійковому коді.
Автор дякує користувачеві mayorovp за виявлені неточності.
ЛІТЕРАТУРА
1. habrahabr.ru/post/309812
