Арифметика рухомої коми

Домівка > Математика, Перекладені > Арифметика рухомої коми

Арифметика рухомої коми

24.10.2014 harmyder Залишити коментар Go to comments

Небагато часу знадобилось, щоб після винайдення комп’ютерів дійти згоди щодо правильного способу представлення дійсних чисел на цифровій машині. Цим способом є арифметика рухомої коми, апаратний аналог експоненці́йного/наукового представлення чисел.

Обмеження цифрового представлення

Оскільки цифрові комп’ютери використовують скінченну кількість бітів для представлення дійсного числа, вони можуть представити лише скінченну підмножину дійсних чисел (або комплексних). Це обмеження вводить дві складності. Перше, представлені числа не можуть бути довільно великими або маленькими. Друге, між ними повинні бути розриви.

Сучасні комп’ютери представляють числа достатньо великі і маленькі, тому перше обмеження рідко викликає складнощі. Наприклад, широко використовна IEEE арифметика подвійної точності дозволяє числа великі як $1.79 \times 10^{308}$ і такі маленькі як $2.23 \times 10^{-308},$ діапазон достатньо великий для числових алгоритмів. Інакше кажучи, втрата змістових розрядів через використання завеликих або замалих чисел не є серйозним ризиком.

На відміну, проблема розривів між числами, що представляються важлива для наукових обчислень. Наприклад, в IEEE арифметиці подвійної точності, проміжок $[1, 2]$ представлено як дискретну підмножину
$1, 1 + 2^{-52}, 1 + 2 \times 2^{-52}, 1 + 3 \times 2^{-52}, \dots, 2.$ (1)
Проміжок $[2, 4]$ представлено тими ж числами помноженими на 2,
$2, 2 + 2^{-51}, 2 + 1 \times 2^{-51}, 2 + 3 \times 2^{-51}, \dots, 4,$
і загалом, проміжок $[2^j, 2^{j+1}]$ представляють через (1) помножене на $2^j.$ Отже в IEEE арифметиці подвійної точності, розриви між прилеглими числами у відносному сенсі ніколи не більше ніж $2^{-52} \approx 2.22 \times 10^{-16}.$ Таке число може виглядати нехтуваним, у більшості випадків воно так і є за умови використання стабільного алгоритму. Але дивовижно багато недбало розроблених алгоритмів виявляються нестабільними!

Числа з рухомою комою

IEEE арифметика є прикладом арифметичної системи базованої на використанні рухомої точки для представлення дійсних чисел. На сьогодні це універсальна практика на комп’ютерах загального призначення. У числовій системі з рухомою комою, позиція десяткової (або двійкової) коми зберігається окремо від цифр, і розриви між прилеглими числами масштабуються пропорційно до розміру чисел. Це відрізняється представлення з нерухомою комою, де усі розриви однакової величини.

Розглянемо ідеалізовану числову систему з рухомою комою визначену наступним. Система містить дискретну підмножину $\mathrm{F}$ дійсних чисел $\mathbb{R}$ , яка визначена цілим $\beta \ge 2$ відомим як основа (зазвичай 2) і цілим $t \ge 1$ відомим як точність (24 і 53 для IEEE одинарної і подвійної точності, відповідно). Елементи $\mathrm{F}$ це число $0$ разом із усіма числами виду
$x = \pm(m/\beta^t)\beta^e,$ (2)
де $m$ це ціле в діапазоні $1 \le m \le \beta^t$ і $e$ це довільне ціле. Тотожно, ми можемо обмежити діапазон до $\beta^{t - 1} \le m \le \beta^t - 1,$ роблячи вибір $m$ унікальним. Величина $\pm(m/\beta^t)$ відома як мантиса $x$ і $e$ як експонента.

Наша числова система з рухомою комою ідеалізована в сенсі, що вона ігнорує переповнення – занадто великі і занадто малі числа. Як наслідок, $\mathrm{F}$ це зліченно нескінченна множина, і вона самоподібна: $\mathrm{F} = \beta\mathrm{F}.$

Найменшим цілим яке не можна точно представити є $n = \beta^t + 1.$

Машинне епсилон

Вирізняльна здатність $\mathrm{F}$ традиційно підсумовується числом відомим як машинне епсилон. Поки що визначимо його як
$\epsilon_{machine} = \frac{1}{2}\beta^{(1-t)}.$ (3)
(Скоро ми змінимо це визначення.) це число є половиною відстані між одиницею і наступним більшим числом з рухомою точкою. У відносному сенсі, це число завбільшки як розрив між дійсним числом і його представленням з рухомою комою. Тобто, $\epsilon_{machine}$ має таку властивість:
$\forall x \in \mathbb{R}, \exists x' \in \mathrm{F}, |x - x'| \le \epsilon_{machine}|x|.$ (4)

Для значень $\beta$ і $t$ поширених на різних комп’ютерах, $\epsilon_{machine}$ зазвичай лежить між $10^{-6}$ і $10^{-35}.$ В IEEE арифметиці одинарної і подвійної точності, $\epsilon_{machine}$ визначено як $2^{-24} \approx 5.96 \times 10^{-8}$ і $2^{-53} \approx 1.11 \times 10^{-16},$ відповідно.

Нехай $\mbox{fl} : \mathbb{R} \in \mathrm{F}$ буде функцією, що дає найкраще наближення рухомою комою до дійсного числа, його округлений еквівалент у системі з рухомою комою. (Для наших цілей, випадки рівновідстані числа від двох представлень з рухомою комою розв’язуються довільним чином. Хоча обробка рівновідстаней (тайбрейкінг) таким чином, щоб уникнути статистичного зміщення цікаве питання саме по собі.) Нерівність (4) можна виразити в термінах $\mbox{fl}:$
$\forall x \in \mathbb{R}, \exists \epsilon, |\epsilon| \le \epsilon_{machine}, \mbox{fl}(x) = x(1 + \epsilon).$ (5)

Тобто, різниця між дійсним числом і його найближенням рухомою комою завжди менше ніж $\epsilon_{machine}$ , якщо говорити відносними термінами.

Арифметика рухомої коми

Та саме представлення дійсних чисел не є самоціллю для нас; необхідно обчислювати з ними. На комп’ютері всі математичні операції зведені до елементарних арифметичних операцій, з яких класичним набором є $+, -, \times$ і $\div.$ Математично ці символи представляють операції на $\mathbb{R}.$ На комп’ютері вони мають аналоги які діють на $\mathrm{F}.$ Зазвичай їх позначають $\oplus, \dots$

Комп’ютер може бути побудованим на таких принципах. Нехай $x$ і $y$ будуть довільні числа з рухомою точкою, тобто, $x, y \in \mathrm{F}.$ Нехай $\ast$ буде однією з операцій $+, -, \times, \div,$ і нехай $\oast$ буде її аналогом з рухомою комою. Тоді $x \oast y$ повинне бути задано саме так
$x \oast y = \mbox{fl}(x \ast y).$ (6)