Умножение Монтгомери на P C с модулями размера слова. Стоит ли оно того?

Question

Я пишу некоторый код C для исследовательского проекта в теории чисел, который требует выполнения множества операций в модульной арифметике c со многими различными модулями. Проще говоря: мне нужно многократно выполнять операцию (a * b) % n.

Код предназначен для запуска на P C с 64-битными словами, и все модули, как известно, меньше чем 2 ^ 64, поэтому все операнды реализуются с помощью 64-разрядных целых чисел без знака.

Мой вопрос: будет ли использование модульного умножения Монтгомери (которое использует только сложение и умножение) вместо оператора C по модулю % (что переводится как a % n = a - n*(a / n) и использует также деление) приводит к более быстрому выполнению?

Интуитивно, я бы сказал, что ответ: Нет, потому что (размер слова) деления на P C не слишком сложны в вычислительном отношении, чем умножения (размер слова), и сокращение Монтгомери на самом деле может привести к накладным расходам.

Спасибо за любые предложения.

Обновление: С одной стороны, согласно Полу Огилву ie (см. Его комментарий ниже), (a * b) % n требует 1 умножения и 1 деления. С другой стороны, умножение Монтгомери требует (игнорируя операции, необходимые для преобразования и обратного преобразования операндов в их представления Монтгомери, поскольку они выполняются один раз только для каждого по модулю n; двоичные сдвиги) 3 умножения. Поэтому может показаться, что Монтгомери быстрее, чем ``% '', как только умножение выполняется в два раза быстрее, чем деление ...

Answer 1

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

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

Однако лучший ответ вы получите, когда реализуете обе версии своего кода и тестируете его.

Answer 2

известно, что все модули меньше 2 ^ 64, поэтому все операнды реализуются 64-разрядными целыми числами без знака.

Однако a * b - это 128-битное, что усложняет история. div требует 128-битного дивиденда и a * b / n < n, поэтому он не может переполнить деление (что подразумевает вход за пределы диапазона), поэтому записать в сборке x64 тривиально:

; compute (A * B) % N
; A: rax
; B: rdx
; N: rcx
; result: rdx
mul rdx
div rcx

И в C вышесказанное невозможно написать, за исключением некоторых специальных вещей, таких как __uint128_t или _mul128 и _div128. Как бы вы ни отображали этот код, эта форма div является самой медленной из возможных форм , ищите «: DIV r64 128 / 64b (full)», например, Дамп синхронизации инструкций Haswell . Почти сто циклов, на процессорах до IceLake это в основном хуже, чем все остальное, что вы можете сделать, за исключением самостоятельного внедрения побитового разделения. Ледяное озеро отличается и, наконец, имеет приличное целочисленное деление, в 18 циклах (добавьте +4 для начального mul для общего модуля) это все еще не быстрое , но по крайней мере это не так на порядок выше нормы и, возможно, стоит задуматься (включая покупку нового оборудования), потому что:

с множеством различных модулей

Это может сломать все, в зависимости от того, как много есть много Умножение Монтгомери требует нахождения некоторого забавного модульного обратного, по модулю степени два, чтобы вы могли по крайней мере использовать подъем Хензеля вместо расширенного евклидова, но это все еще стоит дюжину умножений плюс некоторые дополнительные вещи, все последовательные. Точно так же, уменьшение Барретта требует нахождения некоторой забавной обратной аппроксимации с фиксированной точкой, которая является причудливым способом сказать, что требуется предварительное деление. При слишком большом количестве различных модулей уловки бесполезны.