Напомним, что в предыдущей статье, для простоты изложения, нами были введены следующие понятия. Область машинной мантиссы (ОММ) — это область машинного слова, в которую записывается мантисса числа. Область машинного порядка (ОМП) — это область машинного слова, в которую записывается порядок характеристики числа. Далее, в тексте, мы будем использовать эти понятия.
Итак, как известно, любое число, записанное в естественном виде, может быть представлено в эквивалентном ему экспоненциальном виде:
F = М• q^(±h)
где М представляет собой число, записанное в естественном виде, со смещенной точкой на h позиций в ту или иную сторону. Число М в такой записи принято называть мантиссой числа, а q^(±h) характеристикой числа с порядком ±h. Знак и величина порядка h компенсируют величину смещения точки относительно ее первоначального положения в числе, представленном в естественном виде
Когда мы ставим перед собой задачу записать некоторое число в машинное слово, мы, прежде всего, заботимся о том, чтобы в машинном слове было записано число с минимальной потерей точности. Этому условию удовлетворяет такая запись числа, при которой в ОММ записывается максимум значащих цифр мантиссы числа и, при этом, в ОМП не происходит переполнения.
Предположим, что мы имеем некоторое двоичное число, записанное в экспоненциальном виде с мантиссой, имеющей N разрядов и порядком характеристики, равным h. Рассмотрим случай, когда N?К., т.е., если число значащих цифр мантиссы записываемого числа превышает или равно количеству разрядов ОММ.
Например, пусть нам необходимо записать в машинное слово, в котором В =3, К=4 двоичное число, представленное в естественной форме как 11.011. В этом числе количество значащих цифр превышает количество разрядов ОММ. В экспоненциальном виде это число может иметь различные варианты записи, такие как: 11011•2^(-3); 11.011•2^0; 0.0011011•2^4; и проч.
Для того, чтобы число 11011.•2^(-3) записать в машинное слово с дробной мантиссой, необходимо точку в мантиссе числа смещать влево до тех пор пока в старшем разряде ОММ ни появится единица. На количество смещений точки необходимо откорректировать порядок характеристики мантиссы в ОМП. В нашем случае точку необходимо сместить на 5 разрядов влево. В ОМП тогда будет записано число 5-3=2. А в машинном слове, таким образом, будет записано число 0.1101•2^2. Младшая единица не вместилась в разрядную сетку ОММ и была потеряна. Аналогично будем иметь для числа 11.011•2^0. Чтобы его записать в наше машинное слово необходимо сместить точку на два разряда влево и соответственно увеличить порядок тоже на 2. В результате в машинном слове будет записано число 0.1101•2^2. Чтобы записать в машинное слово число 0.0011011•2^4, точку в нем необходимо сдвинуть на два разряда вправо, а порядок уменьшить также на 2. В результате, мы опять получаем записанное в машинном слове число 0.1101•2^2.
Во всех рассмотренных случаях, не зависимо от вида первоначальной записи числа, мы получили однозначное представление числа в машинном слове и поэтому необходимости в нормализации таких чисел не возникала.
Пусть теперь N<К. Число, удовлетворяющее этому условию, может быть записано в машинное слово различным образом.
Например, в машинном слове, в котором В =3, К=4, число 0.01 может быть представлено следующими вариантами:
0.1000 •2^(-1), 0.0100 •2^0, 0.001•2^1, 0.0001•2^2.
Ну и что? Почему нас это должно смущать? Все эти варианты записи числа 0.01 математически эквивалентны и, будучи использованными в математических преобразованиях, дают правильный результат.
Действительно, пусть в машинном слове число 0.01 представлено как 0.1000 •2^(-1). Сложим это число с двоичным числом 0.011, которое в машинном слове записано, как 0.11•2^(-1). Получим следующий результат:
0.1000 •2^(-1) + 0.11•2^(-1) = 1.01•2^(-1).
Поскольку старшая цифра числа вышла за рамки разрядной сетки ОММ, мы должны сместить точку на один разряд влево, а значение порядка увеличить на 1. В результате, в машинном слове будет записано число 0.1010•2^0.
Допустим теперь, что двоичное число 0.01 представлено в машинном слове в виде 0.0001•2^2. Сложим его с числом 0.011, которое теперь представлено в машинном слове как 0.0011•2^1. По правилам арифметики приведем порядки слагаемых к одинаковому значению и сложим преобразованные таким образом числа:
0.001•2^1+0.0011•2^1=0.0101•2^1.
Полученное в результате сложения число математически эквивалентно ранее полученному числу 0.1010•2^0 и может быть записано в машинное слово без дополнительных преобразований.
Таким образом, неоднозначность записи числа в машинном слове никак не влияет на корректность математических преобразований, в которых участвует это число. А поскольку под машинное слово в вычислительном устройстве отводится, как правило, строго определенное число разрядов, то нет никаких преимуществ в записи приведенных выше вариантов представления чисел в машинном слове с выбранными параметрами К и В.
Отсюда можно сделать очень важный вывод. Любая нормализация числа является операцией, приводящей к непродуктивному использованию вычислительных ресурсов.
Единственно о чем надо заботиться при записи чисел в машинное слово, это, чтобы их значения мантисс и порядков не выходили за пределы разрядной сетки машинного слова. Такая процедура предусмотрена в любом вычислительном устройстве, использующем арифметику с плавающей точкой. В случае обнаружения такого события, числа должны быть скорректированы таким образом, чтобы, по крайней мере, старшие разряды мантиссы, преобразованного числа, вместились в разрядную сетку ОММ.
Еще один очень важный вывод можно сделать из приведенных рассуждений. Отказ от процедуры нормализации чисел позволяет в явном виде получить значение нуля и естественным образом охватить диапазон малых чисел, без искусственного введения класса денормализованных чисел. Это позволяет существенно упростить процесс записи чисел в машинное слово и, как следствие, существенно уменьшить время выполнения математических операций.
ЛИТЕРАТУРА.
1. habrahabr.ru/post/262245
2. wiki.mvtom.ru/index.php/Формы_представления_чисел_в_ЭВМ
3. IEEE Standard for Binary Floating-Point Arithmetic. Copyright 1985 by The Institute of Electrical and Electronics Engineers, Inc 345 East 47th Street, New York, NY 10017 USA.
4. www.softelectro.ru/ieee754.html
5. neerc.ifmo.ru/wiki/index.php?title=Представление_вещественных_чисел&printable=yes
Юрий Спиридонов.
Комментарии (33)
Mrrl
13.07.2015 04:08+3А умножение денормализованных чисел не окажется сильно дороже, чем нормализованных? А сравнение? Нормализованные положительные числа можно сравнивать так же, как целые с той же двоичной записью — они идут в том же порядке. А у денормализованных? Считать разность порядков, выполнять сдвиг, и потом сравнивать сдвинутые значения? Да это почти так же дорого, как сложение нормализованных чисел.
Всё-таки, каждое число создаётся один раз, а в операциях может участвовать многократно. Не лучше ли потратить немного времени при создании, чем вставлять дополнительную обработку аргументов каждой операции?
leshabirukov
13.07.2015 15:09+1По правилам арифметики приведем порядки слагаемых к одинаковому значению и сложим преобразованные таким образом числа:
Вам придётся учитывать значение мантисс при этой операции, то есть фактически нормализовывать. Или будут переполнения\потери точности.
Innotor Автор
14.07.2015 19:10Учитывать значения мантисс при любой арифметической операции конечно необходимо, но зачем для этого нормализовывать числа? Вы же сами говорите, что учет значений мантисс, чтобы не было переполнения/потери точности, это и есть фактически нормализация. Тогда зачем нормализовывать уже нормализованное число?
При работе с большими числами нормализация происходит автоматически, при их правильной математической обработке. Проблемы возникают с малыми числами. Когда малые числа нормализуют, тогда и вылезают все неприятности. И нулем приходится жертвовать и вводить искусственно класс денормализованных чисел со всеми вытекающими…Mrrl
14.07.2015 19:19Ну, здесь разработчикам решать, что для них важнее — добавить лишние 15 десятичных порядков в диапазон (для double это всего 2.5% от всего диапазона), или объявить, что числа, для которых требуется денормализация — это машинный нуль, и избавиться от всей этой головной боли.
Innotor Автор
14.07.2015 19:28Здесь я согласен! Когда у тебя есть тяжелый микроскоп, зачем еще нужен молоток.
Innotor Автор
14.07.2015 19:24Поскольку 13.07.15 я был off-line и не мог вовремя реагировать. Хотелось бы ответить господину jcmvbkbc относительно проблемы нуля.
В нормализованных числах есть проблема получения нуля в явном виде. Отсюда возникает проблема сравнения на равенство двух чисел.
Для нормализованных чисел два числа считаются равными, если они отличаются друг от друга на «бесконечно» малую величину. Но, согласитесь, что с математической точки зрения, нуль и число, близкое к нулю, вещи разные.
Если, как предложено в статье, отказаться от нормализации чисел, то эта проблема с нулем решается, т.к. нуль представлен в явном виде… Одновременно появляется возможность оперировать с таким понятием, как бесконечно малое число.
encyclopedist
Нормализация же позволяет опускать всегда единичный старший разряд.
Innotor Автор
Слишком дорогой ценой дается такая экономия. Во-первых, невозможность получения в явном виде нуля и, во-вторых, необходимость введения денормализованных чисел. На выходе — огромный кусок бесполезной работы.
jcmvbkbc
Это вы говорите о программной реализации операций с плавающей точкой? А если реализация «железная»?
Как будто это не необходимость. Вполне можно считать нулём все числа с нулевым порядком, и некоторые реализации так и делают.
nerudo
Если реализация «железная» — значит вы уже переплатили 5$ за ваш процессор плюс команда выполняется на несколько тактов дольше, чем могла бы…
jcmvbkbc
Вот тебе раз. Откуда вы знаете, для чего мне был нужен мой процессор?
Какая команда? Почему дольше? Дольше по сравнению с чем?
splav_asv
В железе всё это тоже нужно реализовывать — а это и лишняя площать, лишнее тепло, лишняя сложность разводки кристалла.
jcmvbkbc
Практика показывает, что специализированное железо эффективнее справляется с задачами на которые оно рассчитано, чем программная реализация на универсальном железе.
splav_asv
Естественно. Но тут речь про то, что железо вынуждено делать лишнюю работу, следовать более сложному алгоритму. Понятно, что это оно сделает и сделает быстрее, чем программная эмуляция. Но на это уходят ресурсы. Бесплатно ничего не бывает.
А зачем эту работу делать — не очень понятно.
jcmvbkbc
Я не вижу обоснования того, что эта работа лишняя.
При выполнении сложений/вычитаний в любом случае придётся делать относительную нормализацию операндов, так, чтобы их порядки совпадали, либо отличались на 1. Для нормализованных чисел это делается только на основании значения порядка, для ненормализованных потребуется дополнительно смотреть на мантиссу.
При умножении и делении нормализованный результат содержит наибольшее количество значащих цифр.
splav_asv
Для сложения и вычитания как раз всё просто. В любом случае порядки могу отличаться и надо приводить к одному порядку.
А вот для умножения и деления действительно всё сложнее. Сходу не берусь судить, но нормализовать скорее всего придётся. Возможно проще делать это именно лениво — перед делением или умножением.
encyclopedist
Проблема со сложением-вычитанием в том, что надо определить, к какому именно порядке приводить. У нормализованных чисел — всегда к большему. У чисел автора — придётся анализировать мантиссы.
Пример: 0.0001*2^0 + 0.0001*2^4 (мантисса — 5 разрядов). Если приводить к большему порядку, то первое слагаемое обнулится. А правильный ответ 1.0001 * 2^0. Если поразмыслить, то можно придти к выводу что максимальня точность будет, когда порядки выравниваются так, что у большего слагаемого старший разряд 1. Что и есть нормализация!
splav_asv
Всё верно.
В случае нормализации сразу — сдвигать нужно как максимум 3 раза — две нормализации + приведение к большей мантиссе.
Если не делать нормализацию сразу — 2 приведения. Вычислять позицию старшей единички в любом слечае нужно 2 раза.
Innotor Автор
Это вы говорите о программной реализации операций с плавающей точкой? А если реализация «железная»?
Innotor Автор
Извините, я тут нечаянно не ту клавишу нажал. Выше была цитата:).Простите чайника.
Мой ответ: Не зависимо, как реализуется алгоритм, программно или в железе, сложный алгоритм реализуется сложно.
Денормализованные числа — это конечно необходимость. Именно поэтому за них так много «платят». А если убрать нормализацию, как показано в статье, то они ничем не отличаются от прочих, «нормальных» чисел.
jcmvbkbc
У вас есть какие-нибудь подтверждения? Я в своём комментарии привёл ссылочку на раздел «Disabling denormal floats at the code level» в статье о денормализованных числах, где утверждается ровно обратное.
Innotor Автор
Говоря, что денормализованные числа, это необходимость, я имел ввиду, что необходимостью является решение проблемы работы с малыми числами. Одной из решения такой проблемы является просто отказаться от их использования. Но ведь, как я показал в статье, отказавшись от ненужной операции нормализации, мы бесплатно получаем возможность работы с малыми числами.
jcmvbkbc
Вы показали математическую эквивалентность результатов арифметических операций при отсутствии нормализации и при её наличии на конкретном примере. Из этого не следует ненужность нормализации, поскольку она может быть полезна по другим соображениям. Т.е. фразе «Любая нормализация числа является операцией, приводящей к непродуктивному использованию вычислительных ресурсов.» не хватает обоснования. Таким обоснованием мог бы быть программный код реализующий арифметику без нормализации и работающий не медленнее кода, реализующего арифметику с нормализацией, при сохранении численного равенства результатов для всех возможных значений операндов.
Innotor Автор
Хотелось бы услышать эти соображения. В каких случаях нормализация полезна и в чем ее польза. Основная проблема, ради которой была предложена нормализация, это ликвидация неоднозначности представления экспоненциальных чисел. В статье показано, что неоднозначность представления чисел не является проблемой и потому нормализация не нужна.
Я не являюсь профессиональным программистом. Однако мне кажется, что быстродействие любого алгоритма зависит прежде всего от сложности этого алгоритма. А для того, чтобы сравнить, как быстро работает сопроцессор FPU, использующий числа с плавающей точкой с нормализацией и без нее, надо реализовать обработку чисел в самом сопроцессоре.
jcmvbkbc
Некоторое время назад я разрабатывал эмулятор 80-битной арифметики (а её особенность в том, что 80-битное представление сохраняет единичный бит целой части в мантиссе) для 16-битного процессора. Из опыта этой разработки я могу отметить следующие моменты, приходящие в голову в связи с нормализацией:
— умножение: нормализованные аргументы можно умножать сразу, результат имеет понятное выравнивание. Т.е. умножая 1 на 1 в двоичном виде мы умножаем старшие разряды 0x8000 на 0x8000 и получаем 0x40000000. В итоговом результате надо проверить только старший бит, и если он нулевой — сдвинуть всё на один бит влево и увеличить порядок.
В отсутствие нормализации придётся либо искать значащие цифры результата, либо нормализовать два аргумента.
— сложение/вычитание: всегда сдвигается максимум один аргумент, всегда вправо.
В отсутствие нормализации может возникнуть ситуация, когда придётся сдвигать один аргумент влево, а другой вправо.
Для эффективности железной реализации будут другие мерки — сколько потребуется транзисторов и какова будет максимальная достижимая частота. Но тут у меня нет соображений, поскольку железом на этом уровне я почти не занимаюсь.
Innotor Автор
Поправьте меня, если я ошибаюсь. В Вашем примере 1 — это мантисса числа. В числе, возможно, присутствует характеристика 2^h_1. Т.е. первое число равно 1• 2^(h_1). Второе число равно 1• 2^(h_2). Умножаем первое на второе и получаем: 1• 2^(h_1)•1• 2^(h_2) = 1• 2^(h_1+h_2). Мантисса здесь не изменилась. Изменился только порядок характеристики. Если порядок не вызвал переполнения, то он записывается в машинное слово без изменений.
Предположим теперь, что числа не нормализованы. По условию ненормализованных по стандарту чисел, мантисса машинного слова может быть только дробным числом. Тогда оба наших числа из Вашего примера оказываются за пределами разрядной сетки машинной мантиссы. Числа, которые выходят за область определения разрядной сетки машинной мантиссы должны быть приведены к необходимому виду, как при условии нормализации так и без нее. В таком виде они и должны храниться.В нашем случае числа должны быть приведены к виду, когда они меньше 0. Это похоже на нормализацию. Но условия нормализации другие. Где находится старший разряд в мантиссе слагаемого не имеет значения. Важно, чтобы полученный результат не вышел за пределы области машинной мантиссы. Если нет переполнения разрядной сетки машинной мантиссы, то результат будет верен и записывается в машинное слово в том виде, как получен при вычислении.
Innotor Автор
Извините, опять напутал с выделением цитат.
jcmvbkbc
Ок, давайте я распишу свои примеры более подробно:
Умножение: умножаем 1 на 1. В нормализованном виде это 2^0 * 1, в двоичном представлении: порядок 0x3fff, мантисса: 0x80000000_00000000. При умножении 64-битных мантисс получается 128-битное произведение, из которого нужно выбрать 64-битный результат. Мы выбираем старшие 64 бита (с 64го по 127й) если 127й бит равен 1 (дополнительно увеличивая экспоненту результата на 1) либо старшие 64 бита (с 63го по 126й) в противном случае.
Т.е. 0x80000000_00000000 * 0x80000000_00000000 = 0x40000000_00000000_00000000_00000000, результат: биты с 63го по 126й, мантисса: (0x3fff — 0x3fff) + (0x3fff — 0x3fff) + 0x3fff = 0x3fff.
Теперь представьте, что числа ненормализованные, т.е. единица находится в произвольном месте мантиссы.
Для того, чтобы выбрать 64 бита результата нужно просканировать произведение в поисках самого старшего установленного бита и взять 64 бита начиная с него, т.е. фактически выполнить нормализацию. «Начиная с него», а не «начиная с какого-нибудь раньше него, но так чтобы захватить его», потому что там будут значащие биты произведения, которых может быть все 128.
Речь об аргументах и их взаимной нормализации. Например вычтем (или прибавим, в данном случае не важно) из ненормализованной 1, представленной в двоичном виде как порядок: 0x403e, мантисса: 0x00000000_00000001 ненормализованную 1/4, представленную как порядок: 0x3ffd, мантисса: 0x80000000_00000000.
Для выполнения этого действия мантиссу 1 придётся сдвинуть налево, а мантиссу 1/4 — направо, так, чтобы обе единицы остались в пределах 64 бит, но старший бит 1 был бы левее старшего бита 1/4. Сдвигом только одной мантиссы этого добиться нельзя.
Innotor Автор
Чтобы огромное количество нулей не затрудняло понимания вопроса, давайте масштабируем Ваш пример:
следующим образом.
Умножаем 1 на 1. В нормализованном виде это 2^0 * 1. В двоичном представлении: порядок 0x0, мантисса: 0x08. При умножении 4-битных мантисс получается 8-битное произведение, из которого нужно выбрать 4-битный результат. Мы выбираем старшие 4 бита (с 4 го по 7й) если 7й бит равен 1 (дополнительно увеличивая экспоненту результата на 1) либо старшие 4 бита (с 3го по 6й) в противном случае.
Т.е. 0x08 * 0x08 = 0x40, результат: биты с 3го по 6й, порядок равен 0.
Здесь я дословно привел Ваш пример в другом масштабе, только порядки представил без смещения. Мне кажется, что суть от этого не изменилась.
Рассмотрим теперь эту последовательность действий на шестнадцатеричных и двоичных числах:
0х08*0х08 = 0х40 = 1000*1000 = 0100 0000.
Далее дословно (с учетом масштабирования):
мы выбираем старшие 4 бита (с 4 го по 7й) если 7й бит равен 1 (дополнительно увеличивая экспоненту результата на 1) либо старшие 4 бита (с 3го по 6й) в противном случае.
У нас 7й бит равен 0, значит выбираем второй вариант.
Второй шаг равносилен сдвигу разрядов полученного числа влево на единицу. Число увеличилось в 2 раза, следовательно порядок должен быть уменьшен на 1. Будем иметь:
0100 0000 = 1000 0000*2^(-1). В старшем 7м разряде появилась единица. Следовательно, далее, по вашему алгоритму, преобразования должны завершиться. Надо выбрать 4 старших разряда и
порядок увеличить на 1. Получаем число, записанное в машинном слове, как 0х08 и порядок, равный нулю.
Рассмотрим теперь, как выглядят преобразования, когда числа не нормализуются. Поскольку мантисса машинного слова — дробная, число 1 будет представлено как 0.1*2^1. В области машинной мантиссы будет записано число 1000, а в области машинного порядка будет записано число 1. умножим это число само на себя и получим:
1000*1000 = 01000000. С учетом того, что мантисса у нас дробная, ее значение будет равно 0.01.
Порядок полученного числа будет равен 1+1=2. Сдвигаем полученное число влево до тех пор пока в старшем разряде области машинной мантиссы не появится 1. Всего нужно произвести 1 сдвиг. На такое же число уменьшаем порядок, который становится равным 2-1=1. В машинную область мантиссы записываем только 4 старших разряда. Больше не поместится. Таким образом, в результате, в машинном слове будет записано число 1000, а в области машинного порядка число 1. Что соответствует числу 0.1*2^1.
Является ли это нормализацией? Я бы назвал это оптимизацией. При больших числах нормализация и оптимизация алгоритмически совпадают. Но при маленьких числах нормализация дает совсем другой результат.
Вы правы, сдвигом мантиссы только одного числа этого не добиться.
Здесь надо подумать.
jcmvbkbc
Именно. При умножении номализованных аргументов сдвигов всегда либо 0, либо 1. При умножении ненормализованных — здесь цикл сканирования битов.
Innotor Автор
Согласен, нормализация дает положительный эффект при проведении математических операций. Но, видимо, до тех пор, пока речь не идет о малых числах. О таких числах, когда порядок числа достигает своего минимального значения и приходиться переходить к денормализованным числам. Если нормализацию заменить оптимизацией, т.е. числа представлять так, чтобы старший единичный разряд мантиссы числа всегда, когда это возможно, занимал крайнее левое положение, то тем самым мы получаем все преимущества нормализованных чисел. Но, в тех случаях, когда оптимизация приводит к антипереполнению, числа должны записываться без изменений. Признаком таких малых чисел является наличие нуля в старшем разряде мантиссы числа.
Innotor Автор
Чтобы сложить или вычесть два числа надо выравнять их порядки. В случае нормализованных чисел всегда сдвигается вправо мантисса числа с меньшим порядком. Влево нормализованное число сдвигаться не может по определению.
Для чисел ненормализованных, чтобы обеспечить оптимальное сложение, надо, наоборот, в числе с большим порядком сдвигать мантиссу влево и одновременно уменьшать значение порядка до тех пор пока, либо порядки не выравняются, либо, пока в старшем разряде мантиссы ни появится единица. В последнем случае, если порядки слагаемых не сравнялись, надо сдвигать мантиссу числа с меньшим порядком вправо, увеличивая значение порядка этого числа, пока порядки слагаемых не сравняются. Пример. 0.001*2^(2)+0.01*2(-1). Порядок первого слагаемого больше порядка второго слагаемого. Будем сдвигать мантиссу первого слагаемого влево: 0.001*2^(2)=0.01*2^(1)=0.1*2^(0). Дальнейшее смещение мантиссы невозможно. Будем смещать мантиссу второго слагаемого вправо: 0.01*2(-1)=0.001*2(0). Порядки сравнялись, можно найти сумму: 0.1*2^(0)+0.001*2^(0)=0.101*2^(0). Мы здесь обошлись без нормализации, а результат автоматически получился записанным оптимальным образом, т.е. дробная мантисса в старшем разряде имеет единицу.
Innotor Автор
Нормализация придумана прежде всего для решения проблемы неоднозначности представления чисел в машинном слове. Экономия же одного бита, это побочный положительный эффект, ради которого вряд-ли стали бы городить огород.