Что такое нормализованное представление вещественных чисел и для чего оно используется

Математические основы информатики

Представление вещественных чисел

Вещественные числа в компьютере хранятся в формате с плавающей запятой, который опирается на нормализованную форму записи чисел.

Нормализованная запись числа

Если при представлении целых чисел в компьютере ограничением может служить лишь величина записываемого числа, то при записи вещественного числа речь в первую очередь идет о точности его представления, т. е. о количестве значащих цифр, которые удается сохранить в ограниченном числе разрядов.

Пример 6. Допустим, мы имеем калькулятор, в котором на экране дисплея для вывода чисел есть только 10 знакомест (включая знак числа и запятую между целой и дробной частями десятичного числа). Если нам необходимо работать с числами

то на дисплее нашего калькулятора отобразить удастся лишь второе из них (первое число занимает 11 знакомест, второе — 6 знакомест, третье — 13 знакомест).

Эта задача может быть решена» если числа представить несколько иначе. Забегая вперед, скажем, что для примера 6 искомый способ записи чисел в калькуляторе таков :

где знак «Е» читается как «умножить на десять в степени». Такая запись отражает экспоненциальную форму записи чисел.

Определение 3. Любое число а в экспоненциальной форме представляется в виде , где Р — основание системы счисления, т называется мантиссой числа, q — порядком числа.

Пример 7. Длину отрезка, равного 47,8 см, в экспоненциальной форме записи можно представить так:

2) 4,78 х 10 1 см = 4,78 дм;

3) 47,8 х 10 0 см = 47,8 см;

4) 0,478 х 10 2 см = 0,478 м.

Из этого примера видно, что длину одного и того же отрезка можно записать с использованием различных экспоненциальных форм. Эта неоднозначность записи может приводить в определенных случаях к неудобству. Из курса алгебры известно, что если Р фиксировано и 1/Р ≤ m

Заметим, что число ноль не может быть записано в нормализованной форме так, как она была определена. Поэтому относительно нормализованной записи нуля приходится прибегать к особым соглашениям. Условимся, что запись нуля является нормализованной, если и мантисса, и порядок равны нулю.

В нормализованной форме все числа записываются одинаково в том смысле, что запятая у них ставится в одном и том же месте — перед первой (самой левой) значащей цифрой мантиссы. Заметим, что в двоичной системе счисления первая цифра мантиссы нормализованного числа всегда равна 1 (за исключением числа ноль). Величина же числа (т. е. ее порядок) указывается отдельно, с помощью соответствующей степени основания системы счисления, в которой это число было записано изначально. Количество цифр в мантиссе может оказаться меньше, чем число значащих цифр в исходном числе. Часто в нормализованной записи мантисса Р-ичного числа записывается в Р-ичной системе счисления, а порядок и само число Р — в десятичной.

Пример 8. Приведем примеры нормализации чисел:

1) 0 = 0,0 х 10 0 (возможная нормализация нуля);

2) 3,1415926 = 0,31415926 х 10 1 (количество значащих цифр не изменилось);

3) 1000 = 0,1 х 10 4 (количество значащих цифр уменьшилось с четырех до одной);

4) 0,123456789 = 0,123456789 х 10 0 (запятую передвигать не нужно);

6) 1000,0001₂ = 0,10000001₂ х 2 4 (количество значащих цифр уменьшить невозможно);

7) AB,CDEF₁₆ = 0,ABCDEF₁₆ x 16 2 (количество значащих цифр уменьшить невозможно).

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

! В компьютерном представлении вещественных чисел максимально допустимое количество цифр в мантиссе определяет точность, с которой может быть представлено число.

Поясним это на примере школьного калькулятора, который производит вычисления в десятичной системе счисления. Пусть это будет калькулятор с десятью знакоместами на дисплее, мантисса в нем имеет четыре цифры, порядок — две. В отличие от стандартной нормализации, у калькуляторов первая значащая цифра, с которой и начинается мантисса, изображается перед точкой. Порядок при этом соответственно уменьшается на единицу. Такая форма записи нормализованных чисел позволяет экономить одно знакоместо, так как вместо нуля в целой части мы помещаем значащую цифру.

1) Число 248,53786 в калькуляторе превращается в +2.485Е+02. Переводя последнее число в привычное представление с фиксированной запятой, получим +248,5.

3) Число 0,00024853786 в калькуляторе имеет вид +2.485Е-04, т. е. равно числу 0,0002485.

Следовательно, всякое десятичное число, состоящее не более чем из четырех значащих цифр в нормализованном виде, можно представить в таком калькуляторе точно, а остальные числа — лишь приближенно.

Определение 5. Модуль разности между значением числа х и неким его представлением х* (компьютерным, калькуляторным) называется абсолютной погрешностью представления х.

Несмотря на то, что в абсолютном исчислении погрешность может быть значительно больше 1, относительно величины самого числа ее порядок остается неизменным. Относительная погрешность представления чисел в примере 9 равна:

Определение 6. Относительной погрешностью представления х называют величину

Вопрос. Как вы думаете, что нам дает знание величин абсолютной и относительной погрешности при решении реальных задач на компьютере?

Ответ. Абсолютная погрешность говорит о том, на сколько полученный результат (например, результат представления числа в компьютере) отличается от истинного результата (в нашем примере — от самого числа).

При решении реальных задач знание этой величины позволяет оценивать, насколько достоверный результат был получен. Если его точность нас не удовлетворяет, то следует выбрать другой (более точный) способ представления чисел.

Относительная же погрешность показывает, сколько верных старших значащих цифр содержит результат. В примере 9 относительная погрешность представления разных по величине чисел равна 0,00015233. Такая относительная погрешность означает, что мы имеем три безусловно верные значащие цифры результата. Значение относительной погрешности непосредственно связано с количеством разрядов, отводимых для представления мантиссы нормализованного числа.

На практике обычно известна относительная погрешность представления чисел, так как разрядность мантиссы фиксирована. Следовательно, можно предположить, сколько верных цифр содержит результат. Если из каких-то априорных соображений известно значение вычисляемой величины, то можно оценить абсолютную погрешность результата.

В компьютерной записи вещественных чисел с плавающей запятой количество цифр, отводимых под запись порядка, определяет, насколько большие и насколько маленькие положительные числа могут быть представлены.

Покажем это опять на примере школьного калькулятора. В формате нашего калькулятора порядок имеет две цифры, и наибольшее число, которое может быть в нем представлено, — это +9.999Е+99. Если бы нам пришлось записать это число в формате с фиксированной запятой, оно имело бы ровно 100 цифр до запятой (четыре девятки и 96 нулей), т. е. это и в самом деле очень большое число.

А самое маленькое положительное число, которое можно ввести в нашем калькуляторе, — это +1.000Е-99. В формате с фиксированной запятой оно имеет 99 десятичных знаков после запятой, а именно 98 нулей и единицу. Это очень маленькое число. Таким образом, выражая порядок лишь двумя десятичными цифрами, можно записывать числа из очень широкого диапазона.

Широкий диапазон представления чисел с плавающей запятой необходим при решении научных и инженерных задач. Такое представление чисел не только позволяет сохранять в разрядной сетке большое количество значащих цифр и тем самым повышать точность вычислений, но также упрощает действия над порядками и мантиссами.

Представление вещественных чисел в формате с плавающей запятой

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

Например, можно представить себе такое распределение разрядов ячейки памяти:

Первые два разряда служат для представления знаков порядка (s_q) и мантиссы (s_m) соответственно. Следующие к разрядов используются для представления абсолютной величины порядка числа (q), остальные n разрядов — для представления абсолютной величины мантиссы. В каждом разряде ячейки может храниться одно из двух значений: 0 или 1.

Тогда изображенному на схеме состоянию ячейки соответствует число

Вещественных чисел, точно представимых в компьютере, конечное число. Остальные числа либо приближаются представимыми, либо оказываются непредставимыми. Последнее относится к слишком большим и к слишком маленьким вещественным числам.

Выполнение арифметических операций над вещественными числами

Использование в компьютере представления чисел в формате с плавающей запятой усложняет выполнение арифметических операций. При сложении и вычитании чисел сначала производится подготовительная операция, называемая выравниванием порядков. Она состоит в том, что мантисса числа с меньшим порядком сдвигается в своей ячейке вправо на количество разрядов, равное разности порядков данных чисел. После этой операции одноименные разряды мантисс оказываются расположенными в одноименных разрядах обеих ячеек, и теперь уже сложение или вычитание мантисс выполняется достаточно просто, так же как над числами с фиксированной запятой.

Пусть — два нормализованных двоичных числа, и . Результатом их сложения или вычитания будет являться следующее выражение:

После операций над порядками и мантиссами мы получаем порядок и мантиссу результата, но последняя, вообще говоря, может не удовлетворять ограничениям, накладываемым на мантиссы нормализованных чисел. Так как от результата арифметических операций в компьютере требуется, чтобы он также был нормализованным числом, необходимо дополнительное преобразование результата — нормализация. В зависимости от величины получившейся мантиссы результата, она сдвигается вправо или влево так, чтобы ее первая значащая цифра попала в первый разряд после запятой. Одновременно порядок результата увеличивается или уменьшается на число, равное величине сдвига.

Заметим, что над мантиссами в арифметическом устройстве могут выполняться все четыре арифметических действия, а также операции сдвига, тогда как над порядками производятся только действия сложения и вычитания. Отрицательные порядки можно записывать в дополнительном коде для того, чтобы операцию вычитания свести к операции сложения.

В ряде случаев, даже если некоторые два числа были представлены в формате с плавающей запятой абсолютно точно, результат выполнения над ними арифметических операций часто может содержать погрешность, а иногда может быть заведомо неверным.

Поясним более подробно особенности выполнения арифметических операций над вещественными числами на примерах. При этом будем считать, что в записи вещественного числа с плавающей запятой один разряд отводится под десятичный порядок и пять разрядов — под десятичную мантиссу.

Пример 11. Выполним сложение двух вещественных чисел:

При умножении двух целых чисел с плавающей запятой их порядки необходимо просто сложить, а мантиссы — перемножить (предварительное выравнивание не производится). При делении из порядка делимого надо вычесть порядок делителя, а мантиссу делимого разделить на мантиссу делителя.

Результатами выполнения операций умножения и деления нормализованных чисел а и b в арифметике с ограниченным числом разрядов будут:

Пример 13. Выполним умножение двух вещественных чисел:

Источник

Что нужно знать про арифметику с плавающей запятой

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

Арифметика с плавающей запятой почему-то считается экзотической областью компьютерных наук, учитывая, что соответствующие типы данных присутствуют в каждом языке программирования. Я сам, если честно, никогда не придавал особого значения компьютерной арифметике, пока решая одну и ту же задачу на CPU и GPU получил разный результат. Оказалось, что в потайных углах этой области скрываются очень любопытные и странные явления: некоммутативность и неассоциативность арифметических операций, ноль со знаком, разность неравных чисел дает ноль, и прочее. Корни этого айсберга уходят глубоко в математику, а я под катом постараюсь обрисовать лишь то, что лежит на поверхности.

1. Основы

Множество целых чисел бесконечно, но мы всегда можем подобрать такое число бит, чтобы представить любое целое число, возникающее при решении конкретной задачи. Множество действительных чисел не только бесконечно, но еще и непрерывно, поэтому, сколько бы мы не взяли бит, мы неизбежно столкнемся с числами, которые не имеют точного представления. Числа с плавающей запятой — один из возможных способов предсталения действительных чисел, который является компромиссом между точностью и диапазоном принимаемых значений.

Число с плавающей запятой состоит из набора отдельных разрядов, условно разделенных на знак, экспоненту порядок и мантиссу. Порядок и мантисса — целые числа, которые вместе со знаком дают представление числа с плавающей запятой в следующем виде:

Математически это записывается так:

Основание определяет систему счисления разрядов. Математически доказано, что числа с плавающей запятой с базой B=2 (двоичное представление) наиболее устойчивы к ошибкам округления, поэтому на практике встречаются только базы 2 и, реже, 10. Для дальнейшего изложения будем всегда полагать B=2, и формула числа с плавающей запятой будет иметь вид:

Что такое мантисса и порядок? Мантисса – это целое число фиксированной длины, которое представляет старшие разряды действительного числа. Допустим наша мантисса состоит из трех бит (|M|=3). Возьмем, например, число «5», которое в двоичной системе будет равно 101₂. Старший бит соответствует 2 2 =4, средний (который у нас равен нулю) 2 1 =2, а младший 2 0 =1. Порядок – это степень базы (двойки) старшего разряда. В нашем случае E=2. Такие числа удобно записывать в так называемом «научном» стандартном виде, например «1.01e+2». Сразу видно, что мантисса состоит из трех знаков, а порядок равен двум.

Допустим мы хотим получить дробное число, используя те же 3 бита мантиссы. Мы можем это сделать, если возьмем, скажем, E=1. Тогда наше число будет равно

2 = 10 (в двоичной системе) = 1.000e+1 = 0.100e+2 = 0.010e+3. (E=1, E=2, E=3 соответственно)

Обратите внимание, что одно и то же число имеет несколько представлений. Это не удобно для оборудования, т.к. нужно учитывать множественность представлния при сравнении чисел и при выполнении над ними арифметических операций. Кроме того, это не экономично, поскольку число представлений — конечное, а повторения уменьшают множество чисел, которые вообще могут быть представлены. Поэтому уже в самых первых машинах начали использовать трюк, делая первый бит мантиссы всегда положительным. Такое предаставление назвали нормализованным.

Это экономит один бит, так как неявную единицу не нужно хранить в памяти, и обеспечивает уникальность представления числа. В нашем примере «2» имеет единственное нормализованное представление («1.000e+1»), а мантисса хранится в памяти как «000», т.к. старшая единица подразумевается неявно. Но в нормализованном представлении чисел возникает новая проблема — в такой форме невозможно представить ноль.

Строго говоря, нормализованное число имеет следующий вид:

Качество решения задач во многом зависит от выбора представления чисел с плавающей запятой. Мы плавно подошли к проблеме стандартизации такого представления.

2. Немного истории

В 60-е и 70-е годы не было единого стандарта представления чисел с плавающей запятой, способов округления, арифметических операций. В результате программы были крайне не портабельны. Но еще большей проблемой было то, что у разных компьютеров были свои «странности» и их нужно было знать и учитывать в программе. Например, разница двух не равных чисел возвращала ноль. В результате выражения «X=Y» и «X-Y=0» вступали в противоречие. Умельцы обходили эту проблему очень хитрыми трюками, например, делали присваивание «X=(X-X)+X» перед операциями умножения и деления, чтобы избежать проблем.

Инициатива создать единый стандарт для представления чисел с плавающей запятой подозрительно совпала с попытками в 1976 году компанией Intel разработать «лучшую» арифметику для новых сопроцессоров к 8086 и i432. За разработку взялись ученые киты в этой области, проф. Джон Палмер и Уильям Кэхэн. Последний в своем интервью высказал мнение, что серьезность, с которой Intel разрабатывала свою арифметику, заставила другие компании объединиться и начать процесс стандартизации.

Все были настроены серьезно, ведь очень выгодно продвинуть свою архитектуру и сделать ее стандартной. Свои предложения представили компании DEC, National Superconductor, Zilog, Motorola. Производители мейнфреймов Cray и IBM наблюдали со стороны. Компания Intel, разумеется, тоже представила свою новую арифметику. Авторами предложенной спецификации стали Уильям Кэхэн, Джероми Кунен и Гарольд Стоун и их предложение сразу прозвали «K-C-S».

Практически сразу же были отброшены все предложения, кроме двух: VAX от DEC и «K-C-S» от Intel. Спецификация VAX была значительно проще, уже была реализована в компьютерах PDP-11, и было понятно, как на ней получить максимальную производительность. С другой стороны в «K-C-S» содержалось много полезной функциональности, такой как «специальные» и «денормализованные» числа (подробности ниже).

В «K-C-S» все арифметические алгоритмы заданы строго и требуется, чтобы в реализации результат с ними совпадал. Это позволяет выводить строгие выкладки в рамках этой спецификации. Если раньше математик решал задачу численными методами и доказывал свойства решения, не было никакой гарантии, что эти свойства сохранятся в программе. Строгость арифметики «K-C-S» сделала возможным доказательство теорем, опираясь на арифметику с плавающей запятой.

Компания DEC сделала все, чтобы ее спецификацию сделали стандартом. Она даже заручилась поддержкой некоторых авторитетных ученых в том, что арифметика «K-C-S» в принципе не может достигнуть такой же производительности, как у DEC. Ирония в том, что Intel знала, как сделать свою спецификацию такой же производительной, но эти хитрости были коммерческой тайной. Если бы Intel не уступила и не открыла часть секретов, она бы не смогла сдержать натиск DEC.

Подробнее о баталиях при стандартизации смотрите в интервью профессора Кэхэна, а мы рассмотрим, как выглядит представление чисел с плавающей запятой сейчас.

3. Представление чисел с плавающей запятой сегодня

Разработчики «K-C-S» победили и теперь их детище воплотилось в стандарт IEEE754. Числа с плавающей запятой в нем представлены в виде знака (s), мантиссы (M) и порядка (E) следующим образом:

Замечание. В новом стандарте IEE754-2008 кроме чисел с основанием 2 присутствуют числа с основанием 10, так называемые десятичные (decimal) числа с плавающей запятой.

Чтобы не загромождать читателя чрезмерной информацией, которую можно найти в Википедии, рассмотрим только один тип данных, с одинарной точностью (float). Числа с половинной, двойной и расширенной точностью обладают теми же особенностями, но имеют другой диапазон порядка и мантиссы. В числах одинарной точности (float/single) порядок состоит из 8 бит, а мантисса – из 23. Эффективный порядок определяется как E-127. Например, число 0,15625 будет записано в памяти как

Рисунок взят из Википедии

3.1 Специальные числа: ноль, бесконечность и неопределенность

Неопределенность или NaN (от not a number) – это представление, придуманное для того, чтобы арифметическая операция могла всегда вернуть какое-то не бессмысленное значение. В IEEE754 NaN представлен как число, в котором E=E_max+1, а мантисса не нулевая. Любая операция с NaN возвращает NaN. При желании в мантиссу можно записывать информацию, которую программа сможет интерпретировать. Стандартом это не оговорено и мантисса чаще всего игнорируется.

Вернемся к примеру. Наш E_min=-1. Введем новое значение порядка, E=-2, при котором числа являются денормализованными. В результате получаем новое представление чисел:

Интервал от 0 до 0,5 заполняют денормализованные числа, что дает возможность не проваливаться в 0 рассмотренных выше примерах (0,5-0,25 и 1,5-1,25). Это сделало представление более устойчиво к ошибкам округления для чисел, близких к нулю.

Но роскошь использования денормализованного представления чисел в процессоре не дается бесплатно. Из-за того, что такие числа нужно обрабатывать по-другому во всех арифметических операциях, трудно сделать работу в такой арифметике эффективной. Это накладывает дополнительные сложности при реализации АЛУ в процессоре. И хоть денормализованные числа очень полезны, они не являются панацеей и за округлением до нуля все равно нужно следить. Поэтому эта функциональность стала камнем преткновения при разработке стандарта и встретила самое сильное сопротивление.

3.4 Очередность чисел в IEEE754

Одна из удивительных особенностей представления чисел в формате IEEE754 состоит в том, что порядок и мантисса расположены друг за другом таким образом, что вместе образуют последовательность целых чисел для которых выполняется:

4.2 Неассоциативность арифметических операций

В арифметике с плавающей запятой правило (a*b)*c = a*(b*c) не выполняется для любых арифметических операций. Например,

Допустим у нас есть программа суммирования чисел.

Некоторые компиляторы по умолчанию могут переписать код для использования нескольких АЛУ одновременно (будем считать, что n делится на 2):

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

4.3 Числовые константы

Помните, что не все десятичные числа имеют двоичное представление с плавающей запятой. Например, число «0,2» будет представлено как «0,200000003» в одинарной точности. Соответственно, «0,2 + 0,2 ≈ 0,4». Абсолютная погрешность в отдельном
случае может и не высока, но если использовать такую константу в цикле, можем получить накопленную погрешность.

4.4 Выбор минимума из двух значений

4.5 Сравнение чисел

Очень распространенная ошибка при работе с float-ами возникает при проверке на равенство. Например,

Ошибка здесь, во-первых, в том, что 0,2 не имеет точного двоичного представления, а во-вторых 0,2 – это константа двойной точности, а переменная fValue – одинарной, и никакой гарантии о поведении этого сравнения нет.

Лучший, но все равно ошибочный способ, это сравнивать разницу с допустимой абсолютной погрешностью:

Недостаток такого подхода в том, что погрешность представления числа увеличивается с ростом самого этого числа. Так, если программа ожидает «10000», то приведенное равенство не будет выполняться для ближайшего соседнего числа (10000,000977). Это особенно актуально, если в программе имеется преобразование из одинарной точности в двойную.

Выбрать правильную процедуру сравнения сложно и заинтересованных читателей я отсылаю к статье Брюса Доусона. В ней предлагается сравнивать числа с плавающей запятой преобразованием к целочисленной переменной. Это — лучший, хотя и не портабельный способ:

5. Проверка полноты поддержки IEE754

Думаете, что если процессоры полностью соответствуют стандарту IEEE754, то любая программа, использующая стандартные типы данных (такие как float/double в Си), будет выдавать один и тот же результат на разных компьютерах? Ошибаетесь. На портабельность и соответствие стандарту влияет компилятор и опции оптимизации. Уильям Кэхэн написал программу на Си (есть версия и для Фортрана), которая позволяет проверить удовлетворяет ли связка «архитектура+компилятор+опции» IEEE754. Называется она «Floating point paranoia» и ее исходные тексты доступны для скачивания. Аналогичная программа доступна для GPU. Так, например, компилятор Intel (icc) по умолчанию использует «расслабленную» модель IEEE754, и в результате не все тесты выполняются. Опция «-fp-model precise» позволяет компилировать программу с точным соответствием стандарту. В компиляторе GCC есть опция «-ffast-math», использование которой приводит к несоответствию IEEE754.

Заключение

Напоследок поучительная история. Когда я работал над тестовым проектом на GPU, у меня была последовательная и параллельная версия одной программы. Сравнив время выполнения, я был очень обрадован, так как получил ускорение в 300 раз. Но позже оказалось, что вычисления на GPU «разваливались» и обращались в NaN, а работа с ними в GPU была быстрее, чем с обычными числами. Интересно было другое — одна и та же программа на эмуляторе GPU (на CPU) выдавала корректный результат, а на самом GPU – нет. Позже оказалось, что проблема была в том, что этот GPU не поддерживал полностью стандарт IEEE754 и прямой подход не сработал.

Сейчас арифметика с плавающей запятой почти совершенна. Практически всегда наивный подход сработает, и программа, не учитывающая все ее особенности, выдаст правильный результат, а описанные подводные камни касаются только экзотических случаев. Но нужно всегда оставаться бдительным: в таком вопросе как компьютерная математика легко наступить на грабли.

Источник