Представление чисел с плавающей точкой — различия между версиями
(→Свойства чисел с плавающей точкой) |
(→Погрешность предиката "левый поворот") |
||
Строка 252: | Строка 252: | ||
== Погрешность предиката "левый поворот" == | == Погрешность предиката "левый поворот" == | ||
− | + | === Постановка задачи === | |
+ | Найти <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):
- знак
- экспонента (показатель степени) (в виде целого числа в коде со сдвигом)
- мантисса (в нормализованной форме)
В качестве базы (основания степени) используется число
. Экспонента хранится со сдвигом .Знак | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Экспонента (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 |
Утверждение: |
Итоговое значение числа вычисляется по формуле:
|
Нормальная и нормализованная формы
Определение: |
Нормальной называется форма представления числа, при которой абсолютное значение мантиссы десятичного числа находится на полуинтервале | .
Недостатком такой записи является тот факт, что числа нельзя записать однозначно:
.Определение: |
Нормализованной называется форма представления числа, при которой абсолютное значение мантиссы десятичного числа лежит на полуинтервале | , а двоичного на полуинтервале .
Свойства чисел с плавающей точкой
- В нормализованном виде любое отличное от нуля число представимо в единственном виде. Недостатком такой записи является тот факт, что невозможно представить число 0.
- Так как старший бит двоичного числа, записанного в нормализованной форме, всегда равен 1, его можно опустить. Это используется в стандарте IEEE 754.
- В отличие от целочисленных стандартов (например, integer), имеющих равномерное распределение на всем множестве значений, числа с плавающей точкой (double, например) имеют квазиравномерное распределение.
- В следствие свойства 3, числа с плавающей точкой имеют постоянную относительную погрешность (в отличие от целочисленных, которые имеют постоянную абсолютную погрешность).
- Очевидно, не все действительные числа возможно представить в виде числа с плавающей точкой.
- Точно в таком формате представимы только числа, являющиеся суммой некоторых обратных степеней двойки (не ниже -53). Остальные числа попадают в некоторый диапазон и округляются до ближайшей его границы. Таким образом, абсолютная погрешность составляет половину величины младшего бита.
- В формате double представимы числа в диапазоне .
Особые значение чисел с плавающей точкой
Ноль (со знаком)
В нормализованной форме невозможно представить ноль. Для его представления в стандарте зарезервированы специальные значения мантиссы и экспоненты.
Знак | |||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Экспонента | Мантисса | ||||||||||||||||
0/1 | 0 | 0 | 0 | 0 | 0 | 1, | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | = |
Согласно стандарту выполняются следующие свойства:
- (если )
- (если )
Бесконечность (со знаком)
Для приближения ответа к правильному при переполнении, в double можно записать бесконечное значение. Так же, как и в случае с нолем, для этого используются специальные значение мантиссы и экспоненты.
Знак | |||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Экспонента | Мантисса | ||||||||||||||||
0/1 | 1 | 1 | 1 | 1 | 1 | 1, | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | = |
Бесконечное значение можно получить при переполнении или при делении ненулевого числа на ноль.
Неопределенность
В математике встречается понятие неопределенности. В стандарте 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 | = |
Неопределенность можно получить в нескольких случаях. Приведем некоторые из них:
- , где - любая арифметическая операция
- , где
Машинная эпсилон
Определение: |
Машинная эпсилон - наименьшее положительное число | , такое что, , где - машинное сложение.
Утверждение: |
Таким образом, компьютер не различает числа и , если . |
Утверждение: |
Из свойств чисел двойной точности следует, что для них . |
Погрешность предиката "левый поворот"
Постановка задачи
Найти
не лежат на одной прямой.Решение
Рассмотрим формулу:
Относительная погрешность , где - машинная эпсилон.
Тогда относительная погрешность .
Таким образом, абсолютная погрешность предиката:
Ссылки
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 Предикат "левый поворот"