How to multiply by modulo two 32-bit integers faster?

Правка ru1, от dmkz, 2021-10-09 13:57:30

Hello, codeforces!

Everyone knows that operation a * b % mod is not calling div and mod assembler commands. Instead of it only integer multiplication (imul) and bit shift in right (sar) are used:

Link to this example

I remember from comments for one of the editorials on the codeforces that Intel and AMD have a special extended ASM command for it, that can calculate even faster for assumption that a and b are 32-bit integers and mod is constant that is known at compilation time.

Today I can't find this command, this editorial and this comment from red coder with his template where this command is used for modulo multiplication. Maybe someone knows this ASM command and can help with it?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский dmkz 2021-10-13 14:46:07 880 Initial revision for English translation
ru1 Русский dmkz 2021-10-09 13:57:30 880 Первая редакция (опубликовано)