Изменения

Перейти к: навигация, поиск

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

9515 байт добавлено, 19:29, 4 сентября 2022
м
rollbackEdits.php mass rollback
{{Определение
|definition=
'''Плавающая точка (floating point)''' - метод представления действительных чисел, при котором число хранится в виде мантиссы и показателя степени, а значение числа вычисляется по формуле:<br><tex> x = (-1)^{sign} \times mant \times base^{exp} </tex>, где <tex> x </tex> - число, <tex> sign </tex> - бит, отвечающий за знак числа, <tex> mant </tex> - мантисса, <tex> base </tex> - основание степени, <tex> exp </tex> - показатель степени.
}}
Такой метод является компромиссом между точностью и диапазоном представляемых значений.
Представление чисел с плавающей точкой рассмотрим на примере чисел ''двойной точности'' (''double precision'').
Такие числа занимают в памяти два машинных слова (8 байт на 32-битных системах). Наиболее распространенное представление описано в стандарте IEEE 754.
 
Кроме чисел двойной точности также используются следующие форматы чисел:
* ''половинной точности (half precision)'' (16 бит),
* ''одинарной точности (single precision)'' (32 бита),
* ''четверной точности (quadruple precision)'' (128 бит),
* ''расширенной точности (extended precision)'' (80 бит).
При выборе формата программисты идут на разумный компромисс между точностью вычислений и размером числа.
 
== Нормальная и нормализованная формы ==
{{Определение
|definition=
'''Нормальной''' называется форма представления числа, при которой абсолютное значение мантиссы десятичного числа находится на полуинтервале <tex> [0,1) </tex>.
}}
Недостатком такой записи является тот факт, что числа нельзя записать однозначно: <tex> 0.01 = 0.001 \times 10^1 </tex>.
{{Определение
|definition=
'''Нормализованной''' называется форма представления числа, при которой абсолютное значение мантиссы десятичного числа лежит на полуинтервале <tex> [1, 10) </tex>, а двоичного на полуинтервале <tex> [1, 2) </tex>.
}}
== Числа двойной точности ==
|statement=
Итоговое значение числа вычисляется по формуле:
<br><tex> x = (-1)^{sign} \times (1.mant) \times 2^{exp} </tex>}} == Нормальная и нормализованная формы =={{Определение|definition='''Нормальной''' называется форма представления числа, при которой абсолютное значение мантиссы десятичного числа находится на полуинтервале <tex> [0,1) </tex>.}}Недостатком такой записи является тот факт, что числа нельзя записать однозначно: <tex> 0.001 = 0.01 \times 10^0 </tex>.{{Определение|definition='''Нормализованной''' называется форма представления числа, при которой абсолютное значение мантиссы десятичного числа лежит на полуинтервале <tex> [1, 10) </tex>, а двоичного на полуинтервале <tex> [1, 2) </tex>.
}}
# Так как старший бит двоичного числа, записанного в нормализованной форме, всегда равен 1, его можно опустить. Это используется в стандарте IEEE 754.
# В отличие от целочисленных стандартов (например, integer), имеющих равномерное распределение на всем множестве значений, числа с плавающей точкой (double, например) имеют квазиравномерное распределение.
# В следствие Вследствие свойства 3, числа с плавающей точкой имеют постоянную относительную погрешность (в отличие от целочисленных, которые имеют постоянную абсолютную погрешность).
# Очевидно, не все действительные числа возможно представить в виде числа с плавающей точкой.
# Точно в таком формате представимы только числа, являющиеся суммой некоторых обратных степеней двойки (не ниже -53). Остальные числа попадают в некоторый диапазон и округляются до ближайшей его границы. Таким образом, абсолютная погрешность составляет половину величины младшего бита.
# В формате double представимы числа в диапазоне <tex> [2.3 \times 10^{-308}, 1.7 \times 10^{308}] </tex>.
== Особые значение значения чисел с плавающей точкой ==
=== Ноль (со знаком) ===
В нормализованной форме невозможно представить ноль. Для его представления в стандарте зарезервированы специальные значения мантиссы и экспоненты.
* <tex> \frac{\pm0}{\pm0} = \frac{\pm \infty}{\pm \infty} = NaN </tex>
* <tex> \sqrt{x} = NaN </tex>, где <tex> x < 0 </tex>
 
=== Денормализованные числа ===
Денормализованные (''denormalized numbers'') - способ увеличить количество представимых числе в окрестности нуля. Каждое такое число по модулю меньше самого маленького нормализованного.<
Согласно стандарту числа с плавающей точкой можно представить в следующем виде:
* <tex> (-1)^s \times 1.M \times 2^E </tex>, в нормализованном виде если <tex> E_{min} \leq E \leq E_{max} </tex>,
* <tex> (-1)^s \times 0.M \times 2^E_{min} </tex>, в денормализованном виде если <tex> E = E_{min} - 1 </tex>,
где <tex> E_{min} </tex> - минимальное значение порядка, используемое для записи чисел (единичный сдвиг), <tex> E_{min} - 1 </tex> - минимальное значение порядка, которое он может принимать - все биты нули, нулевой сдвиг.
 
Ввиду сложности, денормализованные числа обычно реализуют на программном уровне, а не на аппаратном. Из-за этого резко возрастает время работы с ними. Это недопустимо в областях, где требуется большая скорость вычислений (например, видеокарты).
Так как денормализованные числа представляют числа мало отличные от нуля и мало влияют на результат, зачастую они игнорируются (что резко повышает скорость). При этом используются две концепции:
# ''Flush To Zero (FTZ)'' - в качестве результата возвращается нуль, как только становится понятно, что результат будет представляться в денормализованном виде.
# ''Denormals Are Zero (DAZ)'' - денормализованные числа, поступающие на вход, рассматриваются как нули.
 
Начиная с версии стандарта IEEE 754 2008 года денормализованные числа называются "субнормальными" (''subnormal numbers''), то есть числа, меньшие "нормальных".
== Машинная эпсилон ==
{{Определение
|definition=
'''Машинная эпсилон''' - наименьшее наибольшее положительное число <tex> \varepsilon_m </tex>, такое что, <tex> 1 \oplus \varepsilon_m = 1 </tex>, где <tex> \oplus </tex> - машинное сложение.
}}
{{Утверждение
Из свойств чисел двойной точности следует, что для них <tex> \varepsilon_m = 2^{-54}</tex>.
}}
 
== Unit in the last place (Unit of least precision)==
Мера единичной точности используется для оценки точности вычислений.
{{Определение
|definition=
Пусть <tex> a </tex> - число с плавающей точкой, мантисса которого имеет длину <tex> m </tex> бит, а экспонента - <tex> e </tex> бит. Тогда <tex> ulp(a) = 2^{e - m} </tex>.
}}
 
Приведем пример кода на Python, который показывает, при каком значении числа <tex> x </tex> компьютер не различает числа <tex> x </tex> и <tex> x + 1 </tex>.
>>> from math import *
>>> x = 1.0
>>> while (x != x + 1):
... x *= 2
...
>>> x
9007199254740992.0
>>> log(x) / log(2)
53.0
 
То есть <tex> x = 2^{53} </tex>, так как мантисса числа двойной точности содержит 53 бита (в памяти хранятся 52).
В C++ для расчета расстояния между двумя числами двойной точности можно воспользоваться функцией <tex> \mathrm{boost::math::float\_distance(a, b)} </tex>.
== Погрешность предиката "левый поворот" ==
=== Постановка задачи Определения ===Найти {{Утверждение|statement=Пусть <tex> D </tex> - множество всех чисел с плавающей точкой с операциями <tex> \oplus, \ominus, \otimes. \forall a, b \in D: </tex>* <tex> a \oplus b = (a + b) (1 + \delta), |\delta| \leq \varepsilon_m </tex>,* <tex> a \ominus b = (a - b) (1 + \delta), |\delta| \leq \varepsilon_m </tex>,* <tex> a \varepsilonotimes b = ab (1 + \delta), |\delta| \leq \varepsilon_m </tex>.}} {{Утверждение|statement=<tex> \forall a, b, c\in D^2, \tilde{v} = (b_x \ominus a_x) \otimes (c_y \ominus a_y) \ominus (b_y \ominus a_y) \otimes (c_x \ominus a_x) = </tex><tex> \exists \tilde{\epsilon} \varepsilonin D: |</tex># <tex> \tilde{v} > \tilde{\epsilon} \Rightarrow (b - a) \times (c - a)| > 0 </tex># <tex> \varepsilon tilde{v} < -\tilde{\epsilon} \Rightarrow (b - a, ) \times (c - a) < 0 </tex>}} === Расчет <tex> \tilde{\epsilon} </tex> ===Обозначим <tex> v = (b, - a) \times (c - a) = (b_x - a_x) (c_y - a_y) - (b_y - a_y) (c_x - a_x)</tex> не лежат на одной прямойТеперь распишем это выражение в дабловой арифметике. <tex>\tilde{v} = (b_x \ominus a_x) \otimes (c_y \ominus a_y) \ominus (b_y \ominus a_y) \otimes (c_x \ominus a_x) = \\ = [ (b_x - a_x) (c_y - a_y) (1 + \delta_1) (1 + \delta_2) (1 + \delta_3) - \\ - (b_y - a_y) (c_x - a_x) (1 + \delta_4) (1 + \delta_5) (1 + \delta_6) ] (1 + \delta_7),</tex> <tex> |\delta_i| \leq \varepsilon_m </tex> Заметим, что <tex> v \approx \tilde{v} </tex>
Теперь оценим абсолютную погрешность <tex> \epsilon === Решение ===|v - \tilde{v}|. </tex>  Рассмотрим формулу: <tex> |v - \tilde{v}| = |(b_x - a_x) (c_y - a_y) - (b_y - a_y) (c_x - a_x) - \\- (b_x - a_x)(c_y - a_y) (1 + \delta_1) (1 + \delta_2) (1 + \delta_3) (1 + \delta_7) + \\+ (b_y - a_y)(c_x - a_x) </tex>. <br>(1 + \delta_4) (1 + \delta_5) (1 + \delta_6) (1 + \delta_7)| = \\= |(b_x - a_x) (c_y - a_y) (1 - (1 + \delta_1) (1 + \delta_2) (1 + \delta_3) (1 + \delta_7)) - \\Относительная погрешность <tex> - (b_y - a_y) (c_x - a_x) (1 - (1 + \delta_4) (1 + \delta_5) (1 + \deltadelta_6) (1 + \delta_7))|\leq \\\leq |(b_x - a_x) (c_y - a_y) (1 - (1 + \delta_1) (1 + \delta_2) (1 + \delta_3) (1 + \delta_7))|+ \\+ |(b_y - a_y) (c_x - a_x) (1 - (1 + \delta_4) (1 + \delta_5) (1 + \delta_6) (1 + \delta_7))| = \delta\= |(b_x - a_x) (|c_y - a_y)|\cdot |((1 + \delta_1) (1 + \delta_2) = (1 + \deltadelta_3) (1 + \delta_7) - 1)|+ \\+ |(b_y - a_y) (c_x - a_x)| \cdot |((1 + \delta_4) (1 + \delta_5) (1 + \delta_6) (1 + \delta_7) - 1)| = \delta\= |(b_x - a_x) (c_y - a_y)| \cdot |\delta_1 + \delta_2 + \delta_3 + \delta_7 + \delta_1 \delta_2 \ldots| + \\+ |(b_y - a_y) (c_x - a_x)| \cdot |\delta_4 + \delta_5 + \delta_6 + \delta_7 + \delta_4 \delta_5 \ldots| \leq \\\leq |(b_x - a_x) (c_y - a_y)| \cdot (|\delta_1| + |\delta_2| + |\delta_3|+ |\delta_7| + |\delta_1 \delta_2| \ldots) = + \varepsilon_m </tex>, где <tex> \varepsilon_m </tex> + |(b_y - a_y) (c_x - машинная эпсилон. <br>a_x)| \cdot (|\delta_4| + |\delta_5| + |\delta_6| + |\delta_7| + |\delta_4 \delta_5| \ldots) \leq \\Тогда относительная погрешность <tex> \deltaleq |(|b_x - a_x) (c_y - a_y)|\cdot (4 \varepsilon_m + 6 \varepsilon_m^2 + 4 \varepsilon_m^3 + \varepsilon_m^4) + \\+ |c_y (b_y - a_y) (c_x - a_x)|\cdot (4 \varepsilon_m + 6 \varepsilon_m^2 + 4 \varepsilon_m^3 + \varepsilon_m^4) = \delta\= (|b_y (b_x - a_x) (c_y - a_y)|+ |(b_y - a_y) (c_x - a_x)|) = (4 \varepsilon_m + 6 \varepsilon_m^2 + 4 \varepsilon_m ^3 + \varepsilon_m^4)</tex> Пусть <tex> t = (|(b_x - a_x) (c_y - a_y)| + |(b_y - a_y) (c_x - a_x)|). <br/tex>Получаем, чтоТаким образом, абсолютная погрешность предиката: <tex> \epsilon = |v - \tilde{v}| \leq t \cdot (4 \varepsilon_m + 6 \varepsilon_m^2 + 4 \varepsilon_m^3 + \varepsilon_m^4). <br/tex> <tex> \varepsilon tilde {t} = (|(b_x - a_x) (c_y - a_y) (1 + \delta_1) (1 + \delta_2) (1 + \delta_3)|+ \\+ |c_y (b_y - a_y) (c_x - a_x) (1 + \delta_4) (1 + \delta_5) (1 + \delta_6)| ) (1 + \delta_7) \deltageq \\\geq |(|b_x - a_x||) (c_y - a_y) (1 - \varepsilon_m)^3)|(1 - \varepsilon_m) + \\+ |(b_y - a_y) (c_x - a_x) (1 - \varepsilon_m)^3)|(1 - \varepsilon_m) = \\= |c_x (b_x - a_x) (c_y - a_y)| (1 - \deltavarepsilon_m)^4 + |(|b_y - a_y||) (c_x - a_x)|(1 - \varepsilon_m) ^4 = </tex><br><tex dpi\\="180"> = 2 \varepsilon_m (|(b_x - a_x||) (c_y - a_y)| + |(b_y - a_y) (c_x - a_x)|) (1 - \varepsilon_m)^4 = t \cdot (1 - \varepsilon_m)^4</tex>  Итого: <tex> t \leq \tilde{t} \frac{1}{(1 - \varepsilon_m)^4} = \tilde{t} (1 + 4 \varepsilon_m + 10 \varepsilon_m^2 + 20 \varepsilon_m^3 + \cdots) </tex> <tex> \epsilon = |c_x v - a_x\tilde{v}|\leq \tilde{\epsilon} \leq \tilde{t} (1 + 4 \varepsilon_m + 10 \varepsilon_m^2 + 20 \varepsilon_m^3 + \cdots) (4 \varepsilon_m + 6 \varepsilon_m^2 + 4 \varepsilon_m^3 + \varepsilon_m^4) </tex> === Ответ ===<tex dpi="180"> \tilde{\epsilon} < 8 \varepsilon_m \tilde{t} </tex> Заметим, что это довольно грубая оценка. Вполне можно было бы написать <tex> \tilde{\epsilon} < 4.25 \varepsilon_m \tilde{t} </tex>или <tex> \tilde{\epsilon} < 4.5 \varepsilon_m \tilde{t}.</tex>
== Ссылки ==
[http://en.wikipedia.org/wiki/Floating_point en.wikipedia.org ''Floating point'']<br>
[http://en.wikipedia.org/wiki/Half-precision_floating-point_format en.wikipedia.org ''Half-precision floating point format'']<br>
[http://en.wikipedia.org/wiki/Single-precision_floating-point_format en.wikipedia.org ''Single precision floating point format'']<br>
[http://en.wikipedia.org/wiki/Double_precision_floating-point_format en.wikipedia.org ''Double precision floating point format'']<br>
[http://en.wikipedia.org/wiki/Extended_precision en.wikipedia.org ''Extended precision floating point format'']<br>
[http://en.wikipedia.org/wiki/Quadruple_precision en.wikipedia.org ''Quadruple precision floating point format'']<br>
[http://citeseer.ist.psu.edu/viewdoc/download?doi=10.1.1.102.244&rep=rep1&type=pdf Goldberg, D. 1991 ''What every computer scientist should know about floating-point arithmetic'']<br>
[http://grouper.ieee.org/groups/754 ieee.org ''IEEE 754'']<br>
[http://en.wikipedia.org/wiki/Unit_in_the_last_place en.wikipedia.org ''Unit in the last place'']
[http://neerc.ifmo.ru/mediawiki/index.php/%D0%9F%D1%80%D0%B5%D0%B4%D0%B8%D0%BA%D0%B0%D1%82_%22%D0%BB%D0%B5%D0%B2%D1%8B%D0%B9_%D0%BF%D0%BE%D0%B2%D0%BE%D1%80%D0%BE%D1%82%22 neerc.ifmo.ru/mediawiki ''Предикат "левый поворот"'']
 
[[Категория: Вычислительная геометрия]]
1632
правки

Навигация