Представление чисел с плавающей точкой — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Ссылки)
м (rollbackEdits.php mass rollback)
 
(не показаны 53 промежуточные версии 5 участников)
Строка 3: Строка 3:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Плавающая точка (floating point)''' - метод представления действительных чисел, при котором число хранится в виде мантиссы и показателя степени.
+
'''Плавающая точка (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'').
 
Представление чисел с плавающей точкой рассмотрим на примере чисел ''двойной точности'' (''double precision'').
 
Такие числа занимают в памяти два машинных слова (8  байт на 32-битных системах). Наиболее распространенное представление описано в стандарте IEEE 754.
 
Такие числа занимают в памяти два машинных слова (8  байт на 32-битных системах). Наиболее распространенное представление описано в стандарте IEEE 754.
  
== Числа двойной точности ==
+
Кроме чисел двойной точности также используются следующие форматы чисел:
Число с плавающей точкой хранится в нормализованной форме и состоит из трех частей (в скобках указано количество бит, отводимых на каждую секцию в формате double):
+
* ''половинной точности (half precision)'' (16 бит),
# знак (1)
+
* ''одинарной точности (single precision)'' (32 бита),
# экспонента (показатель степени) (11)
+
* ''четверной точности (quadruple precision)'' (128 бит),
# мантисса (52)
+
* ''расширенной точности (extended precision)'' (80 бит).
В качестве базы (основания степени) используется число 2.
+
При выборе формата программисты идут на разумный компромисс между точностью вычислений и размером числа.
{{TODO| t=Вставить картинку, когда можно будет загрузить файл}}
 
  
 +
== Нормальная и нормализованная формы ==
 +
{{Определение
 +
|definition=
 +
'''Нормальной''' называется форма представления числа, при которой абсолютное значение мантиссы десятичного числа находится на полуинтервале <tex> [0,1) </tex>.
 +
}}
 +
Недостатком такой записи является тот факт, что числа нельзя записать однозначно: <tex> 0.01 = 0.001 \times 10^1 </tex>.
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Нормализованной''' называется форма представления числа, при которой мантисса двоичного числа <tex> mant </tex> лежит в диапазоне <tex> [1, 2) </tex>.
+
'''Нормализованной''' называется форма представления числа, при которой абсолютное значение мантиссы десятичного числа лежит на полуинтервале <tex> [1, 10) </tex>, а двоичного на полуинтервале <tex> [1, 2) </tex>.
 
}}
 
}}
 +
 +
== Числа двойной точности ==
 +
Число с плавающей точкой хранится в нормализованной форме и состоит из трех частей (в скобках указано количество бит, отводимых на каждую секцию в формате double):
 +
# знак
 +
# экспонента (показатель степени) (в виде целого числа в коде со сдвигом)
 +
# мантисса (в нормализованной форме)
 +
В качестве базы (основания степени) используется число <tex> 2 </tex>.
 +
Экспонента хранится со сдвигом <tex> -1023 </tex>.
 +
 +
{|class="wikitable" style="border-collapse: collapse; border: none"
 +
|-
 +
!colspan=7 style="background-color: powderblue; border: thin solid black; border-bottom: none"|Знак
 +
|-
 +
!style="background-color: powderblue; border: thin solid black; border-top: none"|
 +
!colspan=11 style="background-color: lightgreen; border: thin solid black"|Экспонента<br />(11 бит)
 +
!colspan=53 style="background-color: lightcoral; border: thin solid black"|Мантисса<br />(52+1 бит)
 +
|-style="text-align: right"
 +
!style="background-color: powderblue; border: thin solid black"|0
 +
!style="background-color: lightgreen; border: thin solid black"|0
 +
!style="background-color: lightgreen; border: thin solid black"|0
 +
!style="background-color: lightgreen; border: thin solid black"|0
 +
!style="background-color: lightgreen; border: thin solid black"|0
 +
!style="background-color: lightgreen; border: thin solid black"|0
 +
!style="background-color: lightgreen; border: thin solid black"|0
 +
!style="background-color: lightgreen; border: thin solid black"|0
 +
!style="background-color: lightgreen; border: thin solid black"|0
 +
!style="background-color: lightgreen; border: thin solid black"|0
 +
!style="background-color: lightgreen; border: thin solid black"|0
 +
!style="background-color: lightgreen; border: thin solid black"|0
 +
!style="border: none"|1,
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
|-
 +
|style="border: none"|
 +
|colspan=4  style="border: none; border-left: 1px solid gray; text-align: left"|62
 +
|colspan=7  style="border: none; border-right: 1px solid gray; text-align: right"|52
 +
|style="border: none"|
 +
|colspan=48 style="border: none; border-left: 1px solid gray; text-align: left"|51
 +
|colspan=4  style="border: none; border-right: 1px solid gray; text-align: right"|0
 +
|}
  
 
{{Утверждение
 
{{Утверждение
 
|statement=
 
|statement=
 
Итоговое значение числа вычисляется по формуле:
 
Итоговое значение числа вычисляется по формуле:
<br><tex> x = (-1)^{sign} \times (1.mant) \times 2^{exp} </tex>
+
<br><tex> x = (-1)^{sign} \times (1.mant) \times 2^{exp} </tex>.
 
}}
 
}}
  
Строка 30: Строка 127:
 
# В нормализованном виде любое отличное от нуля число представимо в единственном виде. Недостатком такой записи является тот факт, что невозможно представить число 0.
 
# В нормализованном виде любое отличное от нуля число представимо в единственном виде. Недостатком такой записи является тот факт, что невозможно представить число 0.
 
# Так как старший бит двоичного числа, записанного в нормализованной форме, всегда равен 1, его можно опустить. Это используется в стандарте IEEE 754.
 
# Так как старший бит двоичного числа, записанного в нормализованной форме, всегда равен 1, его можно опустить. Это используется в стандарте IEEE 754.
# В отличие от целочисленных стандартов (например, integer), имеющих равномерное распределение на всем множестве значений, числа с плавающей точкой (double, например) имеют квазиравномерное распределение. {{TODO| t=Вставить картинки, когда можно будет загрузить файл}}
+
# В отличие от целочисленных стандартов (например, integer), имеющих равномерное распределение на всем множестве значений, числа с плавающей точкой (double, например) имеют квазиравномерное распределение.
# В следствие свойства 3, числа с плавающей точкой имеют постоянную относительную погрешность (в отличие от целочисленных, которые имеют постоянную абсолютную погрешность).
+
# Вследствие свойства 3, числа с плавающей точкой имеют постоянную относительную погрешность (в отличие от целочисленных, которые имеют постоянную абсолютную погрешность).
 
# Очевидно, не все действительные числа возможно представить в виде числа с плавающей точкой.
 
# Очевидно, не все действительные числа возможно представить в виде числа с плавающей точкой.
 
# Точно в таком формате представимы только числа, являющиеся суммой некоторых обратных степеней двойки (не ниже -53). Остальные числа попадают в некоторый диапазон и округляются до ближайшей его границы. Таким образом, абсолютная погрешность составляет половину величины младшего бита.
 
# Точно в таком формате представимы только числа, являющиеся суммой некоторых обратных степеней двойки (не ниже -53). Остальные числа попадают в некоторый диапазон и округляются до ближайшей его границы. Таким образом, абсолютная погрешность составляет половину величины младшего бита.
 +
# В формате double представимы числа в диапазоне <tex> [2.3 \times 10^{-308}, 1.7 \times 10^{308}] </tex>.
 +
 +
== Особые значения чисел с плавающей точкой ==
 +
=== Ноль (со знаком) ===
 +
В нормализованной форме невозможно представить ноль. Для его представления в стандарте зарезервированы специальные значения мантиссы и экспоненты.
 +
{|class="wikitable" style="border-collapse: collapse; border: none"
 +
|-
 +
!colspan=5 style="background-color: powderblue; border: thin solid black; border-bottom: none"|Знак
 +
|-
 +
!style="background-color: powderblue; border: thin solid black; border-top: none"|
 +
!colspan=5 style="background-color: lightgreen; border: thin solid black"|Экспонента
 +
!colspan=11 style="background-color: lightcoral; border: thin solid black"|Мантисса
 +
!style="border: none"|
 +
|-style="text-align: right"
 +
!style="background-color: powderblue; border: thin solid black"|<sup>0</sup>/<sub>1</sub>
 +
!style="background-color: lightgreen; border: thin solid black"|0
 +
!style="background-color: lightgreen; border: thin solid black"|0
 +
!style="background-color: lightgreen; border: thin solid black"|0
 +
!style="background-color: lightgreen; border: thin solid black"|0
 +
!style="background-color: lightgreen; border: thin solid black"|0
 +
!style="border: none"|1,
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: transparent; border: none"|&nbsp;=&nbsp;<tex>\pm0</tex>
 +
|}
 +
Согласно стандарту выполняются следующие свойства:
 +
* <tex> +0 = -0 </tex>
 +
* <tex> \frac{-0}{ \left| x \right| } = -0\,\!</tex> (если <tex>x\ne0</tex>)
 +
* <tex> (-0) \cdot (-0) = +0\,\!</tex>
 +
* <tex> \left| x \right| \cdot (-0) = -0\,\!</tex>
 +
* <tex> x + (\pm 0) = x\,\!</tex>
 +
* <tex> (-0) + (-0) = -0\,\!</tex>
 +
* <tex> (+0) + (+0) = +0\,\!</tex>
 +
* <tex> \frac{-0}{-\infty} = +0\,\!</tex>
 +
* <tex> \frac{\left|x\right|}{-0} = -\infty\,\!</tex>  (если <tex>x\ne0</tex>)
 +
 +
=== Бесконечность (со знаком) ===
 +
Для приближения ответа к правильному при переполнении, в double можно записать бесконечное значение. Так же, как и в случае с нолем, для этого используются специальные значение мантиссы и экспоненты.
 +
{|class="wikitable" style="border-collapse: collapse; border: none"
 +
|-
 +
!colspan=5 style="background-color: powderblue; border: thin solid black; border-bottom: none"|Знак
 +
|-
 +
!style="background-color: powderblue; border: thin solid black; border-top: none"|
 +
!colspan=5 style="background-color: lightgreen; border: thin solid black"|Экспонента
 +
!colspan=11 style="background-color: lightcoral; border: thin solid black"|Мантисса
 +
!style="border: none"|
 +
|-style="text-align: right"
 +
!style="background-color: powderblue; border: thin solid black"|<sup>0</sup>/<sub>1</sub>
 +
!style="background-color: lightgreen; border: thin solid black"|1
 +
!style="background-color: lightgreen; border: thin solid black"|1
 +
!style="background-color: lightgreen; border: thin solid black"|1
 +
!style="background-color: lightgreen; border: thin solid black"|1
 +
!style="background-color: lightgreen; border: thin solid black"|1
 +
!style="border: none"|1,
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: lightcoral; border: thin solid black"|0
 +
!style="background-color: transparent; border: none"|&nbsp;=&nbsp;<tex>\pm\infty</tex>
 +
|}
 +
Бесконечное значение можно получить при переполнении или при делении ненулевого числа на ноль.
 +
 +
=== Неопределенность ===
 +
В математике встречается понятие неопределенности. В стандарте double предусмотрено псевдочисло, которое арифметическая операция может вернуть даже в случае ошибки.
 +
{|class="wikitable" style="border-collapse: collapse; border: none"
 +
|-
 +
!colspan=5 style="background-color: powderblue; border: thin solid black; border-bottom: none"|Знак
 +
|-
 +
!style="background-color: powderblue; border: thin solid black; border-top: none"|
 +
!colspan=5 style="background-color: lightgreen; border: thin solid black"|Экспонента
 +
!colspan=11 style="background-color: lightcoral; border: thin solid black"|Мантисса
 +
!style="border: none"|
 +
|-style="text-align: right"
 +
!style="background-color: powderblue; border: thin solid black"|<sup>0</sup>/<sub>1</sub>
 +
!style="background-color: lightgreen; border: thin solid black"|1
 +
!style="background-color: lightgreen; border: thin solid black"|1
 +
!style="background-color: lightgreen; border: thin solid black"|1
 +
!style="background-color: lightgreen; border: thin solid black"|1
 +
!style="background-color: lightgreen; border: thin solid black"|1
 +
!style="border: none"|1,
 +
!style="background-color: lightcoral; border: thin solid black"|<sup>0</sup>/<sub>1</sub>
 +
!style="background-color: lightcoral; border: thin solid black"|<sup>0</sup>/<sub>1</sub>
 +
!style="background-color: lightcoral; border: thin solid black"|<sup>0</sup>/<sub>1</sub>
 +
!style="background-color: lightcoral; border: thin solid black"|<sup>0</sup>/<sub>1</sub>
 +
!style="background-color: lightcoral; border: thin solid black"|<sup>0</sup>/<sub>1</sub>
 +
!style="background-color: lightcoral; border: thin solid black"|<sup>0</sup>/<sub>1</sub>
 +
!style="background-color: lightcoral; border: thin solid black"|<sup>0</sup>/<sub>1</sub>
 +
!style="background-color: lightcoral; border: thin solid black"|<sup>0</sup>/<sub>1</sub>
 +
!style="background-color: lightcoral; border: thin solid black"|<sup>0</sup>/<sub>1</sub>
 +
!style="background-color: lightcoral; border: thin solid black"|<sup>0</sup>/<sub>1</sub>
 +
!style="background-color: transparent; border: none"|&nbsp;=&nbsp;<tex>NaN</tex>
 +
|}
 +
 +
Неопределенность можно получить в нескольких случаях. Приведем некоторые из них:
 +
* <tex> f(NaN) = NaN </tex>, где <tex> f </tex> - любая арифметическая операция
 +
* <tex> \infty + (-\infty) = NaN </tex>
 +
* <tex> 0 \times \infty = NaN </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=
 
|definition=
'''Машинная эпсилон''' - наименьшее положительное число <tex> \varepsilon_m </tex>, такое что, <tex> 1 \oplus \varepsilon_m = 1 </tex>, где <tex> \oplus </tex> - машинное сложение.
+
'''Машинная эпсилон''' - наибольшее положительное число <tex> \varepsilon_m </tex>, такое что, <tex> 1 \oplus \varepsilon_m = 1 </tex>, где <tex> \oplus </tex> - машинное сложение.
 
}}
 
}}
 
{{Утверждение
 
{{Утверждение
Строка 44: Строка 268:
 
Таким образом, компьютер не различает числа <tex> x </tex> и <tex> y </tex>, если <tex> 1 < \frac{x}{y} < 1 + \varepsilon_m </tex>.
 
Таким образом, компьютер не различает числа <tex> x </tex> и <tex> y </tex>, если <tex> 1 < \frac{x}{y} < 1 + \varepsilon_m </tex>.
 
}}
 
}}
 +
{{Утверждение
 +
|statement=
 +
Из свойств чисел двойной точности следует, что для них <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 \otimes 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} \in D: </tex>
 +
# <tex> \tilde{v} > \tilde{\epsilon} \Rightarrow (b - a) \times (c - a) > 0 </tex>
 +
# <tex> \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) (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)) - \\
 +
- (b_y - a_y) (c_x - a_x) (1 - (1 + \delta_4) (1 + \delta_5) (1 + \delta_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))| = \\
 +
= |(b_x - a_x) (c_y - a_y)| \cdot |((1 + \delta_1) (1 + \delta_2) (1 + \delta_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)| = \\
 +
= |(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) + \\
 +
+ |(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 (4 \varepsilon_m + 6 \varepsilon_m^2 + 4 \varepsilon_m^3 + \varepsilon_m^4) + \\
 +
+ |(b_y - a_y) (c_x - a_x)| \cdot (4 \varepsilon_m + 6 \varepsilon_m^2 + 4 \varepsilon_m^3 + \varepsilon_m^4) = \\
 +
= (|(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)|).</tex> Получаем, что
 +
 +
<tex> \epsilon = |v - \tilde{v}| \leq t \cdot (4 \varepsilon_m + 6 \varepsilon_m^2 + 4 \varepsilon_m^3 + \varepsilon_m^4). </tex>
 +
 +
<tex>\tilde {t} = (|(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) \geq \\
 +
\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) = \\
 +
= |(b_x - a_x) (c_y - a_y)| (1 - \varepsilon_m)^4 + |(b_y - a_y) (c_x - a_x)| (1 - \varepsilon_m)^4 = \\
 +
= (|(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 = |v - \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/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/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://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 ''Предикат "левый поворот"'']
 
[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 ''Предикат "левый поворот"'']
 +
 +
[[Категория: Вычислительная геометрия]]

Текущая версия на 19:29, 4 сентября 2022

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

Знак
Экспонента
(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
Утверждение:
Итоговое значение числа вычисляется по формуле:
[math] x = (-1)^{sign} \times (1.mant) \times 2^{exp} [/math].

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

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

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

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

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

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

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

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

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

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

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

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

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

В математике встречается понятие неопределенности. В стандарте 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  = [math]NaN[/math]

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

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

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

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

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

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

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

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

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

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

Определение:
Машинная эпсилон - наибольшее положительное число [math] \varepsilon_m [/math], такое что, [math] 1 \oplus \varepsilon_m = 1 [/math], где [math] \oplus [/math] - машинное сложение.
Утверждение:
Таким образом, компьютер не различает числа [math] x [/math] и [math] y [/math], если [math] 1 \lt \frac{x}{y} \lt 1 + \varepsilon_m [/math].
Утверждение:
Из свойств чисел двойной точности следует, что для них [math] \varepsilon_m = 2^{-54}[/math].

Unit in the last place (Unit of least precision)

Мера единичной точности используется для оценки точности вычислений.

Определение:
Пусть [math] a [/math] - число с плавающей точкой, мантисса которого имеет длину [math] m [/math] бит, а экспонента - [math] e [/math] бит. Тогда [math] ulp(a) = 2^{e - m} [/math].


Приведем пример кода на Python, который показывает, при каком значении числа [math] x [/math] компьютер не различает числа [math] x [/math] и [math] x + 1 [/math].

>>> from math import *
>>> x = 1.0
>>> while (x != x + 1):
...   x *= 2
... 
>>> x
9007199254740992.0
>>> log(x) / log(2)
53.0

То есть [math] x = 2^{53} [/math], так как мантисса числа двойной точности содержит 53 бита (в памяти хранятся 52). В C++ для расчета расстояния между двумя числами двойной точности можно воспользоваться функцией [math] \mathrm{boost::math::float\_distance(a, b)} [/math].

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

Определения

Утверждение:
Пусть [math] D [/math] - множество всех чисел с плавающей точкой с операциями [math] \oplus, \ominus, \otimes. \forall a, b \in D: [/math]
  • [math] a \oplus b = (a + b) (1 + \delta), |\delta| \leq \varepsilon_m [/math],
  • [math] a \ominus b = (a - b) (1 + \delta), |\delta| \leq \varepsilon_m [/math],
  • [math] a \otimes b = ab (1 + \delta), |\delta| \leq \varepsilon_m [/math].
Утверждение:
[math] \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) [/math]

[math] \exists \tilde{\epsilon} \in D: [/math]

  1. [math] \tilde{v} \gt \tilde{\epsilon} \Rightarrow (b - a) \times (c - a) \gt 0 [/math]
  2. [math] \tilde{v} \lt -\tilde{\epsilon} \Rightarrow (b - a) \times (c - a) \lt 0 [/math]

Расчет [math] \tilde{\epsilon} [/math]

Обозначим [math] v = (b - a) \times (c - a) = (b_x - a_x) (c_y - a_y) - (b_y - a_y) (c_x - a_x)[/math].

Теперь распишем это выражение в дабловой арифметике.

[math]\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),[/math]

[math] |\delta_i| \leq \varepsilon_m [/math]

Заметим, что [math] v \approx \tilde{v} [/math]

Теперь оценим абсолютную погрешность [math] \epsilon = |v - \tilde{v}|. [/math]

[math] |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) (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)) - \\ - (b_y - a_y) (c_x - a_x) (1 - (1 + \delta_4) (1 + \delta_5) (1 + \delta_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))| = \\ = |(b_x - a_x) (c_y - a_y)| \cdot |((1 + \delta_1) (1 + \delta_2) (1 + \delta_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)| = \\ = |(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) + \\ + |(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 (4 \varepsilon_m + 6 \varepsilon_m^2 + 4 \varepsilon_m^3 + \varepsilon_m^4) + \\ + |(b_y - a_y) (c_x - a_x)| \cdot (4 \varepsilon_m + 6 \varepsilon_m^2 + 4 \varepsilon_m^3 + \varepsilon_m^4) = \\ = (|(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)[/math]

Пусть [math] t = (|(b_x - a_x) (c_y - a_y)| + |(b_y - a_y) (c_x - a_x)|).[/math] Получаем, что

[math] \epsilon = |v - \tilde{v}| \leq t \cdot (4 \varepsilon_m + 6 \varepsilon_m^2 + 4 \varepsilon_m^3 + \varepsilon_m^4). [/math]

[math]\tilde {t} = (|(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) \geq \\ \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) = \\ = |(b_x - a_x) (c_y - a_y)| (1 - \varepsilon_m)^4 + |(b_y - a_y) (c_x - a_x)| (1 - \varepsilon_m)^4 = \\ = (|(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[/math]

Итого:

[math] 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) [/math]

[math] \epsilon = |v - \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) [/math]

Ответ

[math] \tilde{\epsilon} \lt 8 \varepsilon_m \tilde{t} [/math]

Заметим, что это довольно грубая оценка. Вполне можно было бы написать [math] \tilde{\epsilon} \lt 4.25 \varepsilon_m \tilde{t} [/math] или [math] \tilde{\epsilon} \lt 4.5 \varepsilon_m \tilde{t}.[/math]

Ссылки

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