• Числа №11. Большие десятичные типы

  Apr 27, 2026 numbers

  Из прошлых заметок ясно, почему Float нельзя использовать для денег: вы не контролируете точность. В этих случаях говорят: используйте классы BigInteger и BigDecimal. Они хранят циклопические числа с гарантией точности. Что это за классы такие и как они устроены?

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

  Условный класс BigInteger устроен именно так: он хранит знак и числовой массив. Каждый его элемент — разряд. При этом разряд очень велик: как правило это integer, то есть около двух миллиардов! За счет этого достигается невероятная емкость. Если в каждом элементе MAX_INT значений, а всего их — тоже MAX_INT, то итоговое число равно

  MAX_INT ^ MAX_INT
  

  , то есть два миллиарда в степени два миллиарда. Наверное, если бы каждый атом был Вселенной, то и тогда итоговое число атомов не превысило бы этой цифры.

  Складываются такие числа поразрядно, в столбик. Берутся нулевые элементы массивов и суммируются как два integer с учетом переполнения. Если оно было, в нулевой разряд идет остаток, а в следующий накидывается единичка. Аналогично устроено вычитание.

  Класс BigDecimal устроен просто: это BigInteger с данными о том, сколько разрядов хранится после десятичной запятой. Как и в случае с Float, при сложении и вычитании число “плавает”, но на этот раз без потери точности. Мы не ограничены 32 битами, в нашем распоряжении вся оперативная память.

  Получается, что условные BigDecimal и BigInteger — это программная эмуляция больших чисел. Операции над ними раскладываются в серию машинных команд, например когда складываются два разряда. Однако таких разрядов много, плюс мы проверяем переполнение вручную. Такие операции очень медленны в сравнении с теми, что выполняются на процессоре. Поэтому к программной эмуляции прибегают только если точность критически важна.

  Postgres предлагает тип numeric — высокоточное хранилище чисел. Он хранит знак, масштаб и точность — сколько разрядов выделить на число и сколько проходится на дробную часть. Далее идет массив типа short[] — двухбайтовых элементов. Каждый элемент — это разряд от 0 до 9999; их число не ограничено.

  Один элемент хранит 10.000 значений, два элемента — 100.000.000 значений. Три — накиньте еще четыре нуля и так далее. Складываются numeric как описано выше, только переполнение проверяется для порога в 10 тысяч.

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

  Если вы пользуетесь numeric, обязательно указывайте точность. Иначе возможна ситуация, когда в целой части, скажем, 123, а в дробной — километровый хвост. Numeric относится к типам произвольной длины, и если значение не поместиться в 512 байтов (или около того), то будет сброшено в TOAST-хранилище. Проблемы можно избежать, указав точность: sum numeric(15, 2).

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

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

  Apr 27, 2026 numbers

  Предположим, мы объявили переменную 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/

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

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

• Числа №9. 0.1 + 0.2

  Apr 27, 2026 numbers

  Переходим к кульминации. В этой заметке мы рассмотрим, как складываются числа 0.1 и 0.2. Итак…

  Напомню, что десятичное 0.1 в двоичном виде выглядит как бесконечная периодическая дробь:

  0.0(0011) * 2^0
  

  Нормализуем ее: сдвинем точку за первый единичный бит:

  1.1(0011) e^-4
  

  Обрежем дробную часть до 23 бит. Можно сделать это в лоб: выбросить все биты после двадцать третьего (пробел означает границу):

  10011001100110011001100 11001100110011...
  

  Современные компиляторы поступают иначе: они округляют биты, которые не поместились. Если первый отброшенный бит равен 1, он переносится к младшему разряду. Если там тоже единица, они складываются и таким образом передают перенос вперед.

  Это наш случай: видим, что отброшенная часть начинается с 1. Это значит, единица переходит в конец фиксированной части. Она кончается на ноль, к нему прибавляется единица, и получается вот что:

  10011001100110011001101
  

  Это была мантиса. Экспонента равна -4, к ней прибавляется 127, в двоичном виде получается 1111011. В итоге десятичное 0.1 становится следующим массовом:

  0 1111011 10011001100110011001101
  

  Теперь 0.2. Это тоже периодическая дробь вида 0.(0011). Для нормализации ее нужно сдвинуть на три позиции:

  1.1(0011) e^-3
  

  Экспонента: -3 + 127 = 124 = 1111100 в двоичном виде. Разделим мантиссу по границе 23 бит. Видим, что она тоже округляется, потому что первый бит отброшенной части начинается с единицы.

  10011001100110011001100 11001100110011...
  10011001100110011001101
  

  Итого, 0.2 = 0 1111100 10011001100110011001101 в битовом виде. Эти два массива нужно сложить, но есть нюанс.

  Для сложения и вычитания дробных чисел у них должна быть одинаковая экспонента. Сейчас экспоненты разные: -4 и -3. Поэтому одно из чисел денормализуют так, чтобы степени совпадали. Обратите внимание: это второй раз, когда число “плавает”. Первый раз мы двигали разделитель при нормализации, теперь делаем это опять.

  Вопрос: какое число двигать? Если двигать биты влево, есть шанс, что потеряются левые биты, а если вправо – правые. Вспомним, что биты идут по убыванию значения. Самый левый бит оказывает наибольший вклад в число, а самый правый – наименьший. Поэтому если двигать число, то так, чтобы биты ехали вправо. Сдвиг вправо аналогичен делению на два, а значит – степень растет. Из этого вывод: берем то число, у которого степень меньше и подгоняем под ту, что больше.

  В нашем случае это 0.1, потому что степень -4 меньше, чем -3 у 0.2. Поэтому приведем 0.1 к степени -3. Напомню, число 0.1 мы выразили так:

  1.10011001100110011001101 e-4
  

  Сдвиг:

  0.110011001100110011001101 e-3
  

  Отсекаем последний бит (в данном случае он не округляется, а именно отбрасывается, почему — понятно не до конца):

  0.11001100110011001100110  -3
  

  Теперь у обоих числа одинаковая степень:

   0.11001100110011001100110  -3
   1.10011001100110011001101  -3
  

  Складываем их побитово в стобик:

  1   11  11  11  11  11
   0.11001100110011001100110  -3
   1.10011001100110011001101  -3
  10.01100110011001100110011  -3
  

  Получилось 10.01100110011001100110011 e-3. Однако это не окончательный результат – число не нормализовано. Результат операции нужно снова нормализовать, и это уже третий раз, когда число плавает! Сдвинем разделитесь влево и уменьшим степень. Получится вот что:

  1.001100110011001100110011 e-2
  

  Один правый бит не влезает и отсекается:

  1.00110011001100110011001 1 e-2
  

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

  Результат:

  1.00110011001100110011010 e-2
  

  Последний шаг: битовая упаковка. Знак положительный, первый бит ноль. Экспонента -2+127=125 = 01111101 в двоичном виде. Итого:

  0 01111101 00110011001100110011010
  

  Если привести эту штуку к десятичному виду, она даст примерно 0.3 с кучей нулей и четверкой на конце. Но и это — лишь примерное предствавление, о котором мы поговорим в следующей заметке.

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

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

• Числа №8. Битовый формат

  Apr 27, 2026 numbers

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

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

  Еще запись должна быть монотонной: накрутка битов как в целом числе должна монотонно увеличивать вещественное число.

  Давайте запишем несколько нормализованных дробей:

   1.110011101 * 2^3
  -1.010101 * 2^10
   1.001 * 2^6
  -1.11101 * 2^100
  

  Что между ними общего? Все их можно выразить тремя показателями:

  • был ли спереди минус;
  • степень двойки;
  • биты дробной части.

  Возьмем наше любимое число -42.515625. В нормализованном виде оно равно:

  -1.01010100001 * 2^5
  

  Тройка его параметров выглядит так:

  • 1 (впереди минус);
  • 5 (степень);
  • 01010100001 (биты).

  Вопрос: почему не учитывается целая часть? Та самая единица перед разделителем. Ответ – у нормализованной дроби целая часть всегда равна единице, поэтому она не хранится, а подразумевается. Имея тройку (1, 5, 01010100001), получим исходное число:

  -1.01010100001 * 2^5
  

  Далее тройка записывается в 32 бита (4 байта). Старший бит хранит знак, еще восемь бит – степень. На дробную часть остается 23 бита, она называется мантиссой. И напомню – целая часть дроби, равная единице, подразумевается.

  Со степенью есть одна тонкость: она записывается со смещением 127 (половина размерности). Смысл в том, чтобы записать знаковое число как беззнаковое. Это необходимо, чтобы обеспечить монотонное возрастание числа при накрутке битов. Так, к степени 5 будет прибавлено 127 и получится 132. В двоичном виде это 10000100.

  Итак, в битовом виде число -42.515625 равно:

  1 10000100 01010100001000000000000
  

  Пробелы разделяют смысловые части: знак, экспоненту с выравниванием, мантиссу. Битов 32, и они помещаются в 4 байта. Как с ними работать, рассмотрим позже.

  Float определяет особые числа. Прежде всего это ноль, когда все биты нулевые. Особенность нуля в том, что его нельзя нормализовать. Помните, мы двигали разделитель, пока он не окажется за первым единичным битом? С нулем это невозможно – такого бита нет.

  Еще одно интересное число – минус ноль:

  1 00000000 00000000000000000000000
  

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

  Другие интересные случаи:

  • экспонента 11111111, мантисса = 0 -> бесконечность (может быть отрицательной за счет первого бита)
  • экспонента 11111111, мантисса не равна 0 -> NaN
  • экспонента 0000000, мантисса не равна 0 -> субнормальные числа.

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

  Особые числа нельзя получить в лоб: чаще всего для этого возводят специальные флаги процессора, чтобы при NaN не возбуждалось исключение. Ну или у вас JavaScript.

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

• Числа №7. Нормализация

  Apr 27, 2026 numbers

  Возвращаемся к числам. Мы выяснили, что любая десятичная дробь приводится к двоичной чередой делений и умножений на два. Чаще всего вы получите периодическую дробь как в случае с 0.1. Но бывают и удачные варианты: например, число 42.515625 в двоичном представлении дает 101010.100001.

  Легко заметить: проблем не создают те десятичные числа, которые являются половинками, четвертинками, восьмушками и так далее. Объяснение простое: помните таблицу умножения на 2 из прошлой заметки? Мы останавливаемся, когда получаем единицу, вычитаем из нее единицу и получаем ноль. Это значит, что очередное умножение должно вернуть 1. Если размотать алгоритм назад, на предыдущем шаге должно быть 0.5, перед ним — 0.25 и так далее.

  Поэтому 25% — это ок: в двоичном виде 0.25 будет 0.01. А 10% — не ок: 0.1 будет 0.0(0011). Двоичная природа дает о себе знать.

  Хорошо, мы привели десятичную дробь к двоичной, что дальше? Как ее хранить? Наивное решение — выделить группу бит под целую и дробные части отдельно. Например, если float занимает 4 байта, разделим его пополам: по два байта под каждую часть. В два байта умещаются числа от -32,768 до 32,767. Выходит, подобный float сможет хранить числа от -32,768.32768 до 32,767.32767. Не густо, если сравнить с нормальным float.

  Стандарт чисел с плавающей запятой предусматривает другой принцип хранения. Первый шаг на пути к нему — нормализовать двоичную дробь. Возьмем число 42.515625, которое привели к двоичному виду:

  101010.100001
  

  Это же число я могу представить так:

  101010.100001 * 2^0
  

  Оператор “крышка” означает возведение в степень. Два в нулевой степени равно единице, поэтому такое умножение ничего не изменит.

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

  10101.0100001 * 2^(0+1)
  

  Оно ничуть не изменилось: это все то же число, только в другой записи.

  Теперь сделаем обратное: сдвинем разделитель на два разряда вправо. Это равносильно тому, что дважды умножить число на 2. Чтобы компенсировать умножение, вычтем из степени двойки два:

  1010101.00001 * 2^(0+1-2)
  

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

  Так вот: что же значит нормализовать двоичную дробь? Ответ — сдвинуть разделитель так, чтобы он оказался позади первого единичного бита. При этом неважно, в какой части встречается этот бит: целой или дробной. Мы сканируем биты слева направо, находим первый единичный и передвигаем разделитель так, чтобы он был сразу за ним.

  С числом

  101010.100001 * 2^0
  

  нам повезло: оно начинается сразу с единицы (в отличии, скажем, от 0.00001). Потребуется пять сдвигов влево. Это равносильно тому, чтобы поделить число на 2 пять раз. Компенсация степени составит +5. Вот как выглядит нормализованное число:

  1.01010100001 * 2^5
  

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

  Теперь вспомним 0.1 — оно становится 0.0(0011) в двоичной системе. Чтобы разделитель оказался за единицей, нужно четыре сдвига вправо. Это равносильно умножению, поэтому степень уменьшается. Вот что было до:

  0.0(0011) * 2^0
  

  и после:

  1.1(0011) * 2^-4
  

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

  После нормализации следует третий этап — битовая упаковка, который мы рассмотрим в следующей заметке.

• Числа №6. 0.1 в двоичном виде

  Apr 27, 2026 numbers

  В прошлой заметке был подвох. Чтобы привести десятичную дробь к двоичной, я выбрал число 42.515625. Оно подобрано так, чтобы результат был коротким и без периода. Хорошо, а что нас ждет с другими числами? Давайте проверим.

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

  Для 0.1 получается следующая таблица:

  | number | x2  | bit | next |
  |--------|-----|-----|------|
  | 0.1    | 0.2 | 0   | 0.2  |
  | 0.2    | 0.4 | 0   | 0.4  |
  | 0.4    | 0.8 | 0   | 0.8  |
  | 0.8    | 1.6 | 1   | 0.6  |
  | 0.6    | 1.2 | 1   | 0.2  |
  | 0.2    | 0.4 | 0   | 0.4  |
  | 0.4    | 0.8 | 0   | 0.8  |
  | 0.8    | 1.6 | 1   | 0.6  |
  | 0.6    | 1.2 | 1   | 0.2  |
  | 0.2    | 0.4 | 0   | 0.4  |
  | 0.4    | 0.8 | 0   | 0.8  |
  | 0.8    | 1.6 | 1   | 0.6  |
  | 0.6    | 1.2 | 1   | 0.2  |
  
  ...
  
  0.1 = 0.0001100110011...
  0.1 = 0.0(0011)
  

  Очевидно, образовался повтор из 0011. Цикл никогда не закончится: это дробь с периодом. Как ни утруждайся, точно выразить ее в двоичной системе невозможно. Дело не в запасе точности: будь у нас хоть миллион битов, все равно мы потеряем какую-то часть после запятой.

  Таблица для 0.1 весьма интересна. Из нее следует, что числа 0.2, 0.4, 0.6, 0.8 и другие тоже приводят к периодическим дробям. Например, 0.2 – это всего лишь 0.1 * 2, то есть очередной шаг итерации. В двоичной системе 0.2 дает 0.(0011), то есть то же самое, только без первого нуля.

  Теперь ясно, что происходит, когда вы пишете в коде float f = 0.1. Десятичное 0.1 приводится к двоичной дроби, и получается 0.0(0011) Дробь нормализуется, отсекаются лишние биты, и получается 0.00011001100110011001101. Лишние биты могут как отсекаться, так и округлятся в зависимости от компилятора. Именно из-за округления на конце 01, а не 00.

  Поэтому то, что вы видите как 0.1, в двоичном представлении является 0.00011001100110011001101. То же самое происходит с 0.2. Это косвенно дает ответ на вопрос об их сумме. Оба числа лишь приблизительно равны их десятичным литералам. Поэтому сумма тоже равна 0.3 лишь приблизительно.

  Предлагаю подумать: почему при печати числа 0.1 и 0.2 выглядят адекватно, а их сумма – 0.30000000000000004? Ведь мы выяснили, что в двоичном виде оба они – мешанина нулей и единиц. На это я отвечу в одной из следующих заметок.

• Числа №5. Знакомство с float

  Apr 27, 2026 numbers

  Переходим к числам с плавающей запятой, которые для краткости будем называть флотами. Они бывают половинной точности (16 бит), единичной (32, float), двойной (64, double) и больше. Для простоты будем работать с обычным 32-битным флотом.

  Как мы выяснили, компьютер хранит числа в двоичном виде. Сложение и вычитание устроены по школьному принципу “в столбик”, и каждый разряд должен быть двоичным числом. По-другому компьютер не умеет – так устроены сумматоры (логические схемы): они принимают битовые входы по одному на разряд и выдают битовую маску разрядов результата. И еще бит переноса или переполнения.

  Любое число, объявленное в коде, приводится к двоичному виду. Когда вы пишете в программе:

  float f = 42.01
  

  нужно понимать, что 42.01 – это еще не число. Это литерал, который задает число. Литерал может быть другим, например 0.53 или -4.5234e5. Важно, что на этапе лексера он хранится как строка с метаданными, мол, из этой штуки надо извлечь флоат.

  Дробные числа тоже приводятся к двоичному виду. В примере ниже – двоичная дробь:

  1010111.011011
  

  Кого-то она вводит в ступор, но ничего особенного в ней нет. Мы привыкли к десятичным дробям, но аналогично записывается дробь с любым основанием. Например, вот дроби в шестнадцатеричной и восьмеричной системах счисления:

  0xfa523.ac591
  05627.6232
  

  Так что когда вы пишете f = 42.515625, помните – после компиляции никакого числа 42.515625 нет. Оно преобразуется к двоичной дроби. Если точнее, это только первый шаг: после преобразования двоичная дробь нормализуется и помещается в специальный битовый контейнер. Но пока что мы рассмотрим только преобразование.

  Итак, как привести 42.515625 к двоичному виду? С целой частью все просто: делим на два и выписываем остаток, пока не получим ноль. Ниже – таблица для 42:

  expr  rem bit
  42/2  21  0
  21/2  10  1
  10/2   5  0
   5/2   2  1
   2/2   1  0
   1/2   0  1
  
  = (101010)2
  

  Для остатка алгоритм, по сути, тот же самый: умножаем его на два (то есть делим на два в отрицательной степени). Если результат меньше единицы, пишем ноль и продолжаем. Если больше единицы, то пишем единицу, вычитаем ее и продолжаем.

  Вот что получится для 0.515625:

  number    *2       bit   next
  0.515625  1.03125  1     0.03125
  0.03125   0.0625   0     0.0625
  0.0625    0.125    0     0.125
  0.125     0.25     0     0.25
  0.25      0.5      0     0.5
  0.5       1        1     -
  
  = (0.100001)2
  

  Итого – в двоичном виде 42.515625 становится (101010.100001)2. Это все еще не конечный набор битов – впереди несколько других операций. Но уже на этом шаге видны некоторые проблемы. Я оставлю их на следующую заметку, а вы в качестве упражнения сделайте вот что: приведите к двоичному виду какие-нибудь числа вроде 1.1, 10.135 и так далее. Алгоритмы у вас есть.

• Числа №4. Натуральные дроби

  Apr 27, 2026 numbers

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

  Натуральная дробь — это отношение двух целых чисел, например 1/2, 1/3, 4/9 и так далее. Их достоинство в том, что иногда из них можно выйти обратно к целым числам. Например, кто-то меняет коров на лошадей по курсу 2/3, то есть за две коровы — три лошади. В случае с флоатами курс был бы 0.666666… или 0.(6) в периоде. Далее нам дают 6 лошадей. Умножаем 6 на 0.66666… и получаем 3.999996 коровы. Округляем до четырех и совершаем обмен. Но если учесть, что:

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

  то погрешность рано или поздно даст о себе знать.

  Если хранить курс обмена в виде натуральной дроби 2/3, то умножение на 6 даст целое число:

  2   6   12
  - * - = -- = 4
  3   1    3
  

  Легко написать класс для работы с натуральными дробями. Это пара целых чисел. Операции над парой повторяют школьную программу. Чтобы сложить две дроби, их проводят к общему знаменателю. Например, чтобы сложить 1/6 и 1/12, мы:

  • приводим 1/6 к знаменателю 12 и получаем 2/12;
  • складываем числители;
  • сокращаем дробь.

  1    1    2    1    3   1
  - + -- = -- + -- = -- = -
  6   12   12   12   12   4
  

  Вычитание — то же самое, только меняется знак. Умножение несложное: перемножаем числители и знаменатели, затем сокращаем результат. Деление аналогично, только вторая дробь переворачивается.

  Для всех этих действий нужны две вещи: наименьшее общее кратное (НОК) и наибольший общий делитель (НОД). Принцип их поиска был найден еще греками.

  В Кложе из коробки идет тип Ratio, который устроен как пара чисел BigInteger. Если я поделю одно целое на другое, и результат дает остаток, то получу дробь:

  (/ 2 3)
  2/3 ;; clоure.lang.Ratio
  

  Умножив дробь на целое, которое сокращает знаменатель, я получу целое:

  (* (/ 2 3) 6)
  4 ;; clоjure.lang.BigInt
  

  Никаких 3.999996 коровы, все честно. Здесь Рич Хикки ничего не придумал, а взял реализацию из Common Lisp, который еще до вашего рождения считал натуральные дроби из коробки.

  Понимаю, что примеры с лошадьми звучат забавно. Но есть область, где натуральные дроби в высшей степени оправданы — недвижимость. Доли собственников хранятся в натуральных дробях, например у Васи — 1/2, у Пети — 1/3, у Маши — 1/6. В сумме они дают единицу. Предположим, Вася поделил свою долю 1/2 между Колей и Жорой: каждый получил по 1/4 от общей площади. Сумма долей по-прежнему дает единицу.

  В недвижимости бывают и более сложные доли. Скажем, недавно я участвовал в сделке, где моя доля была 49/125. Так получилось в результате наследства, выкупа долей у других собственников и так далее.

  Приступая к делению, подумайте: можно ли выразить его натуральной дробью. Не всегда это возможно, но если все-таки да, вы обезопасите себя от проблем, связанных с флотами. Об этих проблемах мы поговорим в следующих заметках.

• Числа №3. Сложение

  Apr 27, 2026 numbers

  Продолжаем тему чисел, на этот раз – что-то более серьезное. Поговорим, как компьютеры складывают числа. На эту тему написаны хорошие статьи и книги, поэтому в формате заметки изложить тему невозможно. Напишу только то, что считаю наиболее важным.

  Мы, люди, учимся считать в десятичной системе счисления. Если нужно сложить два числа, мы делаем это в столбик. Мы складываем разряды, при этом может случиться переполнение, например 5 + 7 = 12. В текущем разряде останется 2, а старший переедет к следующему, и нужно учесть его при сложении. Покажем это на примере:

     1 1
    23.55
    12.97
    -----
    36.52
  

  Мы складываем по две десятичные цифры за раз: 2 и 3, 4 и 9 и так далее. Компьютер делает то же самое, но в двоичном виде. Он не может сложить 2 и 3 за один машинный такт – это невозможно. Его система счисления доведена до предела: в ней только нули и единицы. Такой подход следует из природы полупроводников и транзисторов: они принимают два сигнала и выдают один. Были машины на троичной логике, но они не получили распространения.

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

  

  Почему “полу”? Потому что если подать 1 и 1, мы должны получить 0 (результат) и 1 (бит переноса). У полусумматора нет переноса, поэтому бит 1 пропадет. Чтобы этого не случилось, из двух полусумматоров делают полный. Он принимает не два, а три входа: два бита (входы) и перенос, который, возможно, образовался при сложении прошлого разряда.

  

  Множество сумматоров объединяют в каскад, и можно складывать многобитные числа: 4-, 8-, 16- и 32-битные. Пусть вас не смущают четырехбитные числа: такие архитектуры были в старых калькуляторах. Обратите внимание, что последний флаг переноса никуда не делся: складывая числа, мы должны быть готовы к тому, что последний разряд переполнился, и с этим нужно что-то делать.

  

  Проблему последнего переноса решают так: этот бит подключается к специальному регистру флагов. У процессора есть регистр, где каждый бит означает особое состояние. Один из них определяет, был ли перенос в последнем разряде (carry flag). Есть особая команда семейства jump, которая переходит на нужный адрес, если флаг не ноль. В высокоуровневых языках по этому адресу находится код, который возбуждает исключение.

  

  

  До сих пор я использовал слова “перенос” и “переполнение” вместе, но на самом деле это разные вещи. Перенос (carry) используется для беззнаковых чисел, а для знаковых мы говорим о переполнении (overflow). В регистре флагов это два разных бита и две разные команды jump.

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

  Картинки взяты из замечательной книги “Код: тайный язык информатики”. Горячо рекомендую ее к прочтению.

• Числа №2. Арабские числа

  Apr 27, 2026 numbers

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

  Вы, конечно, скажете: Иван, ты несешь ахинею. Арабские числа читаются слева направо, например 12.423 читается как двенадцать тысяч четыреста двадцать три. Но чтобы прочитать тысячи, сотни и так далее, сперва нужно распрасить их. Встретив число, сперва мы переходим в конец и шагаем по три цифры, чтобы определить сотни, тысячи, миллионы и так далее. Только потом, распарсив, мы читаем число.

  На коротких числах это незаметно, и уж тем более, если кто-то расставил разделители: точки, полупробелы. Но попробуйте прочесть это число:

  5512346134
  

  У вас не получится. Сначала вы мысленно добавите разделители:

  5 512 346 134
  

  и таким образом поймете, что первая 5 – это миллиарды. Только теперь число можно прочесть.

  Я уж не говорю о том, что нельзя прочитать число, если его конец неизвестен.

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

  Пример: составим фразу “У меня 125 овец”. Сильно упрощая, на арабском она выглядела бы так:

  .цево 125 янем У
  

  Когда носитель арабского читает эту фразу, он воспринимает цифру 125 как пять единиц, два десятка и одна сотня.

  При этом число записано одинаково: в обоих случаях это 125. Однако его чтение отличается: арабы начинают с младшего порядка и идут по нарастанию. Западный человек читает от старшего ко младшему, при этом он либо распознает порядки, если число короткое, либо мысленно вставляет их.

  Если бы мы изменили порядок арабских чисел в соответствии с направлением письма, получилось бы так: “У меня 521 овец”: пять единиц, два десятка и одна сотня. Это удобно для длинных чисел. Мы уже выяснили, что число 5512346134 нельзя прочитать, пока не расставишь разделители. Но если бы оно было записано задом наперед:

  4316432155
  

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

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

Страница 1 из 110 →