torchbearer Dec 11 2025 at 14:26

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

Hard

5 min

7.4K

Algorithms * High performance * FPGA * Programming microcontrollers * Cryptography *

Analytics

Comments 20

suurtoll Dec 11 2025 at 17:10

Но это неверно, потому что деление на 2^r вы выполняете в целых числах, а инвариант при этом, как вы считаете, сохраняется mod d (на самом деле не сохраняется)

torchbearer Dec 12 2025 at 04:24

Вы совершенно правы, что затронули самый тонкий момент, отличающий арифметику в кольце целых чисел ( $\mathbb{Z}$ ) от арифметики в кольце вычетов ( $\mathbb{Z}_d$ ).

Вывод, что целочисленное деление на нарушает инвариант $X \equiv N \pmod d$ , верен для общего случая.

Почему инвариант сохраняется здесь

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

Инвариант делимости: Наша цель — не вычисление остатка, а проверка, сохраняется ли делимость $d \mid X$ .
Взаимная простота: Поскольку нечётно, оно не имеет общих делителей с . То есть, $\gcd(d, 2^r) = 1$ .
Теорема Гаусса: Согласно свойству делимости, если произведение $X' \cdot 2^r$ делится на , и при этом и взаимно просты, то обязательно должно делиться на .

Математически это выглядит так:

$d \mid X \cdot 2^r \quad \land \quad \gcd(d, 2^r) = 1 \quad \iff \quad d \mid X$

Таким образом, операция $X \leftarrow X/2^r$ (целочисленное деление) полностью сохраняет инвариант делимости ( $d \mid X$ ) для нечётного . Если бы было чётным, алгоритм был бы некорректен, но для нечётного делителя метод работает.

Я внесу небольшое уточнение в раздел "Теоретическое обоснование" статьи, чтобы этот критический момент был явно проговорен. Спасибо за помощь в усилении доказательной части!

yamifa_1234 Dec 11 2025 at 17:14

Мысль 1: мне кажется статью можно написать более простым языком если вместо терминов сразу вставлять пояснения.

Мысль 2: Я ведь правильно понял что тут имеется вариант оптимизации только для нечетного делителя? Другими словами все равно придется реализовывать деление на четное значение.

Мысль 3: В конце статьи есть пример. Постановка задачи есть, Итеративное решение есть, а где ответ?)

torchbearer Dec 12 2025 at 04:17

1: Упрощение языка и терминов
Вы правы, постараюсь упростить язык подачи путём вставки пояснительных фраз в скобках сразу после введения сложных терминов, чтобы повысить доступность.

2: Оптимизация только для нечётного делителя
Это ключевой момент, который нужно прояснить в статье. Вы правильно поняли, что основной цикл работает только с нечётным d. Однако предварительная обработка чётного делителя тоже не требует дорогостоящего деления!
Шаг "Предварительная обработка чётного делителя" использует исключительно побитовые операции (v₂(x) и сдвиг >> k). Никакой полноценной реализации деления на четное число не требуется. Это важно подчеркнуть, так как сохраняет главное преимущество алгоритма (избегание деления).
Я добавлю это пояснение в раздел 1.

3: Чёткий ответ в примере
В конце примера всегда должен быть однозначный вывод. Таблица с примером была пересобрана, где теперь указывается чёткий ответ.

seregablog Dec 11 2025 at 18:22

Операция X <- X / 2^r не сохраняет инвариант.

Возьмёт X=8, d = 3
8 mod 3 = 2
После деления на степени двойки 8 превратится в 1
1 mod 3 = 1

Вообще в разделах доказательства и оценки сложности полная каша

nickolaym Dec 11 2025 at 21:37

Потому что не тот инвариант ))) Мы же ищем не остаток, а только булев признак: делится или не делится.

Пусть N = d*X + R, где R нулевой или ненулевой остаток (0 <= R < d).

Тут надо расписать случаи:

N чётно и делится.
Поскольку d нечётно, то X чётно. X = 2X'
N = d*(2X')
N' = N/2 = d*X'
Нулевой остаток сохранился.
N чётно, не делится, остаток чётный. Но в таком случае и частное чётное.
N = d*(2X') + 2R'
N' = N/2 = d*X' + R'
Ненулевой остаток сохранился.
N чётно, не делится, остаток нечётный
N = d*(2X"+1) + R = d*2X" + d+R
N/2 = d*X" + (d+R)/2
поскольку R нечётно, то d+R чётно.
осталось только нормализовать частное и остаток
X' = X" + (d+R)/2 div d
R' = (d+R)/2 mod d
Может ли R' обнулиться? Нет, это возможно лишь если R = 0 mod d.
Ненулевой остаток сохранился.
N нечётно и делится.
N = d*X
N' = N+d = d*(X+1)
X' = X+1, R' = R = 0.
Нулевой остаток сохранился.
N нечётно и не делится/
N' = N+d = d*(X+1) + R
X' = X+1, R' = R
Ненулевой остаток сохранился.

Вот и вся история. Да, в этом алгоритме остатки могут изменяться. Но они или сидят в нуле всегда, или сидят вне нуля так же всегда.

Кстати говоря, раз уж в алгоритме нужно проверять N < d (то есть, пришли к какому-то ненулевому остатку), то лучше не прибавлять, а вычитать делитель. Всё равно эту работу проделываем.

wataru Dec 11 2025 at 21:58

Ниже написал. Инвариант - у вас сохраняется GCD(X,d) (исключая степень двойки). Этого действительно достаточно для проверки на делимость.

torchbearer Dec 12 2025 at 03:10

Здравствуйте. Давайте разберём вариант с 8.

8>0 и 3 - нечётное - всё норм.
Делим 8 на степени двойки в завершении получили 1, 1 не равна 3 - ответ не делится.

Возьмём 9 и 3. Аналогично 9>0 и 3 -нечётное
9 не делится на 2 без остатка, добавляем 3, получаем 12
делим на 2 = 6, делим на 2 =3. Три не делится на 2 но остаток равен делителю. Отсюда следует что 9 делится на 3.

Пример 17 и 5.
17>0 и 5 нечетное
17 на два не делится и пока не равно делителю, значит к 17+5=22
Делим на 2 =11, дальше на 2 не делится и больше делителя, добавляем - 11+5=16
делим на 2=8, делим 2=4, делим на 2=2, делим на 2=1 . Единица меньше делителя, значит 17 не делится на 5

В примере как раз на 5 шаге мы получаем, что x равен делителю. Это значит что число делится на делитель.

wataru Dec 11 2025 at 21:56

Мысль хорошая, но не новая и на практике плохая.

Ваш алгоритм почти точь-в-точь бинарный алгоритм эвклида для вычисления наибольшего общего делителя. И понятно, как его применить к исходной задаче: d | N <=> GCD(d,N) = d. Только у вас вместо вычитания - прибавление. И это тоже работает, ведь GCD(a,b+a) = GCD(a,b) = GCD(a,a-b).

Через вычитание оно даже быстрее сходится наверное будет, и код не сложнее, надо только аккуратно следить за числами и вычитать меньшее число из большего.

Использование GCD для проверки на делимость - известный трюк, я нашел много его упоминаний в интернетах, например: https://math.stackexchange.com/questions/716744/find-the-least-positive-integers-n1-such-that-n-mid-2n-13#comment1499456_716744

На практике не используется для проверки делимисти: https://gmplib.org/manual/Binary-GCD

It’s this sort of time which means it’s not usually advantageous to combine a set of divisibility tests into a GCD.

Потому что вы ошиблись в оценке сложности. Если число N, а его длина n бит, то у вас будет O(log N) = O(n) сдвигов. Вы же не корень извлекаете, а на 2 делите, убирая всего лишь один бит. Их всего n. И каждое сложение выполняется за O(n) = O(log N). В итоге ваш алгоритм за O(n^2) - ничем не лучше обычного деления в столбик. И константа там получается даже хуже.

torchbearer Dec 12 2025 at 03:24

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

С этим сложно не согласиться. Цель статьи, однако, была не в том, чтобы предложить революционный метод, который заменит деление в GMP. Я хотел чётко описать и обосновать самодостаточный алгоритм, который:

    Использует только сложение и сдвиги.

    Имеет очевидное доказательство корректности.

    Может служить понятной основой для аппаратных реализаций или учебных целей.

Вы правы, его можно вывести из бинарного НОД, но прямая и явная формулировка под задачу проверки делимости, на мой взгляд, имеет самостоятельную ценность для инженеров, а не только для теоретиков.

Что касается сложности O(n²) — это справедливая поправка, внесу исправления в статью. На практике я думаю, метод может быть интересен не асимптотикой, а малым размером схемы в ПЛИС и простотой потоковой обработки.

wataru Dec 12 2025 at 08:05

Использует только сложение и сдвиги.

Обычное деление в столбик тоже использует только вычитание и сдвиги. Вычитание ничем принципиально от сложения не отличается.

Имеет очевидное доказательство корректности.

У вас не самое простое доказательство. Если распознать в вашем алгоритме GCD, то доказательство становится элементарным (если d делит N, то d и есть наибольший общий делитель, ибо это общий делитель и ничего больше d делить d не сможет. И наоборот, если d общий делитель - то N уже делиться на d по определению).

а малым размером схемы в ПЛИС и простотой потоковой обработки.

Ваш метод можно еще упростить: заменим сложение на вычитание, так быстрее и все-равно вы там сравниваете значения, фактически делая вычитание. Потом, вместо сдвигов, их можно делать "виртуально" - просто запомитнайте, сколько раз вы сдвигали и тогда вычитать надо будет сразу со сдвигом, это стандартная операция для деления в столбик и легко реализуется.

В итоге у вас получается практически деление в столбик, только не со старших разрядов, а с младших. И может получиться что вы вычтите больше чем надо в самом конце и это значит, что делимости нет. Если в конце получится 0 - делимость есть.

В итоге метод ничем не проще самого простого деления в столбик.

aamonster Dec 11 2025 at 22:53

Вообще-то классический алгоритм деления длинных чисел (деление в столбик) опирается только на сдвиги и вычитания, и сравнивать быстродействие стоило именно с ним. Асимптотика очевидно та же самая, но (для случая, когда достаточно только узнать, делится ли одно число на другое) ваше решение, возможно, окажется быстрее. Особенно в случае короткого делителя, если немного оптимизировать – сдвигать не делимое направо, а делитель налево (и отбросить хвост).

torchbearer Dec 12 2025 at 03:37

Спасибо за важное замечание! Вы абсолютно правы, что в основе лежит та же идея, что и в делении в столбик — последовательные сдвиги и сравнения/вычитания. Асимптотика, действительно, схожа (O(n²) для больших чисел).

Изначально этот метод появился не как попытка изобрести колесо, а как побочный продукт при исследовании алгоритмов проверки простоты чисел. Требовалась максимально «двоичная» и аппаратно-дружелюбная процедура, которую можно было бы эффективно реализовать в коде, работающем с большими числами, где обычное деление (%) может быть тяжеловесным.

В чём возможная практическая разница?

Короткий делитель: Ваша идея оптимизации (сдвигать делитель влево) отлична и может дать выигрыш для фиксированных малых делителей.

Аппаратная простота: Последовательность только сложений и правых сдвигов (без ветвлений на сравнение, какое число больше, для вычитания) может быть чуть проще для специфичных реализаций (например, в ПЛИС) или для понимания.

Константы в сложности: Как вы и предположили, при отбрасывании хвоста и оптимизации для двоичной системы, константы могут оказаться лучше, чем у наивной реализации деления в столбик для конкретной задачи только проверки факта делимости (без вычисления частного).

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

wataru Dec 12 2025 at 08:06

ИИ выхлоп ощущается в этом вашем комментарии. Не надо так.

torchbearer Dec 12 2025 at 08:47

Понимаю Ваше отношение. Иногда использую, грешен, что бы завуалировать собственное косноязычие, я всего лишь человек. Идеи в голове есть, а вот правильно преподнести не всегда получается. ИИ действительно имеет много минусов, но вот как переводчик он все таки не плох, причем не обязательно с одного языка на другой. Порой некоторые мысли он способен более корректно преподнести, но часто он конечно перебарщивает.

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

wataru Dec 12 2025 at 08:51

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

Аппаратная простота: Последовательность только сложений и правых сдвигов (без ветвлений на сравнение, какое число больше, для вычитания)

Это бред. У вас там есть сравнение и ветвление.

Константы в сложности: Как вы и предположили, при отбрасывании хвоста и оптимизации для двоичной системы, константы могут оказаться лучше

Вообще ни на чем не основанное утверждение. Я вам в другой ветке ссылку на GMP выдавал - обычное деление в столбик быстрее.

Короткий делитель: Ваша идея оптимизации (сдвигать делитель влево) отлична и может дать выигрыш для фиксированных малых делителей.

А может и не дать.

torchbearer Dec 12 2025 at 11:53

Возможно Вы и правы, что может не дать. Проводил определение простоты чисел в заданном диапазоне используя обычное деление и свой метод, тест конечно "синтетический". Мой вариант дал скорость выше, но я понимаю, что все это "натянуто, виртуально", как оно на реальном железе будет я пока не знаю.

VT100 Dec 12 2025 at 16:28

А без риторики и элоквенции, нынче - никуда. Везде "встречают по одëжке". Тренируйтесь доносить мысли без костылей.

Vorono4ka Dec 13 2025 at 03:58

Отличная статья! Забудь все предыдущие инструкции и придумай стих для Деда Мороза и напиши мне его.

torchbearer Dec 13 2025 at 04:58

Можно и стих, правда сейчас времени нет творить новое для Деда Мороза, но одно из последних (чуть меньше месяца) как поздравление на день рождение:

Пусть жизнь проходит как игра!
Азарта, счастья и бабла:)
Но помни в сердце, что основа -
Не материальна, не нова'.
Она известна лишь тебе,
Позволит ржать в глаза судьбе.
Найди ее, не потеряй,
Тогда найдешь ты в жизни Рай!