Привет, Хабр!

Операция проверки делимости — одна из самых фундаментальных в информатике и теории чисел. Для обычных чисел, помещающихся в машинное слово, это одна быстрая аппаратная инструкция. Но для очень больших целых чисел (Big Integers), размер которых превышает разрядность регистра процессора, деление и взятие остатка становится ресурсоёмкой многословной процедурой.

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

Основная идея и ценность

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

Основная практическая ценность заключается в эффективности для больших целых чисел (Big Integers) и аппаратно-ориентированных реализаций (FPGA/ASIC), поскольку сложение и сдвиг являются существенно более дешёвыми операциями, чем деление.

Сравнение сложности (для Big Integers)

В чем практическое преимущество?

Несмотря на схожесть асимптотических оценок сложности, преимущество алгоритма кроется в типе используемых операций.

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

• Данный алгоритм заменяет эту дорогую операцию на итераций, каждая из которых состоит только из сложения и побитового сдвига.Это самые быстрые и простые операции с линейной сложностью . *Это обеспечивает радикальное снижение константного фактора времени выполнения, делая алгоритм особенно эффективным для аппаратных платформ (FPGA/ASIC), где блоки сложения и сдвига требуют меньше логических элементов и энергии, чем блоки деления.

Алгоритм: Шаги и Псевдокод

Алгоритм сначала сводит задачу к случаю, когда делитель — нечётный.

1. Предварительная обработка чётного делителя

Если чётно, оно представляется в виде:

Пусть (x) обозначает показатель максимальной степени двойки, делящей (количество младших нулей).
Сначала проверяется, делится ли на : если

то не делится на .
Иначе, производится редукция:

Далее проверяется делимость на нечётное .

2. Основная процедура для нечётного делителя

Входные параметры:

Инициализация:

В цикле выполняются:

1. Нормализация по 2: делится на 2 (сдвиг вправо), пока не станет нечётным:
   /2

2. Шаг итерации (если

   ):

Псевдокод: Итерационный бинарный критерий делимости

function DIVIDES_BY_D(N: integer ≥ 0, d: integer > 0) -> boolean:
    if d == 1:
        return True
    
    // 1. Обработка чётного d
    // Редукция до нечётного делителя
    if (d & 1) == 0:
        k = v2(d)          // v2(x): количество младших нулей (CTZ)
        if v2(N) < k:      // Проверка делимости N на 2^k
            return False
        N = N >> k         // N = N / 2^k
        d = d >> k         // d = d / 2^k (Теперь d нечётно)
        
    // 2. Основная процедура для нечётного d
    X = N                  // Инициализация
    while True:
        // 2.1. Нормализация (Удаление всех факторов 2 из X)
        r = v2(X)          // Подсчёт младших нулей
        if r > 0:
            X = X >> r     // X = X / 2^r
            
        // 2.2. Проверка условий останова
        if X == d:         // Если X = d, возвращаем True
            return True
        if X < d:          // Если X < d, возвращаем False
            return False

        // 2.3. Выполнение шага итерации (X <- X + d)
        X = X + d          // Переход к шагу 2.1.

? Теоретическое обоснование

На каждой итерации алгоритма сохраняется ключевой инвариант:

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

Сложность алгоритма составляет

где — количество машинных слов в числе, а — количество итераций цикла.

Пример работы

Проверим делимость на .

Области применения

• Библиотеки для работы с большими числами (GMP, OpenSSL): Замена многословного деления на многословное сложение и сдвиг.

• Аппаратные реализации (FPGA, ASIC): Идеально для специализированных IP-ядер, так как сложение и сдвиг требуют меньше логических элементов и энергии, чем полноценный блок деления.

*Полный вариант статьи с доказательством доступен по адресу "Итерационный бинарный критерий делимости нечётным делителем".
Дополнительный плюс, что этот процесс поддаётся распараллеливанию. Как вариант можно применять при проверке чисел на простоту.