Представление чисел с плавающей точкой

Эта статья находится в разработке!

Плавающая точка

Определение:

Плавающая точка (floating point) - метод представления действительных чисел, при котором число хранится в виде мантиссы и показателя степени, а значение числа вычисляется по формуле: $x = (-1)^{sign} \times mant \times base^{exp}$, где $x$ - число, $sign$ - бит, отвечающий за знак числа, $mant$ - мантисса, $base$ - основание степени, $exp$ - показатель степени.

Такой метод является компромиссом между точностью и диапазоном представляемых значений. Представление чисел с плавающей точкой рассмотрим на примере чисел двойной точности (double precision). Такие числа занимают в памяти два машинных слова (8 байт на 32-битных системах). Наиболее распространенное представление описано в стандарте IEEE 754.

Кроме чисел двойной точности также используются следующие форматы чисел:

• половинной точности (half precision) (16 бит),
• одинарной точности (single precision) (32 бита),
• четверной точности (quadruple precision) (128 бит),
• расширенной точности (extended precision) (80 бит).

При выборе формата программисты идут на разумный компромисс между точностью вычислений и размером числа.

Нормальная и нормализованная формы

Определение:

Нормальной называется форма представления числа, при которой абсолютное значение мантиссы десятичного числа находится на полуинтервале $[0,1)$.

Недостатком такой записи является тот факт, что числа нельзя записать однозначно: $0.01 = 0.001 \times 10^1$.

Определение:

Нормализованной называется форма представления числа, при которой абсолютное значение мантиссы десятичного числа лежит на полуинтервале $[1, 10)$, а двоичного на полуинтервале $[1, 2)$.

Числа двойной точности

Число с плавающей точкой хранится в нормализованной форме и состоит из трех частей (в скобках указано количество бит, отводимых на каждую секцию в формате double):

1. знак
2. экспонента (показатель степени) (в виде целого числа в коде со сдвигом)
3. мантисса (в нормализованной форме)

В качестве базы (основания степени) используется число $2$. Экспонента хранится со сдвигом $-1023$.

Знак
	Экспонента (11 бит)											Мантисса (52+1 бит)
0	0	0	0	0	0	0	0	0	0	0	0	1,	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
	62				52								51																																																0

Утверждение:

Итоговое значение числа вычисляется по формуле: $x = (-1)^{sign} \times (1.mant) \times 2^{exp}$.

Свойства чисел с плавающей точкой

1. В нормализованном виде любое отличное от нуля число представимо в единственном виде. Недостатком такой записи является тот факт, что невозможно представить число 0.
2. Так как старший бит двоичного числа, записанного в нормализованной форме, всегда равен 1, его можно опустить. Это используется в стандарте IEEE 754.
3. В отличие от целочисленных стандартов (например, integer), имеющих равномерное распределение на всем множестве значений, числа с плавающей точкой (double, например) имеют квазиравномерное распределение.
4. Вследствие свойства 3, числа с плавающей точкой имеют постоянную относительную погрешность (в отличие от целочисленных, которые имеют постоянную абсолютную погрешность).
5. Очевидно, не все действительные числа возможно представить в виде числа с плавающей точкой.
6. Точно в таком формате представимы только числа, являющиеся суммой некоторых обратных степеней двойки (не ниже -53). Остальные числа попадают в некоторый диапазон и округляются до ближайшей его границы. Таким образом, абсолютная погрешность составляет половину величины младшего бита.
7. В формате double представимы числа в диапазоне $[2.3 \times 10^{-308}, 1.7 \times 10^{308}]$.

Особые значение чисел с плавающей точкой

Ноль (со знаком)

В нормализованной форме невозможно представить ноль. Для его представления в стандарте зарезервированы специальные значения мантиссы и экспоненты.

Знак
	Экспонента					Мантисса
0/1	0	0	0	0	0	1,	0	0	0	0	0	0	0	0	0	0	= $\pm0$

Согласно стандарту выполняются следующие свойства:

• $+0 = -0$
• $\frac{-0}{ \left| x \right| } = -0\,\!$ (если $x\ne0$)
• $(-0) \cdot (-0) = +0\,\!$
• $\left| x \right| \cdot (-0) = -0\,\!$
• $x + (\pm 0) = x\,\!$
• $(-0) + (-0) = -0\,\!$
• $(+0) + (+0) = +0\,\!$
• $\frac{-0}{-\infty} = +0\,\!$
• $\frac{\left|x\right|}{-0} = -\infty\,\!$ (если $x\ne0$)

Бесконечность (со знаком)

Для приближения ответа к правильному при переполнении, в double можно записать бесконечное значение. Так же, как и в случае с нолем, для этого используются специальные значение мантиссы и экспоненты.

Знак
	Экспонента					Мантисса
0/1	1	1	1	1	1	1,	0	0	0	0	0	0	0	0	0	0	= $\pm\infty$

Бесконечное значение можно получить при переполнении или при делении ненулевого числа на ноль.

Неопределенность

В математике встречается понятие неопределенности. В стандарте double предусмотрено псевдочисло, которое арифметическая операция может вернуть даже в случае ошибки.

Знак
	Экспонента					Мантисса
0/1	1	1	1	1	1	1,	0/1	0/1	0/1	0/1	0/1	0/1	0/1	0/1	0/1	0/1	= $NaN$

Неопределенность можно получить в нескольких случаях. Приведем некоторые из них:

• $f(NaN) = NaN$, где $f$ - любая арифметическая операция
• $\infty + (-\infty) = NaN$
• $0 \times \infty = NaN$
• $\frac{\pm0}{\pm0} = \frac{\pm \infty}{\pm \infty} = NaN$
• $\sqrt{x} = NaN$, где $x \lt 0$

Денормализованные числа

Денормализованные (denormalized numbers) - способ увеличить количество представимых числе в окрестности нуля. Каждое такое число по модулю меньше самого маленького нормализованного.< Согласно стандарту числа с плавающей точкой можно представить в следующем виде:

• $(-1)^s \times 1.M \times 2^E$, в нормализованном виде если $E_{min} \leq E \leq E_{max}$,
• $(-1)^s \times 0.M \times 2^E_{min}$, в денормализованном виде если $E = E_{min} - 1$,

где $E_{min}$ - минимальное значение порядка, используемое для записи чисел (единичный сдвиг), $E_{min} - 1$ - минимальное значение порядка, которое он может принимать - все биты нули, нулевой сдвиг.

Ввиду сложности, денормализованные числа обычно реализуют на программном уровне, а не на аппаратном. Из-за этого резко возрастает время работы с ними. Это недопустимо в областях, где требуется большая скорость вычислений (например, видеокарты). Так как денормализованные числа представляют числа мало отличные от нуля и мало влияют на результат, зачастую они игнорируются (что резко повышает скорость). При этом используются две концепции:

1. Flush To Zero (FTZ) - в качестве результата возвращается нуль, как только становится понятно, что результат будет представляться в денормализованном виде.
2. Denormals Are Zero (DAZ) - денормализованные числа, поступающие на вход, рассматриваются как нули.

Начиная с версии стандарта IEEE 754 2008 года денормализованные числа называются "субнормальными" (subnormal numbers), то есть числа, меньшие "нормальных".

Машинная эпсилон

Определение:

Машинная эпсилон - наибольшее положительное число $\varepsilon_m$, такое что, $1 \oplus \varepsilon_m = 1$, где $\oplus$ - машинное сложение.

Утверждение:

Таким образом, компьютер не различает числа $x$ и $y$, если $1 \lt \frac{x}{y} \lt 1 + \varepsilon_m$.

Утверждение:

Из свойств чисел двойной точности следует, что для них $\varepsilon_m = 2^{-54}$.

Погрешность предиката "левый поворот"

Постановка задачи

Найти $\varepsilon(a, b, c) = \varepsilon: |(b - a) \times (c - a)| \gt \varepsilon \Rightarrow a, b, c$ не лежат на одной прямой.

Решение

Рассмотрим формулу: $|b_x - a_x||c_y - a_y| + |b_y - a_y||c_x - a_x|$.
Относительная погрешность $\delta(|b_x - a_x|) = \delta(|c_y - a_y|) = \delta(|b_y - a_y|) = \delta(|c_x - a_x|) = \varepsilon_m$, где $\varepsilon_m$ - машинная эпсилон.
Тогда относительная погрешность $\delta(|b_x - a_x||c_y - a_y|) = \delta(|b_y - a_y||c_x - a_x|) = 2 \varepsilon_m$.
Таким образом, абсолютная погрешность предиката:
$\varepsilon = |b_x - a_x||c_y - a_y| \times \delta(|b_x - a_x||c_y - a_y|) + |b_y - a_y||c_x - a_x| \times \delta(|b_y - a_y||c_x - a_x|) = 2 \varepsilon_m (|b_x - a_x||c_y - a_y| + |b_y - a_y||c_x - a_x|)$.

Ответ

$\varepsilon(a, b, c) = 2 \varepsilon_m (|b_x - a_x||c_y - a_y| + |b_y - a_y||c_x - a_x|)$

Ссылки

en.wikipedia.org Floating point
en.wikipedia.org Double precision floating point format
Goldberg, D. 1991 What every computer scientist should know about floating-point arithmetic
ieee.org IEEE 754
neerc.ifmo.ru/mediawiki Предикат "левый поворот"