Перевод дробей между системами

Учимся переводить дробную часть числа в любую систему счисления и понимаем, почему безобидная 0.1 превращается в бесконечную двоичную дробь.

Дробная часть — это всё, что стоит после запятой; переводится она в другую систему отдельно от целой части, своим собственным алгоритмом — умножением на основание.

В базовых уроках мы переводили целые числа: делили на основание и собирали остатки снизу вверх. Но число $12{,}625$ состоит из двух частей. Целую часть ($12$) переводим делением, как раньше, а дробную ($0{,}625$) — совершенно другим приёмом. Зачем это нужно? Любое вещественное число в памяти компьютера хранится в двоичном виде, и понимание перевода дробей объясняет самую болезненную тему программирования: почему 0.1 + 0.2 не равно ровно 0.3. Без этого фундамента остальные два урока раздела повисли бы в воздухе.

Метод умножения на основание

Алгоритм для дробной части — зеркальное отражение деления для целой. Чтобы перевести дробь в систему с основанием $q$, нужно:

1. Умножить дробь на основание $q$.
2. Записать целую часть результата — это очередная цифра после запятой (записываем сверху вниз).
3. Отбросить целую часть, оставив только дробную, и повторить с ней шаг 1.
4. Остановиться, когда дробная часть станет равна нулю (получили конечную дробь) или когда остатки начнут повторяться (дробь периодическая).

Формально, если дробь записана как $0{,}d_1 d_2 d_3 \ldots$ в системе с основанием $q$, то её значение восстанавливается рядом:

$$0{,}d_1 d_2 d_3 \ldots = \frac{d_1}{q} + \frac{d_2}{q^2} + \frac{d_3}{q^3} + \ldots$$

Метод умножения как раз вытаскивает эти цифры $d_i$ по одной, начиная со старшей.

Разбор: переводим 0,625 в двоичную

Возьмём $0{,}625_{10}$ и основание $q = 2$. Каждую строку умножаем на 2, отделяем целую часть как очередной бит:

Читаем биты сверху вниз: $0{,}625_{10} = 0{,}101_2$. Проверим обратным разложением: $\frac{1}{2} + \frac{0}{4} + \frac{1}{8} = 0{,}5 + 0{,}125 = 0{,}625$. Сходится. Эта дробь оказалась конечной в двоичной системе — потому что $0{,}625 = \frac{5}{8}$, а знаменатель $8 = 2^3$ — степень двойки.

Конечные и периодические дроби

Ключевая идея: будет ли дробь конечной, зависит от системы счисления. Дробь $\frac{p}{q}$ (несократимая) записывается конечной в системе с основанием $b$ тогда и только тогда, когда все простые делители знаменателя $q$ входят в число делителей основания $b$.

• В десятичной системе основание $10 = 2 \cdot 5$. Конечны дроби, у которых знаменатель составлен только из двоек и пятёрок: $\frac{1}{2}, \frac{1}{4}, \frac{1}{5}, \frac{1}{20}$. А вот $\frac{1}{3} = 0{,}333\ldots$ — периодическая.
• В двоичной системе основание $2$. Конечны только дроби со знаменателем — степенью двойки: $\frac{1}{2}, \frac{1}{4}, \frac{1}{8}$. Любой множитель $5$ в знаменателе делает дробь периодической.

Почему 0,1 бесконечна в двоичной

Десятичная $0{,}1 = \frac{1}{10} = \frac{1}{2 \cdot 5}$. В знаменателе сидит пятёрка, которая не делится нацело в системе по основанию 2. Значит, в двоичной записи $0{,}1$ — бесконечная периодическая дробь. Прогоним метод умножения и увидим, как остатки зацикливаются:

На пятом шаге остаток $0{,}2$ совпал с первым — дальше всё повторяется бесконечно. Получаем $0{,}1_{10} = 0{,}0\overline{0011}_2 = 0{,}0001100110011\ldots_2$, где группа $0011$ — период. Запомните этот факт: именно поэтому компьютер не может хранить $0{,}1$ абсолютно точно.

Как это работает

Под капотом метод умножения — это просто способ выделить очередную цифру разложения по степеням основания. Когда мы умножаем дробь на $q$, мы сдвигаем «запятую» на один разряд влево в системе с основанием $q$ (точно как умножение на 10 сдвигает запятую в десятичной). Целая часть, вылезшая за запятую, и есть старшая оставшаяся цифра. Напишем это на Python — он честно умножает и собирает биты:

def to_binary_fraction(x, max_bits=12):
    bits = []
    for _ in range(max_bits):
        x *= 2
        bit = int(x)      # целая часть результата
        bits.append(str(bit))
        x -= bit          # оставляем только дробную часть
        if x == 0:
            break
    return "0." + "".join(bits)

print("0.625 ->", to_binary_fraction(0.625))
print("0.1   ->", to_binary_fraction(0.1))

Вывод:

0.625 -> 0.101
0.1   -> 0.000110011001

Для $0{,}625$ цикл прервался на третьем бите (дробная часть обнулилась) — конечная дробь. Для $0{,}1$ цикл дошёл до лимита в 12 бит и оборвался посередине периода $0011$ — бесконечная дробь, которую пришлось обрезать. Именно это обрезание и порождает крошечную погрешность, о которой пойдёт речь в следующих уроках.

Частые ошибки

• Путают алгоритмы. Целую часть переводят делением (остатки снизу вверх), дробную — умножением (цифры сверху вниз). Перепутать направление чтения цифр — типичная ошибка на экзамене.
• Забывают про разные системы. «Конечная» и «бесконечная» — свойство пары «дробь + система», а не самого числа. $0{,}2$ конечна в десятичной, но бесконечна в двоичной.
• Не замечают зацикливание. Если дробная часть повторилась — дробь периодическая, и умножать дальше бессмысленно: ответ уже найден.
• Теряют ведущие нули. В $0{,}1_{10} = 0{,}0001100\ldots_2$ первые нули после запятой — значимые цифры, отбрасывать их нельзя.

Итоги

• Дробную часть переводят умножением на основание; целые части результатов, прочитанные сверху вниз, — это цифры новой дроби.
• Дробь конечна в системе с основанием $b$, если простые делители её знаменателя делят $b$. В двоичной конечны лишь дроби со знаменателем — степенью двойки.
• $0{,}1_{10} = 0{,}0\overline{0011}_2$ — бесконечная периодическая двоичная дробь из-за множителя 5 в знаменателе.
• Компьютер хранит конечное число бит, поэтому такие дроби округляются — отсюда растут все ошибки точности.