воскресенье, 26 мая 2013 г.

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



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


   В компьютере перевод происходит по иному, данная статья показывает, как добиться сходного результата на бумаге. В качестве рассматриваемого типа будет использован float, который соответствует типу IEEE754 Single precision 32-bit.
  Для чтения статьи вам изначально нужно знать двоичную систему исчисления.
There are 10 types of people in this world: those who understand binary and those who don't.
~Author Unknown

Вы должны легко переводить числа (к примеру, 185) в двоичную систему (10111001).
И значения в следующей таблице не вызывают у вас непонимания:
Степень
Значение
0
1
1
2
2
4
3
8
4
16
5
32
6
64
7
128

   Когда дело касается целочисленных то перевод в бинарный формат довольно легкий процесс, но когда дело доходит до дробных чисел, то форматов великое множество, и каждый раньше тянул одеяло в “истинно правильную” сторону своего личного формата. Но на сцену вышел формат IEEE 754, который принял пальму первенства и держит ее до сих пор.

История IEEE 754:
In 1976 Intel began planning to produce a floating point coprocessor. Dr John Palmer, the manager of the effort, persuaded them that they should try to develop a standard for all their floating point operations. William Kahan was hired as a consultant; he had helped improve the accuracy of Hewlett Packard's calculators. Kahan initially recommended that the floating point base be decimal[8] but the hardware design of the coprocessor was too far advanced to make that change.
The work within Intel worried other vendors, who set up a standardization effort to ensure a 'level playing field'. Kahan attended the second IEEE 754 standards working group meeting, held in November 1977. Here, he received permission from Intel to put forward a draft proposal based on the standard arithmetic part of their design for a coprocessor. The arguments over gradual underflow lasted until 1981 when an expert commissioned by DEC to assess it sided against the dissenters.
Even before it was approved, the draft standard had been implemented by a number of manufacturers.[9][10] The Intel 8087, which was announced in 1980, was the first chip to implement the draft standard.

   Идеален ли формат IEEE 754? Если верить статье «IEEE754-тика угрожает человечеству» Автора Юровицкий В.М МФТИ, РГСУ http://www.yur.ru/science/computer/IEEE754.htm
То IEEE 754 уже наломал немало дров:
  • Взрыв ракеты "Пэтриот» в Саудовской Аравии 25 февраля 1991, который привел к гибели 28 человек, связан с ошибками округления.
  • Взрыв ракеты Ариан-5 сразу после старта при ее первом испытании во Французской Гвиане 4 июня 1996 был следствием переполнения числовой сетки компьютера.
  • 23 августа 1991 в Гандсфиорде в Норвегии затонула нефтяная платформа, что привело к убытку почти в один миллиард долларов. Это, как предполагается, было результатом inaccurate finite element analysis.
Как уверяет автор - в будущем вероятность таких аварий и их тяжесть будет лишь увеличиваться.
  Но, IEEE 754 распространен повсеместно, нужно просто знать, что он не идеален и учитывать возможные погрешности при проектировании программ, к которым предъявляются повышенные требования.


Смысл лучше всего постигать на примере, переведем число  185,4375 в бинарный формат IEEE 754.
Для начала нужно перевести целое число (185) в двоичный формат (10111001)
Далее нужно перевести число после запятой (4375) в двоичный формат.
   Но делается это не так как с целыми числами. Процесс основан на утверждении, что любая дробь не может быть больше единицы. То есть,  какое бы у нас число ни было после запятой, оно всегда будет в пределе от нуля до единицы, дробь 0,4375 не исключение
Для выражения числа в диапазоне от 0 до 1 нам поможет следующая таблица:
Степень
Значение
1/2
0.5
1/4
0.25
1/8
0.125
1/16
0.0625
1/32
0.03125
1/64
0.015625
1/128
0.0078125

   Битовое выражение строится все на том же принципе сумм, но теперь складываем не степени двойки (2,4,8…) а дроби (1/2, 1/4, 1/8…). Число 0,4375 состоит из суммы 0,25+0,125+0,0625.  Да, действительно, для простоты примера я заранее подобрал число из суммы этих значений, но не все дроби так легко подбираются. К примеру, попробуйте перевести число 0,2 его невозможно подобрать ровно, а самое близкое значение из суммы дробей будет 0,20000000298023223876953125 .
   Итак, число 0,4375 в двоичном формате 01110000
   Теперь у нас есть два числа в бинарном формате, целое(10111001) и дробь (01110000) если записать их в строчку, как одно число, то получим 10111001, 01110000 но бинарный формат не поддерживает запятых, только ноли и единицы. Обратимся к формату:
 
Бинарное представление числа 0,15625 Рисунок из статьи http://en.wikipedia.org/wiki/IEEE_754-1985
·         Первый бит это знак: 0 положительное число; 1 отрицательное.
·         Зеленая область – экспонента
·         Розовая – мантисса
   Имея на руках число (185,4375) и его бинарное представление  (10111001, 01110000) мы можем легко вычислить знак, мантиссу и экспоненту.
Число 185,4375  положительное, то есть первый бит 0
0
































   Далее вычисляем мантиссу (просто убираем запятую между числами 10111001, 01110000) 1011100101110000
При вычислении мантиссы существует несколько правил:
1.          Мантисса всегда должна начинаться с единицы, к примеру, возьмем число 5.5, в бинарном формате 5 будет 00000101, а его дробная часть 10000000, запишем его в строчку 00000101,10000000 и вычислим мантиссу 10110000000. Как видите, все ноли до единицы были просто отброшены.
2.          Так как для мантиссы используется всего 23 бита, вместо 24 (один бит съел знак числа) и мантисса всегда начинаться с единицы. То первая единица отбрасывается (она всегда подразумевается, хоть и не записывается, но первая единица “как бы” есть всегда). Эта мантисса с отброшенной первой единицей и записывается, что бы различать мантиссы я ее называю “записываемая мантисса”, но это не официальное название. Записываемая мантисса позволяет записать в 23 бита последовательность из 24 бит.
 Вернемся к числу 185.4375,  его мантисса равна 1011100101110000, на ее основе  вычисляем записываемую мантиссу 011100101110000 и записываем ее.
0








0
1
1
1
0
0
1
0
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0

Настало время экспоненты.
    Число 185,4375  (10111001, 01110000), его записываемая мантисса 01110010111000000000000. Воображаемо поставим в записываемой мантиссе запятую, так чтобы разделить число на целую и дробную части 0111001,0111000000000000.  Не забудьте, что в записываемой мантиссе не указывается первая единица, но она подразумевается, по сути, эта запись 0111001,0111000000000000 = 10111001,0111000000000000. Если подсчитаете, то запятую в записываемой мантиссе мы поставили через 7 битов, число 7 и есть экспонента. Благодаря экспоненте всегда можно выделить из мантиссы целое число и его дробь.
   Дальше формат IEEE 754 вновь подкидывает нам пару «НО»:
1.          Экспонента может быть как положительной, так и отрицательной (случай с отрицательной экспонентой разберем чуть дальше). Чтобы убрать отрицательные числа из 8ми битной экспоненты, бит отвечающий за 128 изначально выставлен в единицу, максимальная сумма всех оставшихся битов равна 127 это число и есть максимальное значение экспоненты.  При максимально возможной отрицательной экспоненте -127 их сумма 128 + (-127) равна единице, благодаря чему компьютер избавляется от необходимости работать с отрицательными числами. Число 127 это максимальное смещение для мантиссы, в любую сторону, как в лево, так и в право.
   Казалось бы, все просто используем в экспоненте 10000000 для обозначения нулевого сдвига, диапазон от 100000001 до 11111111 для положительных значений, а диапазон от 011111111 до 00000001  для отрицательных и все отлично, но вылезает второе “НО”. 
2.          По всей видимости, при разработке стандарта обратили внимание на то, что одно значение в экспоненте не учитывается (00000000), или стояла иная задача, но в итоге, числа с плавающей запятой способны иметь бесконечное значение.
   Еще со времен школы нам говорили, что на ноль делить нельзя - результат окажется бесконечностью. А числа с плавающей запятой на ноль делить можно.
Вот простой код на C#
using System;

namespace Infinity
{
    class Program
    {
        static void Main()
        {
            Console.WriteLine(12345f / 0);
        }
    }
}
   В этом коде мы делим число 12345 на ноль. Запись 12345f, говорит о том, что это число типа float которое соответствует типу IEEE754 Single precision 32-bit.
Результат выполнения программы:
 
  На экспоненту это влияет следующим образом – экспонента 11111111 занята бесконечностью и не может представлять 127ый положительный сдвиг. Выходят из этого положения так: экспонента рассчитывается по формуле 128 + сдвиг – 1.
Теперь значения экспоненты:
·         11111111 – бесконечность
·         01111111 – нулевой сдвиг
·         10000000 – 11111110 положительный сдвиг
·         01111110 – 00000000 отрицательный сдвиг
   Поэтому экспонента числа 185,4375 рассчитывается 128 + 7 -1 = 134, переводим в двоичный формат 10000111 и записываем.
0
1
0
0
0
0
1
1
0
0
1
1
1
0
0
1
0
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0

Мы записали число 185,4375  в бинарном формате IEEE 754
Можно проверить себя на сайте http://www.binaryconvert.com


Разберем случаи с различными экспонентами:
   Положительная экспонента бывает, в случае если целое число (не зависимо от знака) больше или равно 2. Пример положительной экспоненты мы рассмотрели с числом 185,4375
   Отрицательная экспонента бывает, в случае если целое число равно нулю (не зависимо от знака).
   Разберем на примере:
  1. Возьмем число 0,125 переведем его в бинарный формат и запишем в строчку 00000000,00100000.
  2. Получим мантиссу 100000 и вычислим записываемую мантиссу 00000.
  3. Чтобы получить обратно два числа (целое и дробное) нужно сдвинуть записываемую мантиссу на 3 бита вправо это и будет экспонентой, то есть экспонента равна -3.
    128 +(-3)-1 = 124 = 01111100
  4. Совместим получившиеся данные в месте и проверим себя:
    Знак 0; Экспонента 01111100; Мантисса 00000


   Экспонента с нулевым сдвигом бывает, в случае если целое число равно единице (не зависимо от знака).
   Разберем на примере:
  1. Возьмем число -1,375 переведем его в бинарный формат и запишем в строчку 00000001,01100000
  2. Получим мантиссу 101100000 и вычислим записываемую мантиссу 01100000
  3. Чтобы получить обратно два числа (целое и дробное) нам не нужно никуда сдвигать запятую, так как она стоит в правильном месте.
    128 + 0 – 1 = 127 = 01111111
  4. Совместим получившиеся данные вместе и проверим себя
    Знак 1 (так как число отрицательное); Экспонента 01111111; Мантисса 01100000


   Бесконечная экспонента бывает при делении на ноль.
Бесконечность бывает как положительная, так и отрицательная:

 



Обзор был бы неполным,если не упомянуть о NaN.
NaN – Not a Number (не число).   http://ru.wikipedia.org/wiki/NaN
К операциям, приводящим к появлению NaN в качестве ответа,относятся:
  • все математические операции, содержащие NaN в качестве одного из операндов;
  • деление нуля на ноль;
  • деление бесконечности на бесконечность;
  • умножение нуля на бесконечность;
  • сложение бесконечности с бесконечностью противоположного знака;
  • вычисление квадратного корня отрицательного числа;
  • логарифмирование отрицательного числа.

Так же NaN делится на 2 вида:
  • Quiet NaN
  • Signaling NaN
Quiet NaN – как видно из названия “тихий NaN” является простым NaN и не передает ни какой дополнительной информации. В бинарном представлении это бесконечность с записываемой мантиссой, у которой первый бит выставлен в единицу.

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

   На этом все, удачи вам и спасибо что прочитали мою статью. Буду рад оставленным комментариям и новым постоянным читателям.

Александр Кобелев.