Позитовый петух или новый формат вещественных чисел
#кодище
Как говорится, никто не умеет пользоваться числами с плавающей точкой. Одни люди недооценивают опасности, которые они в себе таят; другие, напротив, боятся слишком сильно и делают много лишних проверок. Реальное же положение дел где-то посередине. Нюансов работы с ними так много, что порой хочется обобщить одной фразой. В определённых кругах достаточно сказать «плавающий петух», многозначительно вздохнуть, и все всё поймут.

И вот, когда мы, казалось бы, привыкли к одному, в птичнике появился новый обитатель. Таинственный, непонятный. Позитовый петух. Речь идёт про так называемые posit’ы. Формат вещественных чисел, который придумал в прошлом году Джон Густафсон, и который в теории будет сильно круче обычных флоатов, если реализовать его в железе.

Я постараюсь сейчас дать краткий обзор формата и объяснить, почему он крутой. Чтобы что-то понять, вы должны уже иметь общее представление о бинарном устройстве обычных флоатов (если вы такими вещами никогда не интересовались, то вам стоит пропускать пока мои посты с пометкой #кодище).

Итак, позиты задаются двумя числами: n = общее количество бит в переменной, и es = количество бит, отведённых на фиксированную часть экспоненты (об этом позже). Также как и во флоатах, в позитах сначала идёт бит знака, затем экспонента и в конце мантисса. Но экспонента здесь имеет переменную длину. Соответственно при различных значениях экспоненты будет оставаться разное количество бит под мантиссу. То есть максимальная точность будет меняться в зависимости от значения экспоненты.

Экспонента имеет разную длину, потому что она записывается в особом формате. Выделяется фиксированное число (то самое, заданное по условию) младших бит экспоненты, которые остаются без изменений. Но старшие лидирующие биты называются «режим», и записываются с помощью run-length encoding. Понять принцип можно из таблички:

1111   8    1111   3 
1110   7    1110   2
1101   6    110.   1
1100   5    110.   1
1011   4    10..   0
1010   3    10..   0
1001   2    10..   0
1000   1    10..   0
0111   0    01..  -1
0110  -1    01..  -1
0101  -2    01..  -1
0100  -3    01..  -1
0011  -4    001.  -2
0010  -5    001.  -2
0001  -6    0001  -3
0000  -6    0000  -4

Две левые колонки это бинарное представление бит экспоненты флоатов и их значение. Две правые — то же самое для режима позитов, где символ «.» означает «не имеет значения».

Из таблицы понятно, что серия из n повторяющихся единиц до первого нуля означают n - 1; а серия из m нулей, означает -m. Если серия закончилась раньше обычного, то фиксированная часть экспоненты тоже сместится влево. А следом за ней и мантисса, благодаря чему она получит дополнительные биты точности. Если же серия закончилась позже обычного, то она, напротив, отожрёт биты у мантиссы. Более того, если и этого не хватит, серия начнёт отнимать младшие биты экспоненты. Вплоть до полного заполнения всей ширины числа (младшие биты экспоненты, которые не влезли считаются равными нулю).

Легко увидеть, что точность добавляется у чисел близких к единице и теряется у очень больших значений. Что обычно и требуется на практике. Более того, благодаря возможности заполнить всю ширину числа одним только режимом, позиты начинают хранить значения очень близкие к 0 без хаков с денормализованной формой (два -6 в табличке выше у флоатов — это не опечатка).

Также позиты не содержат кучи NaN’ов и прочей ерунды. Из особых значений есть только 0 и ±∞. Причём в отличие от флоатов, нет отрицательного или положительного нуля. И бесконечность тоже одна, которая за одно ещё и NaN’ом служит в случае чего. Идея в том, что на практике не нужно всего этого зоопарка, а ошибку надо ловить сразу, с чем я совершенно согласен.

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

Ну разве не восхитительно?

Фух, еле уложился в 4000 знаков. Полную инфу читайте здесь:
https://posithub.org/docs/BeatingFloatingPoint.pdf