Опубликовано: Thu, 11 Dec 2025 14:26:15 GMT
Канал: Все статьи подряд / Программирование микроконтроллеров / Хабр

Итерационный бинарный критерий делимости: Деление без деления. Алгоритм для Big Integers и FPGA.Деление — одна из самых ресурсоемких операций для Big Integers в криптографии и для аппаратных ускорителей (FPGA/ASIC). Что, если бы можно было проверять делимость, полностью исключив операцию деления и взятия остатка?Представляем новый детерминированный алгоритм, который заменяет дорогой N mod d на O(logN) итераций, состоящих исключительно из сложения (X+d) и побитового сдвига.Разбираем, как этот подход, обладающий линейно-логарифмической сложностью O(n⋅logN), обеспечивает радикальное снижение константного фактора и становится идеальным решением для многословной арифметики и низкоуровневой оптимизации железа. Экспертный уровень. Читать далее]]>

https://habr.com/ru/articles/975814/