Итерационный бинарный критерий делимости: Деление без деления. Алгоритм для Big Integers и FPGA / Хабр

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

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

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

Основная идея и практическая ценность

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

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

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

Критически важно понимать: асимптотическая сложность данного алгоритма не является его главным преимуществом. Его сила — в низком константном множителе и аппаратной простоте.
Характеристика Традиционное деление / N % d Итерационный бинарный критерий
Ключевые операции Дорогостоящее многословное деление/умножение Дешёвые многословные сложение и сдвиг
Асимптотика для BigInt или $O(n \log n)$
Тип преимущества – Крайне низкий константный множитель и кардинально меньшая сложность аппаратной реализации

В чём заключается реальное практическое преимущество?

Несмотря на схожую асимптотику с наивным делением в столбик (), преимущество алгоритма кроется в типе используемых операций и их стоимости на уровне процессора или логических схем.
Константный фактор: Даже продвинутые алгоритмы деления (с квазилинейной сложностью $O(n \log n)$ ) имеют большой константный накладной расход из-за внутренней сложности. Наш алгоритм заменяет эту дорогую операцию на последовательность элементарных шагов (сложение+сдвиг), каждый из которых выполняется с ли��ейной сложностью и минимальными накладными расходами. Это даёт радикальное снижение константного множителя времени выполнения.
Аппаратная эффективность: На платформах типа FPGA/ASIC блоки сложения и сдвига требуют на порядки меньше логических элементов и энергии, чем полноценные блоки целочисленного деления. Это делает алгоритм идеальным кандидатом для встраивания в специализированные IP-ядра или криптографические ускорители.

Сравнение с аналогами и контекст

Связь с бинарным НОД: Алгоритм логически эквивалентен бинарному алгоритму Евклида для вычисления $\gcd(N, d)$ , так как условие $d \mid N$ равносильно $\gcd(N, d) = d$ . Однако данная формулировка явно нацелена на проверку делимости и использует только сложение (вместо вычитания), что в некоторых конвейерных аппаратных реализациях может быть проще.

Почему не везде используется? В высокооптимизированных библиотеках (GMP) для разовой проверки делимости прямое вычисление НОД часто оказывается менее эффективным, чем специализированные методы. Ценность данного подхода проявляется в нишевых сценариях: массовая проверка на один делитель, аппаратная реализация, образовательные цели.

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

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

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

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

$d=2k⋅d_{odd}, d_{odd} нечётно$

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

то не делится на .
Иначе, производится редукция:
N′←N≫k,d′←d≫k

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

Вход: $N \ge 0$ , нечётный

. Выход: True, если $d \mid N$ ; False иначе.

Инициализация:
X←N

Цикл:

Нормализация по 2: Делим на 2 (сдвиг вправо), пока оно не станет нечётным.
$X \leftarrow X \gg v_2(X)$

Проверка завершения:

Если , вернуть True.

Если , вернуть False.

Итерация: Если

, выполнить $X \leftarrow X + d$ и перейти к шагу 1.

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

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): count trailing zeros (CTZ)
        if v2(N) < k:
            return False
        N = N >> k         // Убираем множитель 2^k из N
        d = d >> k         // Теперь d гарантированно нечётно
        
    // 2. Основная процедура для нечётного d
    X = N
    while True:
        // 2.1. Нормализация: удаление всех факторов 2
        r = v2(X)
        if r > 0:
            X = X >> r
            
        // 2.2. Проверка условий останова
        if X == d:
            return True
        if X < d:
            return False

        // 2.3. Шаг итерации (X <- X + d)
        X = X + d

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

Инвариант и корректность

Данный алгоритм основан на том же фундаментальном принципе, что и Бинарный алгоритм Евклида (Binary GCD): . Данный метод является его специализированной версией, адаптированной для быстрой проверки делимости ( $d \mid N \iff GCD(d, N)=d$ ).

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

$X \equiv N \pmod d$

Поскольку нечётно, $\gcd(2, d) = 1$ . Операции $X \leftarrow X + d$ и $X \leftarrow X/2^r$ (деление на степень двойки) сохраняют инвариант.

Критический момент (Сохранение делимости при целочисленном делении):

В общем случае целочисленное деление $X \leftarrow X/2^r$ не сохраняет конгруэнцию по произвольному модулю. Однако, поскольку делитель всегда нечётен, он взаимно прост со степенью двойки , то есть $\gcd(d, 2^r) = 1$ .

Следовательно, согласно свойству делимости (теорема Гаусса), операция деления на полностью сохраняет инвариант делимости, который является целью нашего алгоритма:

$d \mid X \cdot 2^r \quad \iff \quad d \mid X$

Это гарантирует, что мы можем безопасно использовать только побитовые сдвиги.

4. Анализ сложности

Количество итераций (циклов while) алгоритма оценивается как $O(\log N)$ , что эквивалентно (где — длина числа в битах).

Общая вычислительная сложность для многословных чисел (Big Integers):

Так как стоимость одной итерации (сложение или сдвиг $X \gg r$ ) для машинных слов составляет , а количество итераций равно , общая сложность алгоритма составляет:

$\text{Сложность} = O(\text{итераций}) \cdot O(\text{стоимость операции}) = O(n) \cdot O(n) = O(n^2)$

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

Конечность: В случае делимости ( $N = d \cdot m$ ), после нормализации получаем $X = d \cdot q$ , где — нечётная часть . Шаг $X \leftarrow X+d$ даёт . Поскольку нечётно, чётно. После нормализации нечётный множитель строго уменьшается, гарантируя завершение. В случае неделимости процесс сойдётся к , равному остатку (), и вернёт False.

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

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

Шаг	X (Нечётное на старте)	Операция: X = X + d (Сложение)	Нормализация: v₂ (Кол-во нулей) и Деление на 2ⁿ	Результат X (Новое нечётное)
0	3519	3519 + 9 = 3528	v₂(3528) = 3, Деление на 8	441
1	441	441 + 9 = 450	v₂(450) = 1, Деление на 2	225
2	225	225 + 9 = 234	v₂(234) = 1, Деление на 2	117
3	117	117 + 9 = 126	v₂(126) = 1, Деление на 2	63
4	63	63 + 9 = 72	v₂(72) = 3, Деление на 8	9
5	9	-	-	9. X=d, Делится

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

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

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

Образовательные цели: Предлагает изящную и простую для реализации альтернативу, наглядно демонстрирующую работу с битовыми представлениями чисел и инвариантами.

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

Итерационный бинарный критерий делимости: Деление без деления. Алгоритм для Big Integers и FPGA