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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Свойства чисел с плавающей точкой)
(Погрешность предиката "левый поворот")
Строка 252: Строка 252:
  
 
== Погрешность предиката "левый поворот" ==
 
== Погрешность предиката "левый поворот" ==
{{TODO| t=Вывести}}
+
=== Постановка задачи ===
 +
Найти <tex> \varepsilon(a, b, c) = \varepsilon: |(b - a) \times (c - a)| > \varepsilon \Rightarrow a, b, c </tex> не лежат на одной прямой.
 +
 
 +
=== Решение ===
 +
Рассмотрим формулу: <tex> (b_x - a_x)(c_y - a_y) + (b_y - a_y)(c_x - a_x) </tex>. <br>
 +
Относительная погрешность <tex> \delta(|b_x - a_x|) = \delta(|c_y - a_y|) = \delta(|b_y - a_y|) = \delta(|c_x - a_x|) = \varepsilon_m </tex>, где <tex> \varepsilon_m </tex> - машинная эпсилон. <br>
 +
Тогда относительная погрешность <tex> \delta(|b_x - a_x||c_y - a_y|) = \delta(|b_y - a_y||c_x - a_x|) = 2 \varepsilon_m </tex>. <br>
 +
Таким образом, абсолютная погрешность предиката: <br><tex> \varepsilon = |b_x - a_x||c_y - a_y| \delta(|b_x - a_x||c_y - a_y|) + |b_y - a_y||c_x - a_x| \delta(|b_y - a_y||c_x - a_x|) = </tex><br><tex dpi="180"> = 2 \varepsilon_m (|b_x - a_x||c_y - a_y| + |b_y - a_y||c_x - a_x|) </tex>
  
 
== Ссылки ==
 
== Ссылки ==

Версия 08:41, 11 ноября 2011

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

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

Определение:
Плавающая точка (floating point) - метод представления действительных чисел, при котором число хранится в виде мантиссы и показателя степени.

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

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

Число с плавающей точкой хранится в нормализованной форме и состоит из трех частей (в скобках указано количество бит, отводимых на каждую секцию в формате 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]

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

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

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

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

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

Определение:
Машинная эпсилон - наименьшее положительное число [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].

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

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

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

Решение

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

Ссылки

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 Предикат "левый поворот"