Числа №10. Десятичное представление

Предположим, мы объявили переменную x, равную 0.1:

float x = 0.1

Мы выяснили, что под капотом она становится следующим набором битов:

0 1111011 10011001100110011001101

Однако если мы напечатаем x, число предстанет в понятном виде:

println(x)
# 0.1

Стало быть, некий алгоритм приводит двоичную колбасу к десятичному виду обратно. Какой же?

Наивное решение в том, привести двоичную дробь к десятичной, суммируя степени двойки. Говоря проще, бит N умножается на 2 в степени -N, и все это суммируется, после чего умножается на два в степени экспоненты. Пример на псевдокоде:

sum(for n in [0..p]: get_bit(n) * 2^(-n)) * 2^e

где p – точность (число бит), n – номер текущего бита, e – экспонента. Картинка с формулой:

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

Должен быть алгоритм, который в идеале:

• выполняется за константное время;
• использует только целочисленные операции и битовый сдвиг;
• обратим: если привести строку к float обратно, получим тот же набор битов.

Такие алгоритмы есть, вот некоторые из них: Dragon4, Grisu, Ryū, Giulietti, Dragonbox.

Я немного повозился с Giulietti, потому что именно он используется в большинстве JVM. Если у вас открыта Идея, перейдите в класс java.lang.Float, метод toString. Вы провалитесь в класс FloatToDecimal.java и найдете там реализацию Giulietti. В шапке файла ссылка на академический пейпер с описанием алгоритма.

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

Реализацию на C++ с подробным разбором можно посмотреть в этой статье: https://vitaut.net/posts/2025/smallest-dtoa/

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

Вывод такой: приведение плавающих чисел к десятичным строкам – тоже незаурядная задача.