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

[AI]

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

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

становится ресурсоёмкой многословной процедурой.

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

на нечётный делитель

. Его ключевая особенность: он использует исключительно операции сложения (

) и деления на 2 (побитового сдвига вправо,

), что позволяет полностью избежать дорогой операции взятия остатка.

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


Традиционная проверка делимости

сводится к вычислению остатка

. Данный подход итеративно преобразует число

в меньшее число

, сохраняя при этом инвариант делимости:

.

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

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

Характеристика​	Традиционный	Итерационный бинарный критерий​
Ключевые операции​	Деление (дорого)​	Сложение и Сдвиг (дёшево)​
Сложность для Big Int​	O(n²) или O(n log n)​	O( n log n)​
Эффективность​	Низкая для 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.


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


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

Поскольку

нечётно,

. Операции

и

(деление на степень двойки) сохраняют инвариант, так как деление на

является обратимым преобразованием в кольце вычетов

.

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

где

— количество машинных слов в числе, а

— количество итераций цикла.

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


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

на

.

Шаг​	X (Нечётное)​	Итерация: +d​	Нормализация ( )​	Результат X​
0​	3519​
1​	441​
2​	225​
3​	117​
4​	63​
5​	9​	-​	-​	9​

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

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

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