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

Revision ru1, by 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?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English dmkz 2021-10-13 14:46:07 880 Initial revision for English translation
ru1 Russian dmkz 2021-10-09 13:57:30 880 Первая редакция (опубликовано)