Мне известен вопрос указанного 32-битного кода, но ответ для 64-битного может быть полезен или интересен другим.
И да, 64b / 32b => 32b деление делает полезный строительный блок для 128b% 64b => 64b. __umoddi3 в libgcc (источник связан ниже) дает представление о том, как это делать, но он реализует только 2N% 2N => 2N поверх деления 2N / N => N, а не 4N% 2N => 2N .
Доступны более широкие библиотеки с высокой точностью, например, https://gmplib.org/manual/Integer-Division.html#Integer-Division.
GNU C на 64-битных машинах предоставляет функции __int128 type и libgcc для максимально эффективного умножения и деления в целевой архитектуре.
x86-64's div r/m64 инструкция делает деление 128b / 64b => 64b (также производит остаток в качестве второго вывода), но не работает, если частное переполнение. Так что вы не можете напрямую использовать его, если A/B > 2^64-1, но вы можете заставить gcc использовать его для себя (или даже встроить тот же код, который использует libgcc).
Компилирует ( проводник компилятора Godbolt ) в одну или две div инструкции (которые происходят внутри вызова функции libgcc ). Если бы существовал более быстрый способ, libgcc, вероятно, использовал бы его вместо этого.
#include <stdint.h>
uint64_t AmodB(unsigned __int128 A, uint64_t B) {
return A % B;
}
Функция __umodti3, которую она вызывает, вычисляет полное 128b / 128b по модулю, но реализация этой функции проверяет особый случай, когда старшая половина делителя равна 0, как вы можете увидеть в источнике libgcc . (libgcc создает версию функции si / di / ti из этого кода в соответствии с целевой архитектурой. udiv_qrnnd - это встроенный макрос asm, который выполняет беззнаковое деление 2N / N => N для целевая архитектура.
Для x86-64 (и других архитектур с инструкцией аппаратного деления), fast-path (когда high_half(A) < B; гарантия div не выйдет из строя) - это всего лишь две неиспользованные ветви , некоторый пух для процессоров, вышедших из строя, и одна инструкция div r64, которая занимает около 50-100 циклов на современном x86 Процессоры, согласно таблицам insn Agner Fog . Некоторая другая работа может выполняться параллельно с div, но целочисленная единица деления не очень конвейерна и div декодирует до большого числа мопов (в отличие от деления FP).
Резервный путь все еще использует только две 64-битные div инструкции для случая, когда B только 64-битная, но A/B не умещается в 64-битной, поэтому A/B напрямую может привести к ошибке.
Обратите внимание, что __umodti3 в libgcc просто вставляет __udivmoddi4 в оболочку, которая возвращает только остаток.
* * 1068
Для повторяющихся по модулю того же B
Возможно, стоит подумать о вычислении мультипликативного обратного с фиксированной точкой для B, если таковой существует. Например, с помощью констант времени компиляции gcc выполняет оптимизацию для типов, меньших 128b.
uint64_t modulo_by_constant64(uint64_t A) { return A % 0x12345678ABULL; }
movabs rdx, -2233785418547900415
mov rax, rdi
mul rdx
mov rax, rdx # wasted instruction, could have kept using RDX.
movabs rdx, 78187493547
shr rax, 36 # division result
imul rax, rdx # multiply and subtract to get the modulo
sub rdi, rax
mov rax, rdi
ret
Инструкция
x86 mul r64 выполняет умножение 64b * 64b => 128b (rdx: rax) и может использоваться как строительный блок для построения умножения 128b * 128b => 256b для реализации того же алгоритма. Поскольку нам нужна только верхняя половина полного результата 256b, это экономит несколько умножений.
Современные процессоры Intel имеют очень высокую производительность mul: задержка 3c, одна на тактовую пропускную способность. Однако точная комбинация требуемых сдвигов и добавлений зависит от константы, поэтому общий случай вычисления мультипликативного обратного значения во время выполнения не столь эффективен каждый раз, когда он используется в качестве JIT-скомпилированной или статически скомпилированной версии (даже на вершине затрат на предварительные вычисления).
ИДК, где будет точка безубыточности. Для JIT-компиляции это будет больше, чем ~ 200 повторного использования, если только вы не кешируете сгенерированный код для часто используемых значений B. Для «нормального» способа это может быть в диапазоне 200 повторных использований, но IDK, как дорого было бы найти модульное мультипликативное обратное для 128-битного / 64-битного деления.
libdivide может сделать это за вас, но только для 32- и 64-битных типов. Тем не менее, это, вероятно, хорошая отправная точка.