Международный стандарт представления чисел с плавающей точкой в ЭВМ
Материал из MachineLearning.
(→Введение) |
|||
(40 промежуточных версий не показаны.) | |||
Строка 4: | Строка 4: | ||
От этого главным образом зависит точность вычислений,а также их скорость. | От этого главным образом зависит точность вычислений,а также их скорость. | ||
- | В этом отчёте будут рассматриваться те аспекты представления чисел в ЭВМ, которые важны пользователям, желающим активно работать с | + | В этом отчёте будут рассматриваться те аспекты представления чисел в ЭВМ, которые важны пользователям, желающим активно работать с вещественными величинами. Вначале будут введены общепринятые понятия для дальнейшего изложения материала. Будет достаточно подробно рассмотрен наиболее часто используемый стандарт [http://ru.wikipedia.org/wiki/IEEE IEEE 754]. В заключение будут приведены способы доступа к основным параметрам представления вещественных чисел в ряде компиляторов (Microsoft Visual Studio (2003,2005), Borland C (3.1), GCC(3.4) ). |
== Числа с плавающей точкой == | == Числа с плавающей точкой == | ||
- | Числа с плавающей точкой - общепринятая форма представления | + | Числа с плавающей точкой - общепринятая форма представления действительных чисел в ЭВМ. |
- | + | Основными параметрами такой формы представления является основание степени <tex>\beta</tex> (''base'') и точность <tex>p</tex> (''precision''). | |
При этом всегда требуется, чтобы основание степени было целым чётным числом. | При этом всегда требуется, чтобы основание степени было целым чётным числом. | ||
Если <tex>$\beta=10$</tex> и <tex>$p=3$</tex>, то число 0.1 представляется в виде | Если <tex>$\beta=10$</tex> и <tex>$p=3$</tex>, то число 0.1 представляется в виде | ||
Строка 21: | Строка 21: | ||
При этом <tex>d_0.d_1d_2 \dots d_{p-1}</tex> называется ''мантиссой'' числа и состоит из <tex>p</tex> позиций. | При этом <tex>d_0.d_1d_2 \dots d_{p-1}</tex> называется ''мантиссой'' числа и состоит из <tex>p</tex> позиций. | ||
- | В дальнейшем под числом с плавающей точкой мы будем понимать | + | В дальнейшем под числом с плавающей точкой мы будем понимать действительные числа точно представимые в смысле данной формы. |
Существуют ещё два важных параметра — максимальный и минимальный показатели степени <tex>$e_{max}$</tex> и <tex>e_{min}</tex>. | Существуют ещё два важных параметра — максимальный и минимальный показатели степени <tex>$e_{max}$</tex> и <tex>e_{min}</tex>. | ||
Строка 31: | Строка 31: | ||
Чаще всего такая ситуация возникает при попытке представить числа, имеющие слишком длинное или вообще бесконечное представление (пример с 0.1). | Чаще всего такая ситуация возникает при попытке представить числа, имеющие слишком длинное или вообще бесконечное представление (пример с 0.1). | ||
В этом случае нужное нам число лежит где-то между двумя числами с плавающей точкой и будет представляться одним из них. | В этом случае нужное нам число лежит где-то между двумя числами с плавающей точкой и будет представляться одним из них. | ||
- | Реже встречается попытка использовать числа, меньшие | + | Реже встречается попытка использовать числа, меньшие чем <tex>1.0\times\beta^{e_{min}}</tex>, или большие чем <tex>\beta.0\times\beta^{e_{max}}</tex>. |
- | Подробнее об | + | Подробнее об этих случаях речь пойдёт в разделе "Стандарт IEEE". |
- | == | + | Введём ещё одну договорённость. |
- | == | + | Пока что представление чисел с плавающей точкой неуникально. |
- | == | + | Например, при <tex>$\beta=10$</tex> и <tex>$p=3$</tex> число 0.1 можно представить как <tex>0.01\times 10^{1}</tex> и как <tex>1.00\times 10^{-1}</tex>. |
+ | Представление числа, в старшей позиции которого стоит цифра, отличная от нуля <tex>\left(d_0\neq 0\right)</tex>, мы будем называть ''нормализованным''. | ||
+ | Использование нормализованных форм решает проблему неединственности представления чисел с плавающей точкой. | ||
+ | (Однако, при такой договорённости возникает интересный вопрос — как представлять 0?) | ||
+ | |||
+ | ===Машинный эпсилон=== | ||
+ | Как известно, существует 2 вида погрешностей вычисления — абсолютная и относительная ([[Ошибки вычислений]]). | ||
+ | Под относительной погрешностью понимается отношение | ||
+ | |||
+ | ::<tex>\delta(\tilde a)=\frac{|\tilde a-a|}{a},</tex> | ||
+ | |||
+ | где <tex>\tilde a</tex> – значение, полученное при округлении, а <tex>a</tex> - точное значение вычислений. | ||
+ | |||
+ | Представим, что результатом округления действительного числа стало число | ||
+ | <tex>$d.dd\dots d\times\beta^e$</tex>. | ||
+ | Худшему случаю округления соответствует абсолютная погрешность, равная | ||
+ | <tex>$0.00 \dots 0\beta'\times\beta^e$</tex>, где <tex>\beta'=\beta/2</tex>. В мантиссе результата округления <tex>p</tex> позиций , в мантиссе абсолютной погрешности <tex>p+1</tex> позиция. | ||
+ | |||
+ | При попытке написать неравенство для относительной погрешности, соответствующей упомянутой выше абсолютной погрешности, несложно получить, что | ||
+ | |||
+ | ::<tex>\left(1/2\right)\beta^{-p}\leq\delta\leq\left(\beta/2\right)\beta^{-p}</tex>. | ||
+ | |||
+ | Величину <tex>\eps=\left(\beta/2\right)\beta^{-p}</tex> принято называть ''машинным эпсилоном'' (''machine epsilon''). | ||
+ | Таким образом можно утверждать, что при округлении дробного числа ближайшим к нему числом с плавающей точкой относительная погрешность округления не превосходит машинного эпсилона. | ||
+ | |||
+ | ''Существует и другое определение. Машинный эпсилон можно определить как минимальное положительное число, которое будучи прибавлено к единице даёт результат отличный от единицы. Читателю предлагается проверить эквивалентность этих определений самостоятельно.'' | ||
+ | |||
+ | == Стандарт IEEE == | ||
+ | Существует два разных стандарта IEEE для чисел с плавающей точкой. IEEE 754 - двоичный стандарт и требует, чтобы <tex>\beta=2</tex>, а <tex>p=24</tex> для одинарной точности (''single'') и <tex>p=53</tex> для двойной точности (''double''). | ||
+ | Также в стандарте IEEE 754 точно обговорено использование битов при представлении чисел в одинарной и двойной точностях. | ||
+ | В стандарте IEEE 854 <tex>\beta</tex> может принимать значение 10 или 2. | ||
+ | Также ничего не говорится о распределении битов между мантиссой и степенью. | ||
+ | |||
+ | Понятие '''стандарт IEEE''' используется для обозначения свойств, присущих обоим из перечисленных стандартов. | ||
+ | |||
+ | === Основание степени === | ||
+ | Выбор в качестве основания степени 10 не требует особых разъяснений. | ||
+ | Десятичная система - система, привычная для человека. | ||
+ | В случае двоичной системы стоит обсудить некоторые достоинства, присущие ей. | ||
+ | Мы договорились использовать нормализованные формы чисел. | ||
+ | Если <tex>\beta=2</tex>, то в старшей позиции может стоять только 1. Это даёт нам возможность не хранить эту единицу в памяти и тем самым получить дополнительный бит для мантиссы. | ||
+ | В этом случае принято говорить, что стандарт использует ''скрытый бит'' (''hidden bit''). | ||
+ | |||
+ | Вернёмся к вопросу о представлении нуля в нормализованной форме. | ||
+ | Ноль соответствует нулевой мантиссе и степени <tex>e_{min}-1</tex>. Таким образом ноль представляется в виде <tex>1.0\times 2^{e_{min}-1}</tex>. | ||
+ | |||
+ | === Точность представления === | ||
+ | |||
+ | Стандарт IEEE предлагает 4 разных точности: одинарная (''single''), двойная (''double''), одинарная расширенная (''single-extended'') и двойная расширенная (''double-extended''). | ||
+ | IEEE 754 жёстко обговаривают число бит одинарной и двойной точности. | ||
+ | Это означает, что на всех ЭВМ, поддерживающих IEEE 754, количество бит в представлении чисел с одинарной точностью и с двойной точностью фиксированы. | ||
+ | Количество бит расширенных точностей жёстко не фиксируется. | ||
+ | Расширенные форматы призваны хоть немного увеличить количество бит на мантиссу и на показатель степени. | ||
+ | Ниже представлена таблица параметров различных точностей в стандарте IEEE. | ||
+ | |||
+ | {| border="1" cellpadding="10" cellspacing="0" align="center" | ||
+ | |+'''Форматы''' | ||
+ | |- | ||
+ | |rowspan=2 | Параметры | ||
+ | |colspan="4"| Формат | ||
+ | |- | ||
+ | | Single | ||
+ | | Single-extended | ||
+ | | Double | ||
+ | | Double-extended | ||
+ | |- | ||
+ | | p | ||
+ | | 24 | ||
+ | | 32 | ||
+ | | 53 | ||
+ | | 64 | ||
+ | |- | ||
+ | |<tex>e_{max}</tex> | ||
+ | | +127 | ||
+ | | 1023 | ||
+ | | +1023 | ||
+ | | <tex>>16383</tex> | ||
+ | |- | ||
+ | |<tex>e_{min}</tex> | ||
+ | | -126 | ||
+ | | <tex>\leq-1022</tex> | ||
+ | | -1022 | ||
+ | | <tex>\leq-16382</tex> | ||
+ | |- | ||
+ | | Показатель степени | ||
+ | | 8 бит | ||
+ | | <tex>\leq 11</tex> бит | ||
+ | | 11 бит | ||
+ | | 15 бит | ||
+ | |- | ||
+ | | Длинна записи | ||
+ | | 32 бит | ||
+ | | 43 бит | ||
+ | | 64 бит | ||
+ | | 79 бит | ||
+ | |} | ||
+ | |||
+ | Приведём ещё одну таблицу для наглядности. | ||
+ | |||
+ | {| border="1" cellpadding="10" cellspacing="0" align="center" | ||
+ | |- | ||
+ | | | ||
+ | | Single | ||
+ | | Double | ||
+ | |- | ||
+ | | Самое маленькое нормализованное число | ||
+ | | <tex>2^{-126}</tex> (примерно <tex>1.175494351\times10^{-38}</tex>) | ||
+ | | <tex>2^{-1022}</tex> (примерно <tex>2.2250738585072020\times10^{-308}</tex>) | ||
+ | |- | ||
+ | | Самое большое нормализованное число | ||
+ | | <tex>(1-2^{-24})\times 2^{128}</tex> (примерно <tex>3.4028235\times10^{38}</tex>) | ||
+ | | <tex>(1-(1/2)^{53})\times 2^{1024}</tex> (примерно <tex>1.7976931348623157\times10^{308}</tex>) | ||
+ | |- | ||
+ | | Машинный эпсилон | ||
+ | | <tex>2^{-23}</tex> | ||
+ | | <tex>2^{-52}</tex> | ||
+ | |} | ||
+ | |||
+ | === Показатель степени === | ||
+ | |||
+ | Показатель степени может принимать как положительные так и отрицательные значения. | ||
+ | Это означает, что нужно определить метод представления показателя степени в бинарном виде. | ||
+ | |||
+ | Существует несколько общепринятых методов. Например, резервировать один бит на знак, как это реализовано в представлении мантиссы. | ||
+ | Однако IEEE использует другой метод - ''метод со смещением''. | ||
+ | Для одинарного и двойного формата вводятся смещения - 127 и 1023 соответственно. | ||
+ | Допустим, <tex>k</tex> - значение бинарного вида показателя экспоненты в смысле беззнаковой величины. Тогда показатель экспоненты определяется как <tex>k-127</tex> для одинарной точности и как <tex>k-1023</tex> для двойной. | ||
+ | |||
+ | Из таблицы следует, что для одинарного формата <tex>e_{min}=-126</tex> и <tex>e_{max}=127</tex>. | ||
+ | Может возникнуть вопрос: почему <tex>\left|e_{min}\right|<\left|e_{max}\right|</tex>? | ||
+ | Это сделано для того, чтобы величина обратная к минимальному по модулю числу <tex>\left(1/2^{e_{min}}\right)</tex> не выходила за рамки представимости. | ||
+ | (Однако, при этом величина обратная к максимальному числу становится гарантированно меньше минимального представимого числа. Дело в том, что переполнение - куда более серьёзная проблема, чем потеря значимости.) | ||
+ | |||
+ | В 8 бит, выделенные на показатель степени в одинарном формате, уместится 256 различных значений (от 0 до 255). | ||
+ | Это соответствует диапазону показателей степени от -127 до 128. | ||
+ | Зачем используется показатель -127 (<tex>e_{min}-1</tex>) мы уже знаем. | ||
+ | Об использовании значения 128 (<tex>e_{max}+1</tex>) речь пойдёт в разделе "Специальные величины". | ||
+ | |||
+ | === Операции и округление=== | ||
+ | |||
+ | В стандарте IEEE основными арифметическими операциями является сложение, вычитание, деление, умножение и извлечение квадратного корня. При вычислении значения выражений применяется ''чётное'' округление. | ||
+ | |||
+ | Стандарт IEEE требует, чтобы результаты основных арифметических операций были ''точно округлены'' (''exactly rounded''). | ||
+ | Это означает, что сначала должен быть вычислен точный ответ, а потом он должен быть округлён до ближайшего числа с плавающей точкой. | ||
+ | |||
+ | Само понятие ''округление'' на самом деле прозрачно — за исключением округления чисел вида 12.5. | ||
+ | К какому из чисел 12 и 13 его округлить? | ||
+ | Существует два различных подхода к этому вопросу. | ||
+ | Первый - разделить множество {0,1,2,3,4,5,6,7,8,9} пополам на {0,1,2,3,4} и {5,6,7,8,9} и первое округлять вниз, а второе — наверх. | ||
+ | Второй подход — округлять числа так, чтобы в наименее значащей позиции после округления стояло чётное число. Например, 12.5 округлять в 12, а 10.1235 — в 10.124. Такое округление называется ''чётным''. | ||
+ | |||
+ | В стандарте IEEE используется чётное округление. | ||
+ | |||
+ | Также стандарт IEEE вводит гарантии касательно дополнительных операций - взятия остатка от деления и перевода целых чисел (integer) в числа с плавающей точкой (и наоборот). | ||
+ | Результаты этих операций должны быть также точно округлены. | ||
+ | В отличие от этих операций нет никаких гарантий по поводу перевода между десятичным и двоичным представлениями. | ||
+ | Дело в том, что существуют достаточно эффективные алгоритмы округления всех операций, кроме операции перевода из десятичной формы в двоичную. | ||
+ | |||
+ | ''Ещё одним интересным вопросом является округление значений трансцендентных функций (Функций, которые не могут быть выражены конечным числом суперпозиций стандартных арифметических операций). | ||
+ | Стандарт IEEE не гарантирует точного округления значений таких функций. | ||
+ | Хорошим примером является округление значений экспоненты. | ||
+ | <tex>\exp(1.626)=5.0835</tex>. | ||
+ | К какому значению округлять <tex>\exp(1.626)</tex> — к 5.083 или к 5.084? | ||
+ | Для округления сначала надо получить ''точное'' значение функции. | ||
+ | При увеличении точности <tex>\exp(1.626)=5.08350</tex>, затем <tex>\exp(1.626)=5.083500</tex>, затем <tex>\exp(1.626)=5.0835000</tex>. | ||
+ | Для принятия решения нам нужно определить чему из <tex>5.0835000\dots 00d</tex> или <tex>5.0834999\dots 999d</tex> равна <tex>\exp(1.626)</tex>. | ||
+ | Понятно, что в случае экспоненты мы не гарантированно доберёмся до интересующей нас позиции. | ||
+ | Поэтому в случае трансцендентных функций нет смысла требовать, чтобы значение было сначала получено с бесконечной точностью и затем округлено''. | ||
+ | |||
+ | |||
+ | === Специальные значения === | ||
+ | |||
+ | В стандарте IEEE предложено 3 вида специальных значений - NaN, ноль со знаком и бесконечность со знаком. | ||
+ | |||
+ | В таблице ниже приведены представления этих специальных значений в стандарте IEEE. | ||
+ | |||
+ | {| border="1" cellpadding="10" cellspacing="0" align="center" | ||
+ | |+'''Специальные значения''' | ||
+ | |- | ||
+ | | Показатель степени | ||
+ | | Дробная часть мантиссы | ||
+ | | Обозначение | ||
+ | |- | ||
+ | | <tex>e=e_{min}-1</tex> | ||
+ | | f=0 | ||
+ | | <tex>\pm 0</tex> | ||
+ | |- | ||
+ | | <tex>e=e_{min}</tex> | ||
+ | | <tex>f\neq 0</tex> | ||
+ | | <tex>0.f\times2^{e_{min}}</tex> | ||
+ | |- | ||
+ | | <tex>e_{min}\leq e\leq e_{max}</tex> | ||
+ | | — | ||
+ | | <tex>1.f\times2^e</tex> | ||
+ | |- | ||
+ | | <tex>e=e_{max}+1</tex> | ||
+ | | f=0 | ||
+ | | <tex>Inf</tex> | ||
+ | |- | ||
+ | | <tex>e=e_{max}+1</tex> | ||
+ | | <tex>f\neq0</tex> | ||
+ | | <tex>NaN</tex> | ||
+ | |} | ||
+ | |||
+ | |||
+ | Представим, что у нас есть программа. | ||
+ | При работе эта программа в какой-то момент пытается извлечь корень из -4. | ||
+ | Если бы в стандарте не было никаких резервированных значений и все битовые последовательности выражали бы соответствующие им числа, то не было бы выхода лучше, чем остановить работу программы с сообщением об ошибке. | ||
+ | |||
+ | Именно для таких случаев в стандарте IEEE существуют специальные значения. | ||
+ | |||
+ | ==== NaN ==== | ||
+ | |||
+ | NaN (''Not a number'') используется стандартом IEEE для обработки ситуаций вида извлечения корня из отрицательного числа. | ||
+ | |||
+ | Приведём небольшую таблицу, демонстрирующую случаи возвращения NaN. | ||
+ | |||
+ | {| border="1" cellpadding="10" cellspacing="0" align="center" | ||
+ | |+'''Операции, возвращающие NaN''' | ||
+ | |- | ||
+ | | Операция | ||
+ | | Случай, когда возникает NaN | ||
+ | |- | ||
+ | | + | ||
+ | | <tex>Inf + \left(-Inf\right)</tex> | ||
+ | |- | ||
+ | | <tex>\times</tex> | ||
+ | | <tex>0\times Inf</tex> | ||
+ | |- | ||
+ | | / | ||
+ | | <tex>0/0, Inf/Inf</tex> | ||
+ | |- | ||
+ | | REM | ||
+ | | <tex>x REM 0,\ Inf REM y</tex> | ||
+ | |- | ||
+ | | <tex>\sqrt{x}</tex> | ||
+ | | <tex>\sqrt{x}\ \left(x<0\right)</tex> | ||
+ | |} | ||
+ | |||
+ | В битовом представлении NaN не оговаривается, какое значение должна принимать мантисса. | ||
+ | Единственное ограничение — она не должна быть нулевой. | ||
+ | Этот факт используется для передачи определённой системной информации через мантиссу. | ||
+ | Таким образом существует много различных значений вида NaN — каждое для своего случая. | ||
+ | |||
+ | Предположим, что мы вычисляем значение некоторого выражения, например <tex>\left(a+b+c\right)/d</tex>. | ||
+ | Допустим, <tex>a</tex> принимает значение NaN. | ||
+ | В этом случае итоговое значение выражения также равно NaN. | ||
+ | Если рассматривается некоторое длинное выражение, в ходе вычисления которого возникает значение NaN, то системная информация в мантиссе должна соответствовать тому значению NaN, которое возникло первым. | ||
+ | Исключением является, например, сложение двух NaN. В этом случае мантисса будет соответствовать одному из них, не обязательно первому. | ||
+ | |||
+ | Приведём хороший пример, демонстрирующий важность этого специального значения. | ||
+ | Предположим, что у нас есть программа, вычисляющая нули функции. | ||
+ | Мы хотим реализовать её так, чтобы она не требовала интервал поиска в качестве входного аргумента. | ||
+ | Такая реализация может вызвать проблему — что, если программа попытается вычислить значение функции вне области её определения? | ||
+ | В частности, программа может попытаться взять квадратный корень от -4. | ||
+ | Если бы программа выдала сообщение об ошибке и остановила свою работу она была бы для нас бесполезна. | ||
+ | Существование NaN даёт нам возможность вернуть его в качестве результата взятия квадратного корня и продолжить работу. | ||
+ | |||
+ | ==== Бесконечность ==== | ||
+ | |||
+ | Бесконечность существует для решения таких ситуаций, как переполнение и деление на ноль. | ||
+ | При переполнении можно было бы возвращать максимально представимое число с плавающей точкой. | ||
+ | Однако такое решение не всегда оправдано. | ||
+ | Гораздо выгоднее знать, что произошло переполнение, и принять надлежащие меры, получив в качестве результата <tex>Inf</tex>. | ||
+ | Существует положительная и отрицательные бесконечности. | ||
+ | При получении <tex>Inf</tex> существует способ определить по какой причине произошла ошибка — из-за переполнения или из-за деления на ноль. | ||
+ | Эта информация доступна в флагах состояния. | ||
+ | |||
+ | Арифметика с использованием <tex>Inf</tex> интуитивна ясна: при делении конечной величины на <tex>Inf</tex> результат будет нулём; при сложении или вычитании из конечной величины <tex>Inf</tex> результат будет <tex>Inf</tex> или <tex>-Inf</tex> соответственно. | ||
+ | |||
+ | Приведём небольшой пример бесконечной арифметики. | ||
+ | |||
+ | Допустим, мы работаем с функцией | ||
+ | |||
+ | ::<tex>x/\left(x^2+1\right)</tex> | ||
+ | |||
+ | Данная запись функции не очень хороша. | ||
+ | При <tex>x>sqrt{\beta}\beta^{e_{max}/2}</tex> в знаменателе будет вызвано переполнение и результатом будет 0. | ||
+ | Это некорректно, так как возвращаемым результатом должна быть величина порядка <tex>1/x</tex>. | ||
+ | Перепишем формулу в другом виде. | ||
+ | |||
+ | ::<tex>1/\left(x+x^{-1}\right)</tex> | ||
+ | |||
+ | Эта формула не будет так скоро вызывать переполнения. | ||
+ | В нуле она также будет принимать корректное значение, так как <tex>Inf^{-1}</tex> округлится нулём. | ||
+ | |||
+ | Этот пример показывает основное достоинство использования бесконечной арифметики: использование <tex>Inf</tex> часто позволяет обойти проверки многочисленных крайних случаев. | ||
+ | |||
+ | ==== Ноль со знаком ==== | ||
+ | |||
+ | Ноль соответствует нулевой мантиссе и показателю степени <tex>e_{min}-1</tex>. | ||
+ | В зависимости от значения знакового бита может быть <tex>+0</tex> и <tex>-0</tex>. | ||
+ | Обоснуем ввод этих специальных значений. | ||
+ | |||
+ | Для начала сделаем интересное замечание: в стандарте IEEE определено, что <tex>+0=-0</tex>. | ||
+ | Это сделано для того, чтобы при условных операторах вида <tex>if(x==0)</tex> не возникало неопределённости. | ||
+ | Но это не означает, что стандарт не различает двух этих значений. | ||
+ | При умножении чисел на нули со знаками или при делении нулей со знаками на числа знаки определяются в соответствие с обычной знаковой арифметикой. Например, <tex>(+0)\times 3=+0</tex> и <tex>(-0)/10=-0</tex>. | ||
+ | |||
+ | Предположим, что у нуля не было бы знака. | ||
+ | Тогда при <tex>x=\pm Inf</tex> возникла бы неопределённость с вычислением значения выражения <tex>1/(1/x)</tex>. | ||
+ | Неопределённость заключается в том, что и <tex>1/{+Inf}</tex> и <tex>1/{-Inf}</tex> принимали бы значение 0. | ||
+ | В тоже время <tex>1/0</tex> принимало бы логически верное значение <tex>+Inf</tex>. | ||
+ | Другими словами, | ||
+ | |||
+ | ::<tex>1/(1/x)\neq x</tex>. | ||
+ | |||
+ | Учитывая существование бесконечностей со знаками единственно верным решением рассматриваемой проблемы является ввод нулей со знаками. | ||
+ | |||
+ | Приведём ещё один пример. | ||
+ | |||
+ | Рассмотрим функцию <tex>\log(x)</tex>. | ||
+ | Предположим, что <tex>x</tex> — очень маленькое отрицательное число. Если бы оно округлялось нулём, то результатом бы была <tex>-Inf</tex>, что, конечно, неправильно. | ||
+ | В стандарте IEEE не возникает такой проблемы. | ||
+ | В этом случае <tex>x</tex> округляется <tex>-0</tex> и возвращается значение NaN. | ||
+ | |||
+ | ==== Ненормализованные числа ==== | ||
+ | |||
+ | Последним специальным значением стандарта IEEE являются ненормализованные числа. | ||
+ | |||
+ | Рассмотрим пример. | ||
+ | Пусть <tex>p=3</tex>, <tex>\beta=10</tex> и <tex>e_{min}=-98</tex>. | ||
+ | Числа <tex>6.87\times 10^{-97}</tex> и <tex>6.81\times 10^{-97}</tex> — числа с плавающей точкой, отличающиеся от минимально представимого числа больше чем в 10 раз. | ||
+ | У этих чисел есть интересная особенность : их разность равна нулю, хотя они не равны друг другу. | ||
+ | Это происходит потому, что <tex>x-y=6.0\times 10^{-99}</tex> округляется нулём. | ||
+ | Нам бы хотелось, чтобы привычное нам тождество | ||
+ | |||
+ | ::<tex>x=y <=> x-y=0</tex> | ||
+ | |||
+ | выполнялось всегда. | ||
+ | Без выполнения этого тождества достаточно сложно писать программы, оперирующие с дробными числами. | ||
+ | Пришлось бы в код программы включать множество проверок и условных операторов. | ||
+ | |||
+ | Ввод ненормализованных чисел решает эту проблему. | ||
+ | |||
+ | Суть состоит в том, что при показателе степени равном <tex>e_{min}</tex> мантисса не должна быть нормализованной. | ||
+ | Таким образом при <tex>p=3</tex>, <tex>\beta=10</tex> и <tex>e_{min}=-98</tex> <tex>1.0\times 10^{-98}</tex> уже не минимально представимое число. <tex>0.98\times 10^{-98}</tex> также является корректным числом с плавающей точкой. | ||
+ | |||
+ | == Доступ к формату в различных компиляторах == | ||
+ | |||
+ | === Visual Studio C++ (2003, 2005) === | ||
+ | |||
+ | В папке include установочной директории VC существует стандартный хидер "float.h", в котором описаны основные параметры форматов float, double и long double. | ||
+ | Также существует хидер "limits.h", в котором описан ряд функций по работе со специальными значениями. | ||
+ | |||
+ | === Borland C compiler (3.1) === | ||
+ | |||
+ | В той же папке include находится хидер "float.h" | ||
+ | |||
+ | === GCC compiler (3.4) === | ||
+ | |||
+ | В папке установки (usr/lib/gcc/...) есть всё таже папка include с хидерами. В ней есть файл "float.h". | ||
== Список литературы == | == Список литературы == | ||
* ''David Goldberg.'' What Every Computer Scientist Should Know About Floating-Point Arithmetic. ACM Computing Surveys, Vol. 23, No. 1 (March 1991), pages 5--48. | * ''David Goldberg.'' What Every Computer Scientist Should Know About Floating-Point Arithmetic. ACM Computing Surveys, Vol. 23, No. 1 (March 1991), pages 5--48. | ||
- | + | == См. также == | |
+ | * [[Практикум ММП ВМК, 4й курс, осень 2008]] | ||
{{stub}} | {{stub}} | ||
+ | |||
+ | [[Категория:Учебные задачи]] |
Текущая версия
Содержание |
Введение
Практически любой язык программирования даёт возможность использовать в вычислениях дробные числа. Когда дело касается программной реализации численных методов или любых других вычислений на ЭВМ, важным вопросом является внутреннее представление чисел, с которым приходится работать программисту. От этого главным образом зависит точность вычислений,а также их скорость.
В этом отчёте будут рассматриваться те аспекты представления чисел в ЭВМ, которые важны пользователям, желающим активно работать с вещественными величинами. Вначале будут введены общепринятые понятия для дальнейшего изложения материала. Будет достаточно подробно рассмотрен наиболее часто используемый стандарт IEEE 754. В заключение будут приведены способы доступа к основным параметрам представления вещественных чисел в ряде компиляторов (Microsoft Visual Studio (2003,2005), Borland C (3.1), GCC(3.4) ).
Числа с плавающей точкой
Числа с плавающей точкой - общепринятая форма представления действительных чисел в ЭВМ.
Основными параметрами такой формы представления является основание степени (base) и точность
(precision).
При этом всегда требуется, чтобы основание степени было целым чётным числом.
Если
и
, то число 0.1 представляется в виде
.
Однако, очевидно, что при определённых параметрах некоторые числа не удастся представить точно. Например, при
и
то же самое число 0.1 представляется приблизительно в виде
(поскольку в бинарном представлении число 0.1 имеет бесконечный вид).
В общем случае при заданных параметрах запись вида
представляет число
При этом называется мантиссой числа и состоит из
позиций.
В дальнейшем под числом с плавающей точкой мы будем понимать действительные числа точно представимые в смысле данной формы.
Существуют ещё два важных параметра — максимальный и минимальный показатели степени и
.
Таким образом, при фиксированных параметрах мы можем представить
разных чисел с учётом знака.
Здесь возникает проблема - что делать с числами, не представимыми точно.
Чаще всего такая ситуация возникает при попытке представить числа, имеющие слишком длинное или вообще бесконечное представление (пример с 0.1).
В этом случае нужное нам число лежит где-то между двумя числами с плавающей точкой и будет представляться одним из них.
Реже встречается попытка использовать числа, меньшие чем , или большие чем
.
Подробнее об этих случаях речь пойдёт в разделе "Стандарт IEEE".
Введём ещё одну договорённость.
Пока что представление чисел с плавающей точкой неуникально.
Например, при и
число 0.1 можно представить как
и как
.
Представление числа, в старшей позиции которого стоит цифра, отличная от нуля
, мы будем называть нормализованным.
Использование нормализованных форм решает проблему неединственности представления чисел с плавающей точкой.
(Однако, при такой договорённости возникает интересный вопрос — как представлять 0?)
Машинный эпсилон
Как известно, существует 2 вида погрешностей вычисления — абсолютная и относительная (Ошибки вычислений). Под относительной погрешностью понимается отношение
где – значение, полученное при округлении, а
- точное значение вычислений.
Представим, что результатом округления действительного числа стало число
.
Худшему случаю округления соответствует абсолютная погрешность, равная
, где
. В мантиссе результата округления
позиций , в мантиссе абсолютной погрешности
позиция.
При попытке написать неравенство для относительной погрешности, соответствующей упомянутой выше абсолютной погрешности, несложно получить, что
.
Величину принято называть машинным эпсилоном (machine epsilon).
Таким образом можно утверждать, что при округлении дробного числа ближайшим к нему числом с плавающей точкой относительная погрешность округления не превосходит машинного эпсилона.
Существует и другое определение. Машинный эпсилон можно определить как минимальное положительное число, которое будучи прибавлено к единице даёт результат отличный от единицы. Читателю предлагается проверить эквивалентность этих определений самостоятельно.
Стандарт IEEE
Существует два разных стандарта IEEE для чисел с плавающей точкой. IEEE 754 - двоичный стандарт и требует, чтобы , а
для одинарной точности (single) и
для двойной точности (double).
Также в стандарте IEEE 754 точно обговорено использование битов при представлении чисел в одинарной и двойной точностях.
В стандарте IEEE 854
может принимать значение 10 или 2.
Также ничего не говорится о распределении битов между мантиссой и степенью.
Понятие стандарт IEEE используется для обозначения свойств, присущих обоим из перечисленных стандартов.
Основание степени
Выбор в качестве основания степени 10 не требует особых разъяснений.
Десятичная система - система, привычная для человека.
В случае двоичной системы стоит обсудить некоторые достоинства, присущие ей.
Мы договорились использовать нормализованные формы чисел.
Если , то в старшей позиции может стоять только 1. Это даёт нам возможность не хранить эту единицу в памяти и тем самым получить дополнительный бит для мантиссы.
В этом случае принято говорить, что стандарт использует скрытый бит (hidden bit).
Вернёмся к вопросу о представлении нуля в нормализованной форме.
Ноль соответствует нулевой мантиссе и степени . Таким образом ноль представляется в виде
.
Точность представления
Стандарт IEEE предлагает 4 разных точности: одинарная (single), двойная (double), одинарная расширенная (single-extended) и двойная расширенная (double-extended). IEEE 754 жёстко обговаривают число бит одинарной и двойной точности. Это означает, что на всех ЭВМ, поддерживающих IEEE 754, количество бит в представлении чисел с одинарной точностью и с двойной точностью фиксированы. Количество бит расширенных точностей жёстко не фиксируется. Расширенные форматы призваны хоть немного увеличить количество бит на мантиссу и на показатель степени. Ниже представлена таблица параметров различных точностей в стандарте IEEE.
Параметры | Формат | |||
Single | Single-extended | Double | Double-extended | |
p | 24 | 32 | 53 | 64 |
+127 | 1023 | +1023 | | |
-126 | | -1022 | | |
Показатель степени | 8 бит | | 11 бит | 15 бит |
Длинна записи | 32 бит | 43 бит | 64 бит | 79 бит |
Приведём ещё одну таблицу для наглядности.
Single | Double | |
Самое маленькое нормализованное число | | |
Самое большое нормализованное число | | |
Машинный эпсилон | | |
Показатель степени
Показатель степени может принимать как положительные так и отрицательные значения. Это означает, что нужно определить метод представления показателя степени в бинарном виде.
Существует несколько общепринятых методов. Например, резервировать один бит на знак, как это реализовано в представлении мантиссы.
Однако IEEE использует другой метод - метод со смещением.
Для одинарного и двойного формата вводятся смещения - 127 и 1023 соответственно.
Допустим, - значение бинарного вида показателя экспоненты в смысле беззнаковой величины. Тогда показатель экспоненты определяется как
для одинарной точности и как
для двойной.
Из таблицы следует, что для одинарного формата и
.
Может возникнуть вопрос: почему
?
Это сделано для того, чтобы величина обратная к минимальному по модулю числу
не выходила за рамки представимости.
(Однако, при этом величина обратная к максимальному числу становится гарантированно меньше минимального представимого числа. Дело в том, что переполнение - куда более серьёзная проблема, чем потеря значимости.)
В 8 бит, выделенные на показатель степени в одинарном формате, уместится 256 различных значений (от 0 до 255).
Это соответствует диапазону показателей степени от -127 до 128.
Зачем используется показатель -127 () мы уже знаем.
Об использовании значения 128 (
) речь пойдёт в разделе "Специальные величины".
Операции и округление
В стандарте IEEE основными арифметическими операциями является сложение, вычитание, деление, умножение и извлечение квадратного корня. При вычислении значения выражений применяется чётное округление.
Стандарт IEEE требует, чтобы результаты основных арифметических операций были точно округлены (exactly rounded). Это означает, что сначала должен быть вычислен точный ответ, а потом он должен быть округлён до ближайшего числа с плавающей точкой.
Само понятие округление на самом деле прозрачно — за исключением округления чисел вида 12.5. К какому из чисел 12 и 13 его округлить? Существует два различных подхода к этому вопросу. Первый - разделить множество {0,1,2,3,4,5,6,7,8,9} пополам на {0,1,2,3,4} и {5,6,7,8,9} и первое округлять вниз, а второе — наверх. Второй подход — округлять числа так, чтобы в наименее значащей позиции после округления стояло чётное число. Например, 12.5 округлять в 12, а 10.1235 — в 10.124. Такое округление называется чётным.
В стандарте IEEE используется чётное округление.
Также стандарт IEEE вводит гарантии касательно дополнительных операций - взятия остатка от деления и перевода целых чисел (integer) в числа с плавающей точкой (и наоборот). Результаты этих операций должны быть также точно округлены. В отличие от этих операций нет никаких гарантий по поводу перевода между десятичным и двоичным представлениями. Дело в том, что существуют достаточно эффективные алгоритмы округления всех операций, кроме операции перевода из десятичной формы в двоичную.
Ещё одним интересным вопросом является округление значений трансцендентных функций (Функций, которые не могут быть выражены конечным числом суперпозиций стандартных арифметических операций).
Стандарт IEEE не гарантирует точного округления значений таких функций.
Хорошим примером является округление значений экспоненты.
.
К какому значению округлять
— к 5.083 или к 5.084?
Для округления сначала надо получить точное значение функции.
При увеличении точности
, затем
, затем
.
Для принятия решения нам нужно определить чему из
или
равна
.
Понятно, что в случае экспоненты мы не гарантированно доберёмся до интересующей нас позиции.
Поэтому в случае трансцендентных функций нет смысла требовать, чтобы значение было сначала получено с бесконечной точностью и затем округлено.
Специальные значения
В стандарте IEEE предложено 3 вида специальных значений - NaN, ноль со знаком и бесконечность со знаком.
В таблице ниже приведены представления этих специальных значений в стандарте IEEE.
Показатель степени | Дробная часть мантиссы | Обозначение |
| f=0 | |
| | |
| — | |
| f=0 | |
| | |
Представим, что у нас есть программа.
При работе эта программа в какой-то момент пытается извлечь корень из -4.
Если бы в стандарте не было никаких резервированных значений и все битовые последовательности выражали бы соответствующие им числа, то не было бы выхода лучше, чем остановить работу программы с сообщением об ошибке.
Именно для таких случаев в стандарте IEEE существуют специальные значения.
NaN
NaN (Not a number) используется стандартом IEEE для обработки ситуаций вида извлечения корня из отрицательного числа.
Приведём небольшую таблицу, демонстрирующую случаи возвращения NaN.
Операция | Случай, когда возникает NaN |
+ | |
| |
/ | |
REM | |
| |
В битовом представлении NaN не оговаривается, какое значение должна принимать мантисса. Единственное ограничение — она не должна быть нулевой. Этот факт используется для передачи определённой системной информации через мантиссу. Таким образом существует много различных значений вида NaN — каждое для своего случая.
Предположим, что мы вычисляем значение некоторого выражения, например .
Допустим,
принимает значение NaN.
В этом случае итоговое значение выражения также равно NaN.
Если рассматривается некоторое длинное выражение, в ходе вычисления которого возникает значение NaN, то системная информация в мантиссе должна соответствовать тому значению NaN, которое возникло первым.
Исключением является, например, сложение двух NaN. В этом случае мантисса будет соответствовать одному из них, не обязательно первому.
Приведём хороший пример, демонстрирующий важность этого специального значения. Предположим, что у нас есть программа, вычисляющая нули функции. Мы хотим реализовать её так, чтобы она не требовала интервал поиска в качестве входного аргумента. Такая реализация может вызвать проблему — что, если программа попытается вычислить значение функции вне области её определения? В частности, программа может попытаться взять квадратный корень от -4. Если бы программа выдала сообщение об ошибке и остановила свою работу она была бы для нас бесполезна. Существование NaN даёт нам возможность вернуть его в качестве результата взятия квадратного корня и продолжить работу.
Бесконечность
Бесконечность существует для решения таких ситуаций, как переполнение и деление на ноль.
При переполнении можно было бы возвращать максимально представимое число с плавающей точкой.
Однако такое решение не всегда оправдано.
Гораздо выгоднее знать, что произошло переполнение, и принять надлежащие меры, получив в качестве результата .
Существует положительная и отрицательные бесконечности.
При получении
существует способ определить по какой причине произошла ошибка — из-за переполнения или из-за деления на ноль.
Эта информация доступна в флагах состояния.
Арифметика с использованием интуитивна ясна: при делении конечной величины на
результат будет нулём; при сложении или вычитании из конечной величины
результат будет
или
соответственно.
Приведём небольшой пример бесконечной арифметики.
Допустим, мы работаем с функцией
Данная запись функции не очень хороша.
При в знаменателе будет вызвано переполнение и результатом будет 0.
Это некорректно, так как возвращаемым результатом должна быть величина порядка
.
Перепишем формулу в другом виде.
Эта формула не будет так скоро вызывать переполнения.
В нуле она также будет принимать корректное значение, так как округлится нулём.
Этот пример показывает основное достоинство использования бесконечной арифметики: использование часто позволяет обойти проверки многочисленных крайних случаев.
Ноль со знаком
Ноль соответствует нулевой мантиссе и показателю степени .
В зависимости от значения знакового бита может быть
и
.
Обоснуем ввод этих специальных значений.
Для начала сделаем интересное замечание: в стандарте IEEE определено, что .
Это сделано для того, чтобы при условных операторах вида
не возникало неопределённости.
Но это не означает, что стандарт не различает двух этих значений.
При умножении чисел на нули со знаками или при делении нулей со знаками на числа знаки определяются в соответствие с обычной знаковой арифметикой. Например,
и
.
Предположим, что у нуля не было бы знака.
Тогда при возникла бы неопределённость с вычислением значения выражения
.
Неопределённость заключается в том, что и
и
принимали бы значение 0.
В тоже время
принимало бы логически верное значение
.
Другими словами,
.
Учитывая существование бесконечностей со знаками единственно верным решением рассматриваемой проблемы является ввод нулей со знаками.
Приведём ещё один пример.
Рассмотрим функцию .
Предположим, что
— очень маленькое отрицательное число. Если бы оно округлялось нулём, то результатом бы была
, что, конечно, неправильно.
В стандарте IEEE не возникает такой проблемы.
В этом случае
округляется
и возвращается значение NaN.
Ненормализованные числа
Последним специальным значением стандарта IEEE являются ненормализованные числа.
Рассмотрим пример.
Пусть ,
и
.
Числа
и
— числа с плавающей точкой, отличающиеся от минимально представимого числа больше чем в 10 раз.
У этих чисел есть интересная особенность : их разность равна нулю, хотя они не равны друг другу.
Это происходит потому, что
округляется нулём.
Нам бы хотелось, чтобы привычное нам тождество
выполнялось всегда. Без выполнения этого тождества достаточно сложно писать программы, оперирующие с дробными числами. Пришлось бы в код программы включать множество проверок и условных операторов.
Ввод ненормализованных чисел решает эту проблему.
Суть состоит в том, что при показателе степени равном мантисса не должна быть нормализованной.
Таким образом при
,
и
уже не минимально представимое число.
также является корректным числом с плавающей точкой.
Доступ к формату в различных компиляторах
Visual Studio C++ (2003, 2005)
В папке include установочной директории VC существует стандартный хидер "float.h", в котором описаны основные параметры форматов float, double и long double. Также существует хидер "limits.h", в котором описан ряд функций по работе со специальными значениями.
Borland C compiler (3.1)
В той же папке include находится хидер "float.h"
GCC compiler (3.4)
В папке установки (usr/lib/gcc/...) есть всё таже папка include с хидерами. В ней есть файл "float.h".
Список литературы
- David Goldberg. What Every Computer Scientist Should Know About Floating-Point Arithmetic. ACM Computing Surveys, Vol. 23, No. 1 (March 1991), pages 5--48.