Вещественные числа используются в программировании наряду с целыми, но возникает вопрос: как они вообще хранятся?
С целыми всё понятно: переводим число в двоичный вид и устанавливаем каждый 0 или 1 в ячейке памяти.
Вещественное число вроде 3.14 в той же самой ячейке памяти может храниться только в виде тех же 1 и 0, и значит по сути это тоже целочисленное представление.
Наивный подход
Давайте, как всегда, попробуем изобрести собственный формат хранения вещественных чисел.
Предположим, у нас есть ячейка памяти размером 32 бита.
Для начала мы можем договориться, что дробная часть числа находится в диапазоне от .0000 до .9999. Тогда дробное число достаточно умножить на 10000 и получить из него целое:
2.0067 * 10000 = 20067
Вот в таком целом виде и будем его хранить. Только надо потом не забыть разделить его обратно на 10000:
20067 / 10000 = 2.0067
Мы сейчас изобрели числа с фиксированной точкой. Их особенность в том, что дробная часть всегда занимает одинаковое количество знаков – в нашем случае 4.
То есть у нас точность ограничена 4-мя знаками. Если этого недостаточно, мы можем увеличить количество знаков до 6 или 8, и умножать тогда придётся на 1000000 или 100000000.
Следующая проблема это максимальное значение числа. В 32 бита можно записать целое положительное число со значением около 4 миллиардов. Но так как дробные мы умножаем на 10000, то максимальное значение дробного получается в 10000 раз меньше – около 400 тысяч. А если увеличивать его точность, то получится и того меньше.
Чуть менее наивный подход
Выделим в ячейке памяти некоторое количество бит под целую часть, и некоторое количество под дробную. Например, 20 бит под целую и 12 бит под дробную.
В целую часть можно поместить число чуть больше миллиона. Конечно, ограничения по размеру никуда не делись. Но посмотрим на дробную.
В 12 битах можно сохранить число до 4095. То есть, дробная часть из 4-х знаков может быть максимум .4095.
Это выглядит странно, ведь с таким количеством знаков дробная часть должна доходить до .9999, но не может дойти.
Значит, полноценно использовать мы можем только 3 знака, до .999.
Тогда получается, что 12 бит используются нерационально. Вместо 12 бит можно взять 10, это позволяет хранить число до 1023, и туда почти ровно влезает 999.
Как тогда использовать все 12 бит?
У нас есть 4096 (0..4095) возможных значений в ячейке хранения, и 10000 (0..9999) возможных значений в дробной части.
Тогда мы можем отобразить множество 0..9999 на множество 0..4095.
Попробуем навскидку: дробная часть равна .1234, делаем отображение в виде пропорции:
4095 * 1234 / 9999 = 505
В дробную часть ячейки памяти записываем 505.
Теперь попробуем восстановить дробную часть обратно, для чего используем обратное отображение:
505 * 9999 / 4095 = 1233
Как видим, мы чуть потеряли точность в младшем разряде, но он хотя бы есть.
Ценой некоторой потери точности мы можем использовать все 12 бит для хранения 4-х разрядов.
Но раз мы делаем отображения, то можем таким же образом хранить в 12 битах и 6 разрядов, например:
4095 * 1234 / 999999 = 5
Обратно:
5 * 999999 / 4095 = 1221
Здесь мы потеряли точность уже в 2-х младших разрядах. Но это не значит, что данная система непригодна. Она всё равно наиболее оптимально использует выделенные биты, и в каких-то точках диапазона будет давать абсолютную точность. Две таких очевидных точки это 0, которая даст 0, и 999999, которая даст 4095, и при обратном преобразовании получим то же самое:
4095 * 999999 / 4095 = 999999
Кроме них, есть и другие. Существует до 4096 точных значений, которые разбросаны по множеству размером в миллион.
Образованный подход
Исходя из идеи, что некие значения отображаются на некие другие значения, мы можем прийти к такой системе:
Возьмём любой целочисленный диапазон, размер которого заранее известен. Например, для 16-битного числа это будет 0..65535.
16-битное целое число хранится в сущности как позиция, или как порядковый номер, внутри этого диапазона. Число равно собственному порядковому номеру. 0 хранится как 0, 1 как 1 и т.д.
Итак: фактически мы храним не число, а позицию числа внутри заранее оговорённого диапазона. Для целых чисел это одно и то же. Всего в диапазоне 0..65535 существует 65536 целочисленных позиций, каждая из которых соответствует числу 0..65535.
Если мы увеличим количество позиций вдвое, то кроме значений 0, 1, 2... сможем также хранить промежуточные 0.5, 1.5, 2.5..., у которых появятся свои позиции.
Если увеличим количество позиций в 10 раз, то сможем хранить промежуточные значения 0.1, 0.2, 0.3, 0.4... 0.9 и т.д.
Чтобы найти позицию числа для сохранения, надо будет просто умножить его на 10:
3.2 * 10 = 32
Постойте, но разве это не то же самое, о чём говорилось в самом начале? Мы просто умножаем число на 10, 100 или 10000 и тем самым превращаем его из дробного в целое.
Да, но сейчас мы смотрим на это под другим углом. Если раньше мы просто превращали число из дробного в целое, то сейчас мы ищем для дробного числа целочисленную позицию внутри диапазона, и она не обязательно будет кратна 10.
Так как мы уже установили ограничение, что числа будут от 0 до 65535, то все 32 бита мы теперь можем отдать на хранение позиции в диапазоне. Соответственно, диапазон 0..65535 логически разбивается на 4294967296 позиций.
Возьмём число 1234.56789 и найдём для него позицию:
1234.56789 * 4294967295 / 65535 = 80909875.8069
И округлим до ближайшей целочисленной: 80909876. Это то, что будет записано в ячейку.
Теперь получим число обратно:
80909876 * 65535 / 4294967295 = 1234.56789295
Как видим, у нас есть до 5 знаков точности.
Вернёмся к проблеме ограниченного диапазона. Сейчас у нас максимальное число равно 65535, этого часто бывает мало. Возьмём другой диапазон, например 20 бит: 0..1048575.
У нас по-прежнему есть 4294967296 позиций внутри этого диапазона, но так как сам диапазон стал больше, то и части, на которые он делится, стали больше. Значит, мы потеряли точность.
1234.56789 * 4294967295 / 1048575 = 5056794.8988 = 5056795
Обратно:
5056795 * 1048575 / 4294967295 = 1234.56791471
Теперь мы получили точность не более 3-х знаков.
Экстраполируя дальше, если мы расширим диапазон до 32-х бит, то потеряем дробные части вообще. Каждая позиция в таком диапазоне будет соответствовать только одному целому числу.
А если...
Правило действует и в обратную сторону. Если при увеличении диапазона мы теряем точность, то при уменьшении диапазона точность должна расти!
Возьмём экстремальный случай. Пусть максимальное число будет 1. Но диапазон 0..1 по-прежнему делится на 4294967296 позиций, и вот что мы получим для числа 0.777777, к примеру:
0.777777 * 4294967295 / 1 = 3340526777.8 = 3340526778
Обратно:
3340526778 * 1 / 4294967295 = 0.77777700004
Точность – 10 знаков.
Мы могли бы получить больше точности при хранении вещественных чисел, если бы для каждого конкретного числа определяли оптимальный диапазон.
Например, число 5.5 находится в диапазоне 0..6, и именно для него можно было бы посчитать позицию.
Но так как диапазон мы зафиксировали заранее, менять его на ходу не получится.
Выход очевиден – фиксировать не надо, вместо этого надо эффективный диапазон хранить вместе с позицией.
Выделим для начала 8 бит на диапазон и 24 бита на позицию.
Теперь, если нам нужно закодировать число 2.72, мы в диапазон запишем 3, а в позицию – соответствующую позицию числа 2.72 именно в этом диапазоне.
Если надо закодировать число 99.99, то в диапазон запишем 100, и т.д.
Для каждого конкретного числа мы можем подобрать оптимальный диапазон.
Так мы изобрели числа c плавающей точкой: количество знаков после запятой (точность) зависит от диапазона, который плавает вместе с числом.
Но остаётся старая проблема: в 8 бит можно записать максимальное число 255, что очень мало. Где наши миллиарды?
Экспоненциальные числа
Смотрите: для числа 6.3 оптимальным диапазоном будет 0..7, но это не обязательно. Мы можем взять и диапазон 0..8 или даже 0..16, всё равно число 6.3 находится внутри него, и разница в точности будет небольшой.
Тогда мы можем логически определить группу диапазонов разного размера, не ограниченных числом 255, и хранить не сам диапазон, а его порядковый номер.
Первый диапазон будет 0..1. Если наше число не попадает в него, берём второй, который в 2 раза больше: 0..2. Если число не попадает и в него, то берём следующий, в 2 раза больше: 0..4.
Теперь вместо самого диапазона мы можем записывать только его порядковый номер, который является степенью двойки.
0: 0..1
1: 0..2
2: 0..4
3: 0..8
4: 0..16
и т.д.
И значит, в 8 бит мы теперь можем записать диапазон вплоть до 2^255, что безумно много.
Отметим, что все диапазоны начинаются с 0, но это можно дополнительно оптимизировать. Ведь если число не попало в диапазон 0..1, то дальше искать его позицию надо не среди 0..2, а среди 1..2. А следующий диапазон должен быть не 0..4, а 2..4. То есть фактический размер диапазона уменьшается в 2 раза и соответственно растёт точность:
0: 0..1
1: 1..2
2: 2..4
3: 4..8
4: 8..16
Как на самом деле
Для представления типа float с плавающей точкой используется именно вышеописанная система с некоторыми нюансами.
32-битное число типа float делится на следующие группы:
- Биты с 0 по 22: мантисса (всего 23 бита)
- Биты с 23 по 30: экспонента (всего 8 бит)
- Бит 31: знак
Про знак мы до сих пор не говорили, и дальше говорить не будем, он просто есть.
Экспонента это тот самый номер диапазона, о котором мы говорили. Единственный нюанс здесь в том, что экспонента может быть отрицательной (для чисел меньше 1), и соответственно хранится в т.н. biased (смещённом) виде: к ней прибавляется 127, чтобы её значение было всегда положительным, это нужно для правильного сравнения вещественных чисел. Но при реальных вычислениях из экспоненты нужно вычитать 127.
Мантисса это позиция внутри диапазона, заданного экспонентой.
Так как реально применяемый формат числа требует дополнительных объяснений (отрицательные экспоненты, бесконечность, NaN, сравнения и др.), давайте пока закруглимся на небольшом упражнении, где рассмотрим только положительную экспоненту.
В данном случае, если она равна 0, то диапазон равен 1..2, если она равна 1, то диапазон равен 2..4, и т.д.
Введём числовой тип, к которому можно обращаться одновременно и как к вещественному, и как к целому:
Присвоим переменной значение 3.1415926 и разберём его на части побитно:
Что получилось: знак игнорируем, экспонента равна 128, а мантисса 4788186.
Так как экспонента смещена, вычитаем из неё 127 и получаем 1. Это соответствует диапазону 2..4, в котором находится наше число 3.1415926.
Так как на мантиссу выделено 23 бита, то всего в диапазоне 2^23, или 8388608 позиций. Значение мантиссы равно 4788186-й позиции из 8388608, и мы можем получить значение из диапазона 2..4. Так как номера позиций начинаются с 0, то нормализуем диапазон, чтобы он тоже начинался с 0: 0..2. Его длина равна 2.
Делаем пропорцию: позиция 4788186 относится к максимальному номеру позиции 8388607 так же, как искомое число к длине диапазона.
Искомое число = 2 * 4788186 / 8388607 = 1.141593
Так как число находится в диапазоне 2..4, то прибавляем начало диапазона 2 к целой части:
2 + 1.141593 = 3.141593
Итак, мы вычислили то же число, которое записывали, но с некоторой погрешностью. Эта погрешность возникла уже при записи в вещественной форме. Для проверки мы можем распечатать вещественное значение без каких-либо манипуляций:
printf("%f\n", n.f);
И получим тот же самый результат 3.141593.