Недавно мне понадобилось сэмулировать работу с плавающей точкой только при помощи целочисленной арифметики, поскольку флоаты были недоступны. Полез я было в интернет за готовой библиотекой, и чуть не утонул. Мало того, что я не нашёл того, что искал, это бог с ним. Я обнаружил, что в интернете кто-то неправ. :)

Оказалось, что форумы кишат людьми, которые не до конца понимают, как компьютеры манипулируют числами. Например, мемасик с КПДВ я стянул с реддита (перечеркнул его я). Кто-то настолько был напуган страшными ошибками округления чисел с плавающей точкой, что даже смешную картинку смастерил. Только вот проблема в том, что 0.5 + 0.5 в точности равно 1.0.

Таким образом, я решил засучить рукава, и изобрести велосипед. То есть, написать самую неоптимизированную C++ библиотеку для эмуляции IEEE754 32-битных чисел с плавающей точкой при помощи исключительно 32-битной целочисленной арифметики. Библиотека уложится в несколько сотен строк кода, и в ней не будет никакого битхакинга. Задача написать понятный код, а не быстрый. А заодно хорошенько его документировать серией статей.

Итак, этим полукреслом мастер Гамбс начинает новую партию мебели, или статья первая: поговорим о числах и компьютерах.

Зачем изобретать велосипед

Год назад я поставил себе задачу написать за выходные простой, но вполне полноценный компилятор только что придуманного мной си-подобного языка. Написать-то дело несложное (соответствующая серия статей), а вот описать труднее. Для хорошего описания нужны красочные примеры. У меня аллергия на иллюстрации из разряда вычисления чисел Фибоначчи. Ну сколько же можно?! Поскольку мой язык крайне примитивен, то и примеры мне нужны простые, но всё же как можно более эффектные. Всякие рейтрейсинги и демосцена прекрасно подходят. Вот результат работы одного из примеров, написанных на моём языке:

Проблема с ним была в том, что для рейтрейсинга мне нужны были числа с плавающей точкой, а в моём языке никаких других типов, кроме булевских и 32-битных целочисленных просто нет.

В принципе, в интернете много библиотек, из которых можно было бы выдрать необходимые куски, например Berkeley Softfloat. Но проблема в том, что они все рассчитаны на скорость исполнения, и практически все выходят за рамки 32-битных вычислений, а у меня только 32-битные числа :(

Таким образом, я решил написать совсем маленькую С++ библиотеку, которая манипулирует исключительно int32_t, и при этом нацелена на читаемость кода, а не на скорость исполнения. Основная цель - санпросвет. Мне больно видеть, каким количеством мифов и суеверий оброс простейший float32.

Вот часть мифов, с которыми я борюсь:

• «Все десятичные дроби неточно представляются в плавающей запятой»: как 0.5, так и 1.0 могут быть точно представлены в двоичном формате IEEE754. Таким образом, сумма равна точно 1.0.

  

  Действительно, большинство десятичных дробей, таких как 0.1, не предствляются точно с плавающей точкой:

  

  Но при этом:

  

• «Никогда не следует сравнивать плавающие точки с помощью ==»: слишком строго. Как мы только что видели, сравнение чисел с плавающей запятой с помощью == в некоторых случаях вполне допустимо. Настоящее правило: избегайте ==, если значения прошли через сложные вычисления, в которых округление может отличаться.

  Не полагайтесь на то, что алгебраические законы (ассоциативность, дистрибутивность) действуют точно. Как следствие, избегайте использования == для чисел с плавающей запятой, когда результаты получены в результате нетривиальных вычислений.

  

  Но при этом:

  

• «Плавающая запятая является случайной/ненадежной»: арифметика с плавающей запятой является детерминированной и следует строгим правилам IEEE754. Результаты могут быть неожиданными, но не произвольными.

  Стандарт IEEE требует, что все реализации должны давать точные, бит-в-бит результаты для КАЖДОЙ операции, для которой результат может быть представлен, и ближайшее значение для остальных.

Итак, поехали.

Прежде всего, существует три наиболее распространенных семейства чисел, с которыми мы имеем дело: целые, рациональные и вещественные. Компьютеры могут прекрасно манипулировать целыми числами, с некоторым трудом — рациональными, а вещественными — только в мечтах. Большинство вещественных чисел даже невозможно вычислить с помощью какого-либо алгоритма, а те немногие, которые всё же можно вычислить, при хранении в конечной памяти сводятся к приближенным значениям. Давайте разбираться.

Целые числа: естественный язык компьютеров

Компьютеры — это цифровые машины. Внутри аппаратного обеспечения все хранится в двоичном формате: последовательности нулей и единиц, что делает целые числа наиболее естественным выбором.

32-разрядный регистр может содержать ровно различных комбинаций нулей и единиц; обычно их интерпретируют как целые числа от до (без знака) или от до (со знаком). Арифметические операции над целыми числами (сложение, вычитание, умножение, деление) являются точными, если результат укладывается в выбранную разрядность. Поэтому компьютеры превосходны в работе с целыми числами: представление является точным, арифметика надежна, и все значения в диапазоне охвачены.

Рациональные числа: справимся при помощи двух целых

Рациональное число — это отношение двух целых чисел, например или . Компьютеры могут хранить их точно, сохраняя целые числитель и знаменатель. Например, в Python класс fractions.Fraction делает именно это. Арифметические операции выполняются правильно, но знаменатели могут становиться очень большими, что замедляет вычисления. Таким образом, представление рациональных чисел возможно, и при этом точно, но менее эффективно. Компьютеры могут с этим справляться, хотя аппаратное обеспечение для этого не оптимизировано.

Вещественные числа: невозможная мечта

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

Вычислимые вещественные числа: крохотное подмножество

Скажем, что вещественное число вычислимо, если существует алгоритм, который при заданном выдает -ю цифру числа. Примеров множество: мы знаем формулы для вычисления цифр , , и многих других. Остановимся на слове алгоритм. В нашем контексте алгоритм — это текстовое описание (фактически, компьютерная программа), которое говорит нам, как вычислить -ю цифру некоторого числа. Множество текстов (компьютерных программ) счётно: существует только конечное число программ длиной 1 символ, конечное число программ длиной 2 символа и так далее.

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

Ограничения по объему памяти: конечная точность

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

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

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

Приближения и погрешности

Итак, мы хотим манипулировать вещественными числами на компьютере, но имеем только конечное количество битовых комбинаций. Предположим, что мы хотим представить числа от 0 до 16, и у нас есть 7 битов. Это дает нам бюджет в различных чисел.

Числа с фиксированной запятой

Если — это значение без знака целого числа с 7-битной комбинацией, то варьируется от 0 до 127. Мы можем интерпретировать это как дробное число . Построим график всех 128 таких чисел:

Эти числа равномерно распределены по всему диапазону. Их называют числами с фиксированной запятой, потому что «двоичная запятая» (знаменатель) остается в одном и том же положении для всех значений.

Например, возьмем . Битовый шаблон для — 1111101 (поскольку ). Деление на 8 сдвигает двоичную запятую на три места влево: . Двоичная запятая фиксирована для всех чисел, отсюда и название.

Ошибки аппроксимации

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

Допустим, мы хотим представить число с помощью наших 7-разрядных чисел с фиксированной запятой. Ближайшим числом, которое у нас есть, является . Следовательно, мы допустили ошибку 0.025.

Часто важно, насколько велика ошибка по сравнению с размером числа. Определим понятие относительной ошибки:

Проиллюстрируем разницу между ними:

• Если и , то абсолютная погрешность = 0.1, но относительная погрешность = 0,1 / 1000 = 0,0001 (очень мала, хорошо).

• Если и , то абсолютная погрешность очень мала (0.0001), но относительная погрешность = 0.0001 / 0.01 = 0.01. Это погрешность в 1%, что не очень хорошо.

При представлении вещественных чисел на компьютере возникают две естественные задачи:

• Охватить огромный динамический диапазон: от крошечных чисел, таких как , до огромных чисел, таких как .

• Обеспечить приемлемую точность во всех случаях: числа должны быть относительно близки к истинным вещественным числам.

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

Решением является использование логарифмического распределения представляемых чисел:

Здесь числа равномерно распределены по логарифмической шкале:

Это означает, что между 0,1 и 1 столько же чисел, сколько между 1 и 10. Таким образом, мы достигаем равномерной относительной точности, а не равномерной абсолютной точности. Это соответствует реальным потребностям, где значимые цифры имеют большее значение, чем абсолютное расстояние между ними.

Чем больше доступных битов, тем больший диапазон мы можем охватить. Например, числа IEEE с одинарной точностью могут достигать примерно .

Если мы снова возьмем , то можем определить числа как в диапазоне , как показано на «идеальных» графиках выше.

Это распределение было бы идеальным, если бы нашей единственной целью было приближение действительных чисел с равномерной относительной погрешностью. К сожалению, оно создает проблемы.

Например, предположим, что мы хотим сложить два таких числа. Имея и , представляющие и , нам нужно решить уравнение для :

Это сложное уравнение, особенно из-за дробных показателей. Даже простое сложение двух чисел убивает всю эффективность вычислений.

Кроме того, чистое логарифмическое кодирование не может точно представлять целые числа, за исключением степеней двойки. Форматы с плавающей запятой исправляют эту ситуацию: они точно сохраняют все целые числа до определенного размера (например, все целые числа до помещаются в float32). Это свойство имеет важное значение во многих алгоритмах (индексирование массивов, счетчики циклов, геометрия).

Числа с плавающей запятой

Идея плавающей запятой заключается в имитации логарифмического распределения при сохранении эффективности арифметических вычислений. Хороший способ понять числа с плавающей запятой — сконструировать их самим шаг за шагом.

В нашем примере у нас есть бюджет из 7 бит для представления числа. Мы будем использовать их для хранения двух целых чисел: (экспонента) и (мантисса). Мы сами решаем, сколько бит зарезервировать для , поэтому давайте предположим, что мы используем бит для экспоненты и бит для мантиссы.

Если мы интерпретируем битов как целое число со знаком, то в соответствии с наиболее распространенной интерпретацией в виде дополненительго когда, . Если , то может принимать значений от -4 до 3. Построим график всех 8 значений и дополнительно еще одного значения (пунктирная линия):

Вот небольшой кусочек кода на питоне, при помощи которого я отрисовал этот график:

n_e = 3
anchors = []
for e in range(-2**(n_e-1), 2**(n_e-1)+1):
    anchors.append(2**e)

Эти опорные точки делят диапазон на интервалы. При значение может принимать значений. Внутри каждого интервала мы равномерно распределяем 16 чисел. Таким образом, мы получаем чисел, которые точно помещаются в 7 битах.

Вот небольшой фрагмент кода на Python, который генерирует все 128 чисел:

n_m = 7 - n_e
numbers = []
for i in range(len(anchors)-1): # for each interval
    for m in range(2**n_m):     # populate it with 2**n_m numbers
        v = anchors[i] + m/2**n_m * (anchors[i+1]-anchors[i])
        numbers.append(v)

А вот соответствующий график чисел:

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

Остается одна проблема: самая первая опорная точка это , поэтому нуль отсутствует. Обычно эту проблему решают хаком: переопределяют первую опорную точку как ноль.

anchors = [ 0 ]
for e in range(-2**(n_e-1)+1, 2**(n_e-1)+1):
    anchors.append(2**e)

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

Вот наши 128 чисел с плавающей запятой:

Поскольку опорные точки являются степенями двойки, целые числа могут быть представлены точно. Что касается арифметической эффективности, то это и есть основная тема данного учебника: как манипулировать числами с плавающей запятой, используя только целочисленные операции.

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

Оставайтесь на связи!