Степень дроби: длина, нули и значащий хвост

Посмотрим, что происходит с записью при возведении дроби в степень. Пусть

x = M/b^k,   0 < M < b^k.

Тогда

x^N = M^N / b^kN.

Это гарантирует точную запись в поле из kN позиций. Однако кратчайшая запись может оказаться короче — всё зависит от того, на какую степень b делится M^N.

Пример: ноль справа можно удалить

Вычислим четвёртую степень числа 0,6₈:

(0,6₈)⁴ = 6⁴ / 8⁴ = 1296 / 4096 = 0,2420₈ = 0,242₈.

Поле содержит 4 позиции, а кратчайшая запись — всего 3. Лишний ноль возник потому, что 6⁴ делится на 8, но не на 8²: один множитель основания ушёл в целую часть, а значащие цифры это не затронуло.

Проверь себя

Сколько нулей в конце записи

Теперь научимся заранее предсказывать, сколько нулей появится в конце записи. Обозначим через v_p(M) число множителей простого p в разложении числителя M, где p — простой множитель в разложении основания системы счисления.

Пусть основание раскладывается как

b = ∏ p_i^e_i

Тогда число нулей в конце записи равно

z = min ⌊ (N · v_pi(M)) / e_i ⌋

а длина кратчайшей записи —

\(l = kN − z\)

Почему берётся минимум? Чтобы в конце записи появился ноль, в числителе должен накопиться "полный набор" всех простых множителей основания. Если в основании есть и 2, и 5 (как в десятичной системе), то нули будут появляться только до тех пор, пока не закончится самый дефицитный множитель. Именно он и ограничивает количество нулей.

Пример: Если у нас в числителе много двоек, но всего одна пятерка, мы сможем получить только один ноль, так как "дефицитная" пятерка не даст собрать больше комбинаций "2 · 5".

Частный случай: основание — степень двойки

Для b = 2^e и M = 2^a · q, где q нечётно, формула упрощается: z = ⌊ aN / e ⌋. После удаления z нулей в числителе остаётся

2^{(aN − ez)} · q^N

Остаточная степень двойки определяет последнюю ненулевую цифру.
Пример:
Найти последнюю ненулевую цифру числа (0,A8₁₆)⁷ .
В числители168 = 2³ · 21, отсюда z = 5, а остаточная степень равна 2¹. Поэтому последняя цифра находится по остатку 2¹ · 21⁷ по модулю 16 и равна A.

Проверь себя

Нули сразу после запятой

Разберёмся с другим случаем: когда дробь меньше 1 и у неё есть нули сразу после запятой. Пусть x — число от 0 до 1, а h — позиция, на которой стоит его первая ненулевая цифра. Тогда

b^−h ≤ x < b^−(h−1),

то есть перед первой значащей цифрой стоит ровно h − 1 нулей.

Пример: вычислим четвёртую степень числа 0,3₈:

(0,3₈)⁴ = 81/8⁴ = 0,0121₈,

здесь начальный ноль ровно один.

Число начальных нулей можно найти иначе: вычесть из kN количество цифр целого числа M^N. Удобна и формула через логарифм:

начальных нулей = ⌈−N·log_bx⌉ − 1.

Но если x стоит рядом с точной степенью основания, надёжнее прямое сравнение степеней: округление логарифма может пересечь границу и испортить ответ.

Модуль Fraction

Тип Fraction хранит число как точную обыкновенную дробь и не округляет. Для числа вроде (0,7₁₆)¹³ с огромными степенями это даёт безошибочный ответ, тогда как логарифм с плавающей точкой может промахнуться на единицу, если число близко к границе.

Пример:

from fractions import Fraction
x = Fraction(7**13, 16**13)              # точное значение
n = 0
while x < Fraction(1, 16**(n+1)): n += 1  # ищем нули после запятой
print(n)

Проверь себя