Плавающие запятые и ящики

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

Числа первого типа, называемые целыми (integer), отличаются идеальной точностью. Это — либо числа, которые могут представлять исключительно положительные величины (их называют беззнаковыми целыми числами, unsigned integer), либо числа, способные описывать и положительные, и отрицательные величины (целые числа со знаком, signed integer, или просто integer). Размер таких чисел строго ограничен и соответствует размеру регистра процессора, возведённому в степень двойки (в результате в большинстве современных процессоров размер беззнакового целого числа составляет 2^64).

Числа второго типа могут представлять дробные значения, и значения, которые превышают вышеозначенный размер целых чисел. Это достигается ценой (возможной) потери точности. Такие числа называют числами с плавающей запятой (floating point number, их ещё называют числами с плавающей точкой). Они описаны в стандарте IEEE 754.

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

Почему мне этого хотелось? По нескольким причинам. Первая — это важно знать! Это — знание о том, как работает практически любой процессор. Некоторые языки программирования поддерживают только числа с плавающей запятой. Вторая причина — мне хотелось понять то, с чем я обычно работаю. Обе эти причины, правда, не привязаны к какой-то конкретной ситуации или задаче, поэтому они уже долго лежали в моём длинном списке того, с чем мне хотелось когда-нибудь ознакомиться. И последняя причина, конечно, заключается в том, что я работаю над поддержкой иерархии числовых типов (над «числовой башней», numeric tower) для Janet. Это означает, что мне нужна возможность импорта чисел с плавающей запятой без потери точности. Это было отличным оправданием… нет — отличной возможностью реально углубиться в тему плавающих запятых, и именно результатами того, что мне удалось узнать, я и делюсь в этой статье! Если вам надо больше теоретической базы — обязательно раздобудьте стандарт и внимательно его прочитайте. Здесь я уделяю основное внимание тому, что нужно для понимания практической стороны вопроса.

Мне удалось во всём этом разобраться! Цель статьи в том, чтобы помочь с этим разобраться и вам, не принуждая вас к покупке копии стандарта.

Беззнаковые целые числа

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

Вот, например, предположим, что у нас имеется 8-битный процессор (с 1-байтовыми регистрами). Число «ноль» в двоичной системе — это 0, «один» — это 1. А вот «два» — это уже 10, так как мы пользуемся двоичной системой счисления. Двойка, записанная в виде двоичного числа длиной 8 бит, будет выглядеть как 00000010. Здесь мы видим некое представление двоичного числа, такое, когда его цифры, от наиболее значимой, до наименее значимой, представлены 1-битными значениями, каждое из которых закреплено за определённой цифрой числа.

Мы, помещая число «два» в восьмибитный контейнер, выровняли его, поместили цифры 0 левее цифр 10. Используя тот же подход, мы можем представить число «полноценнее», добавив в его запись точку (.) и с другой его стороны заполнив пустые места нулями. Поэтому ещё один способ представления одного и того же числа в виде 8-битного значения (которое больше не является целым беззнаковым числом, так как теперь оно не является побитовым представлением числа) может быть таким: 0010.0000. Перед нами то же число, для представления которого применён другой способ использования битов.

Конечно, решение о том, где именно разместить точку (другими словами — сколько цифр будет слева и справа от точки), принимается произвольно. Это может быть 010.00000, 10.000000, 00010.000, 000010.00, 0000010.0 и, несомненно 00000010. Всё это — корректные способы использования 8 битов для хранения цифр двоичного числа 2. Можно даже сказать, что точка здесь плавает, ведь именно так она себя и ведёт!

Экспоненциальное представление чисел

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

Тут, правда, мы дошли как раз до того места, где я хочу сделать одно предупреждение. Этот материал, на самом деле, не направлен на общее описание представления чисел с плавающей запятой в IEEE 754. Он посвящён семейству чисел с плавающей запятой стандарта IEEE 754, представленных в двоичной форме, а не семейству чисел, основанных на десятичной форме. Десятичная форма гораздо сложнее, и мне это не так интересно. Ну, разве что, я могу рассматривать эту тему в виде, так сказать, фокуса, которым можно поразить друзей на вечеринке (и, как уже было сказано, всё, с чем работают компьютеры, на самом деле, сводится к двоичным числам). А двоичная форма — это именно о том, как всё устроено. Но, после того, как разберёшься с семейством двоичного представления чисел, понимание десятичных чисел — это не так сложно, как можно себе представить. Просто эта тема выходит за рамки того, что я хочу осветить в этой статье.

Вернёмся к предыдущему примеру с числом 2 и на некоторое время вернёмся к десятичному представлению чисел. При использовании экспоненциального представления чисел 1e0 означает 1*10^0, 1e1 означает 1*10^1, 1e-1 означает 1*10^-1 и так далее. Число 2 можно представить как 2e0, 0.2e1, 20e-1 и так далее. Такие вот корректные представления числа можно назвать «когортой» числа.

Как вы скоро увидите, это неприменимо к двоичному представлению чисел. Но эта концепция важна для десятичного представления чисел!

Обратите внимание на то, что происходит с основанием числа (с той частью конструкции, которая находится до e) в одной и той же когорте по мере того, как мы меняем показатель степени. Так, 20e1 эквивалентно 2e2. Перепишем эти выражения: 20.00e1 равно 2.000e2. Меняя показатель степени, мы перемещаем запятую. Именно поэтому вышеописанные выражения и эквивалентны: показатель степени при представлении чисел с плавающей запятой используется для того, чтобы записывать сведения о положении запятой.

Где находится запятая?

Сейчас мы можем начать разговор о формате хранения чисел, хотя мы некоторое время будем это обсуждать в довольно-таки абстрактной форме. Из вышеизложенного мы вынесли знание о том, что число с плавающей запятой состоит из неких чисел и из сведений о расположении запятой (её позиция определяется показателем степени, в которой, в случае с двоичными числами, используется основание 2). Зная об этом, мы можем начать рассуждать о том, где находится запятая.

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

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

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

Представьт себе число с плавающей запятой, равное 5. В двоичном представлении это будет 0…101.0…. Стандартной когортой для этого числа будет 0.101e3. Запятая поставлена так, что вся значащая часть (я буду называть её мантиссой — это то, что находится до e) — это 0, а самая первая цифра после 0 — это 1. Так как мы знаем о том, что это — устоявшаяся традиция — мы, в некоторых случаях, можем «выбросить» из представления числа ещё немного цифр, решив, что эти две цифры (0.1) не являются частью физического представления числа. Это означает, что число с плавающей запятой, равное 5 будет представлен мантиссой 010… и экспонентой 3.

Каково значение экспоненты?

Итак: в предыдущем примере значение экспоненты — это 3. Оно не представлено в виде числа 3. Авторы спецификации хотели упростить сортировку чисел с плавающей запятой (применение стандартной когорты уже в этом сильно помогло!). А это означает, что мы не можем просто использовать для записи отрицательных экспонент дополнительный код. Вместо этого экспонента реализуется в виде смещённого числа, с которым связаны несколько особых соображений, касающихся его формата. Смещение (хотя и косвенно) встроено в специфическое представление числа.

Если описать это в двух словах, то из беззнакового целого числа, которое «появляется» в экспоненте, неявным образом вычитается некое число. Это число и называют смещением (bias).

Все представления чисел с плавающей запятой в IEEE 754 параметризованы (в некоторой степени) с помощью показателя emax, который выражает максимальное значение, которое можно представить с помощью экспоненты. Минимальное значение зафиксировано на уровне, равном 1-emax. Затем мы исключаем особые значения экспоненты (это — «все единицы» и «все нули»). А после этого можно вычислять смещение.

Ну, на самом деле, есть и другой подход к восприятию всего этого, который выглядит ещё проще: наименьшая возможная ненулевая экспонента (то есть — 0…1 при использовании обратного порядка следования байтов) должна представлять минимальное значение экспоненты. Так как минимальное значение экспоненты установлено в значение 1-emax, которое должно быть равно 1-bias, то смещение просто равняется emax.

Тут надо обратить внимание ещё на особые значения экспоненты. «Все единицы» — это ±NaN или ±Inf. «Все нули» используются для представления субнормальных чисел, о которых мы поговорим ниже. Экспонента имеет больший «вес», нежели мантисса, а это означает, что и NaN, и Inf (по абсолютному значению) больше любого представимого конечного числа. Мы остановимся на этом позже, но отмечу, что значения NaN даже больше, чем Inf.

Физическое хранилище

А вот теперь мы наконец можем поговорить о том, как устроен бинарный формат чисел с плавающей запятой стандарта IEEE 754 (технически называемый «бинарный формат обмена данными», «binary interchange format») Сначала идёт знаковый бит. Потом — смещённая экспонента. А дальше — цифры числа. В общем — теперь можно расходиться по домам. А? Вам ещё интересно услышать про субнормальные числа, про значения NaN, да ещё и с примерами? Ну если так — продолжаем.

Субнормальные числа

У того, чтобы специально начинать стандартную когорту с 0.1, есть один недостаток. Он относится к очень-очень маленьким числам. Представим, например, число 0.001*2^emin. Мы, на самом деле, не можем его представить, так как для этого нам понадобилось бы ещё сильнее уменьшить экспоненту. Это приводит к нехорошему побочному эффекту, когда это вот нормальное представление числа «скатывается к 0». Применение субнормальных чисел решает эту проблему благодаря тому, что принимается следующая идея: когда все цифры экспоненты равны нулю, реальное значение экспоненты должно представлять собой emin (то есть — 1-emax). Стандартная когорта начинается с 0.0, а всё остальное остаётся таким же, как было.

Если мантисса тоже полна нулей — то и число будет нулём. Правда, если, следуя ходу наших рассуждений, решить просто интерпретировать эту конструкцию в виде субнормального числа — ошибки не будет: ведь 0.0…0^2^emin даёт всё тот же 0.

Не-числа

Выше вам, на самом деле, досталась порция неправды. Значения NaN в наши дни невероятно важны. Это так из-за приёма, называемого NaN-boxing. Ниже мы поговорим о том, как этот приём работает, а сначала обсудим обычные значения NaN.

Итак — бесконечность (Inf) — это число, описываемое знаковым битом, за которым идёт экспонента, целиком состоящая из единиц, после чего идёт мантисса, состоящая из нулей. Если в мантиссе установлен хотя бы один бит — значение трактуется как NaN (с учётом того, что положительное значение NaN обязательно «больше», чем положительное значение Inf, и это — единственный случай, когда происходит нечто подобное). Именно поэтому Inf больше любого конечного числа, а -Inf меньше любого конечного числа.

Вернёмся к значениям NaN. Если установлен любой из битов мантиссы — это указывает на то, что перед нами — именно NaN. Но имеет значение и то, какой именно бит установлен! В частности — если самый первый бит мантиссы — это 0, то значение считается «сигнальным» (signaling) NaN. Сделано это для того, чтобы можно было преобразовать сигнальное значение NaN в «тихое» (quiet) значение NaN, установив этот бит в 1, но инверсия может быть невозможна.

Почему невозможна? Вспомним, что какой-то бит мантиссы должен быть установлен, иначе число станет бесконечностью. В сигнальном NaN первый бит не установлен, а это значит, что какие-то другие биты уже установлены. А, с другой стороны, в тихом NaN первый бит может быть единственным установленным битом, поэтому его сброс превратит значение в бесконечность, а не в сигнальное значение NaN.

А что это за «сигнальные» и «тихие» значения? Суть в том, что в ходе работы можно, по самым разным причинам, получить NaN. Сигнальное значение NaN предназначено для указания на последствия применения неинициализированной переменной, или для представления каких-то расширений формата. Тихое NaN нужно для представления отладочной информации о недоступных или некорректных данных. В этом смысле «полезная нагрузка» тихого NaN, когда это возможно, сохраняется даже в ходе выполнения неких операций.

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

Точное описание того, как ведёт себя NaN при выполнении различных операций, мы тут опустим, так как…

…на практике этого, на самом деле, не происходит. А происходит, в итоге то, что полезная нагрузка тихих NaN используется для переноса самой разной информации в рантаймах языков программирования! Насколько я понимаю, первым местом, где это появилось, было JavaScriptCore, но в наше время так делается во множестве языков. В этой идее можно найти гораздо больше смысла в том случае, если рассмотреть классическую задачу сборки мусора: как определить, является ли нечто, лежащее в стеке, указателем, или значением? Как представить значение в языке программирования? Именно эту задачу и пытается решить NaN-boxing.

Вот как работает NaN-boxing (на данный момент вам это должно быть понятно, в противном случае попробуйте перечитать статью, так как мы обсудили очень много всего, а для восприятия такого количества информации может понадобиться время!). При применении этого приёма используется полезная нагрузка 64-битных тихих NaN (qNaN) для кодирования типа информации и любых других необходимых данных (обычно эти данные представляют указатель). Посмотрим на то, как это может выглядеть.

Сначала поговорим о параметрах 64-битных чисел с плавающей запятой (что, кроме прочего, позволит нам упомянуть параметры формата обмена данными binary64). Это — один знаковый бит, после которого идёт экспонента с emax, равным 1023 (то есть — 11 бит хранилища) и 53 цифры точности мантиссы (которые представлены в 52 битах) (на самом деле — 52 + 11 +1 = 64). При том, что один из битов мантиссы должен быть 1, чтобы сделать значение тихим NaN, у нас остаётся 51 бит, с которым можно делать то, что нужно.

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

Тут кто-то может задаться вопросом о том, что делаеть, если имеется больше оперативной памяти, чем укладывается в вышеупомянутое значение. Но в реальности большинство современных операционных не подготовлены к тому, чтобы с этим справляться. Именно поэтому такую практику иногда осуждают. Но я тут не для того, чтобы судить. Я всего лишь объясняю то, как всё это работает.

Возвращаясь к формату 64-битных чисел, видим, что можно использовать эти три бита для чего угодно, и при этом иметь возможность закодировать указатель. Эти три бита используются для встраивания в значения информации о типах данных. Для того, чтобы с этим всем было легче работать, при использовании NaN-boxing выполняется беззнаковое сложение для сдвига диапазона, но, с концептуальной точки зрения — это всё!

Потеря точности

Вы, возможно, сейчас уже это поняли, но, всё равно, стоит это объяснить. Мантисса — это, в сущности, «окно» цифр, а экспонента просто указывает на то, где оно находится. Мы всегда, в качестве начала окна, выбираем самый значимый бит. Комбинация этих двух факторов приводит к тому, что если число должно включать в себя (устанавливать) цифры, находящиеся за пределами этого окна, то эти цифры окажутся утерянными. Это — одно из двух мест, являющихся источниками ошибок, имеющих отношение к числам с плавающей запятой. Нельзя представить по-настоящему большое число и по-настоящему маленькое число, так как такое вот маленькое число просто потеряется!

Ещё один вид потери точности связан с форматом представления значений. Так как мы представляем числа в виде последовательностей «цифр», мы отдаёмся на милость используемой системы счисления. Например — подумаем о (десятичном) числе 0.2. В двоичной форме оно выглядит как 0.00110011…, представляя собой бесконечную последовательность цифр. Учитывая то, как функционируют числа с плавающей запятой (а именно — «окно»), мы просто, в некоей позиции, обрезаем число, а это означает потерю точности.

Манипуляции с числами

В заключение мне хотелось бы поговорить о том, как проводить вычисления с плавающей запятой, не теряя (в дополнение к существующим потерям) точности. Тут, на самом деле, не так уж всё и очевидно! Например, для решения моих задач, нужно получить два целых числа (чтобы создавать большие рациональные числа), даже в том случае, если они велики. Как это сделать?

Ну это, к счастью, достаточно просто. Можно просто переместить точку в нестандартное положение, добавить необходимое количество цифр точности к экспоненте. Правда, вместо того, чтобы делать это, придерживаясь функции scalbn, или чего-то подобного, можно просто напрямую извлечь беззнаковое целое и отдельно подстроить экспоненту. Стандарт (что весьма полезно) это учитывает, поэтому, когда мантиссу интерпретируют как беззнаковое целое, используют экспоненту q (а не e). Взаимоотношения между этими двумя значениями выглядят так: e = q + p - 1, где p — это количество цифр в мантиссе (включая скрытую цифру). Чтобы преобразовать это в более удобную форму, выражение можно переписать так: q = e + 1 - p.

Поэтому можно выяснить количество битов в экспоненте, замаскировать их (и знак), а затем манипулировать экспонентой в (большем) целочисленном типе. Это даёт нам удобный беззнаковый тип uint*, способный хранить в два раза больше целых положительных значений, чем соответствующий ему int*. Тип uint, по очевидным причинам, гарантированно поместится в мантиссу числа с плавающей запятой того же битового размера (тип uint64 всегда способен вместить в себя мантиссу типа double). Похожая логика применима к int экспоненты, оставляя предметом беспокойства лишь знак.

Вот, чтобы было понятнее, пример ручного извлечения e, q, мантиссы и знака из числа с плавающей запятой в C. Обратите внимание на то, что этот код не рассчитан на обработку значений NaN, Inf или субнормальных чисел.

#include <float.h> // FLT_MAX_EXP, FLT_MANT_DIG // … float f; uint32_t F = *(uint32_t*)&f; // прямое приведение типов приведёт к новой интерпретации числа  // математические константы с плавающей запятой int32_t femax = FLT_MAX_EXP-1, // по спецификации C     femin = 1 - femax,     fbias = femax,     fp = FLT_MANT_DIG; // включая скрытый бит  // можно взять ещё кое-какие полезные константы для собственного использования int32_t FLT_MANT_BITS = fp - 1,     FLT_EXP_BITS  = 32 - FLT_MANT_BITS - 1; // ещё = - FLT_MANT_DIG // ещё можно вычислить FLT_EXP_BITS на основе битовой ширины  // физическое представление знака, экспоненты и мантиссы uint32_t fS = F >> 31,      fE = (F >> FLT_MANT_BITS) & ((1u << FLT_EXP_BITS)-1),      fM = F & ((1u << FLT_MANT_BITS)-1);  // логические представления того, что было выше int32_t fe = fE - fbias,     fq = fe - fp + 1; uint32_t fm = fM | (1u << (fp - 1)); // установить скрытый бит  printf("%f = %u * 2^%d\n", f, fm, fq);

Эта логика полностью идентична в применении к числам типа double, за исключением следующего:

1. Поменять все места, где есть 32 (например — uint32_t) на 64 (вроде uint64_t).

2. Поменять 31 на 63.

3. Поменять всё, выглядящее как FLT_, на DBL_ (например — DBL_MANT_DIG).

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

Если вам кажутся непонятными фрагменты вроде ((1u << something)-1) — поясню, что это — быстрый способ сгенерировать диапазон маски. Например, представьте себе, что нужна четырёхбитная маска, выглядящая как 0b01111. Самый быстрый способ её сгенерировать —  применить операцию -1 к 0b10000. Получить 0b10000 можно, применив операцию сдвига влево к 1u (оно же — 0b1), выполнив сдвиг на столько битов, сколько должно присутствовать в маске (в нашем случае — 4). Поэтому, когда вы встречаетесь с конструкцией вида ((1u << FOO)-1), вам следует воспринимать её как «последовательность единиц длины FOO». Если нужно, чтобы маска была бы глубже, можно просто потом сдвинуть полученный результат. Этот приём применим во многих ситуациях, но о нём знает не так уж и много программистов!

Итоги

Для того чтобы закрепить то, что вы узнали, вспомним основные моменты:

• Формат обмена числами с плавающей запятой стандарта IEEE 754 (он нас интересует из-за того, что именно его используют процессоры и другие механизмы компьютеров) — это последовательность битов, имеющих следующий смысл:

  • Первый бит — это знаковый бит.

  • Дальше идут биты, представляющие смещённую экспоненту.

  • И наконец — оставшиеся биты — это физическое представление мантиссы.

• Настоящая экспонента — это представление физической экспоненты в виде беззнакового целого числа минус смещение. Смещение — это максимальное представимое значение экспоненты. Самое маленькое представимое значение экспоненты задано как 1 - emax.

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

• Мантисса — это окно из цифр в простом представлении числа (записанном в двоичном виде), где запятая зафиксирована в позиции, находящейся непосредственно до первого установленного бита.

  • Этот бит не входит в физическое представление числа. Он «скрыт» .

  • Если экспонента состоит из одних нулей — значит этот бит не установлен (что делает число субнормальным).

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

• Разница между бесконечностью и значениями NaN заключается в том, что у значений NaN в мантиссе установлен, по меньшей мере, один бит.

• Значения NaN могут быть тихими и сигнальными, что, на практике, выражается весьма незначительными отличиями одних от других:

  • Значение NaN является тихим в том случае, если первый (самый левый) бит мантиссы установлен.

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

Надеюсь, сегодня вы узнали что-нибудь полезное! Мои знания, совершенно точно, пополнились после написания этой статьи. И последняя оговорка: я — не тот человек, который воспринимает информацию через визуальные образы. Поэтому некоторые из моих цифр (даже что-то вроде текстовых представлений чисел, наподобие 0b…) могут оказаться неправильными. Если вы с чем-то таким встретитесь — дайте мне знать, а я постараюсь это исправить. Мне хочется, чтобы эта статья принесла бы пользу как можно большему количеству её читателей.

Увидимся!

О, а приходите к нам работать?

Мы в wunderfund.io занимаемся высокочастотной алготорговлей с 2014 года. Высокочастотная торговля — это непрерывное соревнование лучших программистов и математиков всего мира. Присоединившись к нам, вы станете частью этой увлекательной схватки.

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

Сейчас мы ищем плюсовиков, питонистов, дата-инженеров и мл-рисерчеров.

Присоединяйтесь к нашей команде