数学背后的gcc9 +模数优化

Question

背景

当我偶然发现gcc trunk中的一个新优化(将是版本9.x)时,我正在使用c中的素数进行操作,该优化将模数比较优化为0整数乘法并使用幻数进行比较.换句话说x%prime==0就变成了x*Magic_mul<=Magic_cmp

_Bool mod(unsigned x){return x % Constant == 0;}

mod:
  imul edi, edi, Magic_mul
  cmp edi, Magic_cmp
  setbe al

细节

基于看到asm输出,它对所有整数进行了这些优化(好吧,至少是素数)我将它们转换为十六进制以帮助查看模式,但目前还不是很明显.

//32bit examples for _Bool mod_n(unsigned x){return x%n==0;};
//note: parameter is unsigned but it becomes a signed multiply
x%3==0;  // x*0xAAAAAAAB <= 0x55555555
x%5==0;  // x*0xCCCCCCCD <= 0x33333333
x%7==0;  // x*0xB6DB6DB7 <= 0x24924924
x%11==0; // x*0xBA2E8BA3 <= 0x1745D174
x%13==0; // x*0xC4EC4EC5 <= 0x13B13B13
x%17==0; // x*0xF0F0F0F1 <= 0x0F0F0F0F
x%19==0; // x*0x286BCA1B <= 0x0D79435E
x%23==0; // x*0xE9BD37A7 <= 0x0B21642C
x%29==0; // x*0x4F72C235 <= 0x08D3DCB0
x%31==0; // x*0xBDEF7BDF <= 0x08421084
x%37==0; // x*0x914C1BAD <= 0x06EB3E45
x%41==0; // x*0xC18F9C19 <= 0x063E7063
x%43==0; // x*0x2FA0BE83 <= 0x05F417D0
x%47==0; // x*0x677D46CF <= 0x0572620A
x%53==0; // x*0x8C13521D <= 0x04D4873E
x%59==0; // x*0xA08AD8F3 <= 0x0456C797
x%61==0; // x*0xC10C9715 <= 0x04325C53
x%67==0; // x*0x07A44C6B <= 0x03D22635
x%71==0; // x*0xE327A977 <= 0x039B0AD1
x%73==0; // x*0xC7E3F1F9 <= 0x0381C0E0
x%79==0; // x*0x613716AF <= 0x033D91D2
x%83==0; // x*0x2B2E43DB <= 0x03159721
x%89==0; // x*0xFA3F47E9 <= 0x02E05C0B
x%97==0; // x*0x5F02A3A1 <= 0x02A3A0FD
///...and even up to 64bit
x%4294967291==0; //x*0x70A3D70A33333333 <= 0x100000005

我检查了黑客的喜悦"整数分区的常数",看起来这可能是乘法和右移的余数的特殊情况,但我不确定.有一个关于黑客的喜悦形式计算这些相同的乘数常数,因此,似乎有希望的.我猜测魔术比较常数取代了移位并比较为零,但我无法看到2s补码以及移位是算术还是逻辑.

题

这背后是否有一些数学或者是否使用二进制表示以其他方式确定了数字？

启示

由于这是简单的整数乘法和比较,因此可以使用向量扩展/内在函数大幅加速(或减少内存占用)检查​​素数.如果数学可以扩展到超过64位,它可能会更快地找到大的大数字素数？

Answer 1

以3为例。

\n\n

0xAB * 3 = 0x201，因此，模 0x100，0xAB 为 1 / 3，反之，0xAB * 3 \xe2\x89\xa1 1。

\n\n

任何8位无符号整数n都可以表示为n = 3*k + r，r < 3，k最多为0x55（十进制85，255 / 3的整数部分）。

\n\n

所以我们有选择：

\n\n

\n

1. r = 0 \xe2\x87\x92 n * 0xAB = 3k * 0xAB = k * (3 * 0xAB) \xe2\x89\xa1 k * 1 = k \xe2\x89\xa4 0x55。

\n

2. r = 1 \xe2\x87\x92 n * 0xAB = 3k * 0xAB + 0xAB; 由于 3k * 0xAB 最多为 0x55 (mod 0x100)，因此将其添加到 0xAB 不会溢出，因此 3k * 0xAB + 0xAB \xe2\x89\xa5 0xAB > 0x55。

\n

3. r = 2 \xe2\x87\x92 n * 0xAB = 3k * 0xAB + 0x156 \xe2\x89\xa1 3k * 0xAB + 0x56 \xe2\x89\xa5 0x56 > 0x55 （与 2 相同。）

\n

\n