C语言 加速执行无符号长长模运算的循环的性能

Question

我需要执行许多操作来查找除法unsigned long long数的余数乘以 16 位模数：

unsigned long long largeNumber;
long residues[100];
unsigned long modules[100];
intiModules(modules); //set different 16-bit values
for(int i = 0; i < 100; i++){
     residues[i] = largeNumber % modules[i];
}

如何加速此循环？

迭代次数不大 （32-128），但此循环经常执行，因此其速度至关重要。

Answer 1

如果速度很关键，根据这个关于分支预测的答案和这个答案，循环展开可能会有所帮助，避免由for指令引起的测试，减少测试的数量并改进"分支预测"。

增益（或没有，某些编译器会为您进行优化）因体系结构/编译器而异。

在我的机器上，更改循环，同时保留操作数

for(int i = 0; i < 500000000; i++){
    residues[i % 100] = largeNumber % modules[i % 100];
}

自

for(int i = 0; i < 500000000; i+=5){
    residues[(i+0) % 100] = largeNumber % modules[(i+0) % 100];
    residues[(i+1) % 100] = largeNumber % modules[(i+1) % 100];
    residues[(i+2) % 100] = largeNumber % modules[(i+2) % 100];
    residues[(i+3) % 100] = largeNumber % modules[(i+3) % 100];
    residues[(i+4) % 100] = largeNumber % modules[(i+4) % 100];
}

gcc -O2增益为 ~15%。（500000000 而不是 100 以观察更显著的时间差）

Answer 2

除以

一个常数（其中只有 65536 个）可以通过将倒数乘以后跟/之前进行一些微调来执行。由于此方法在有限的范围内是准确的，因此可以使用一些技术将 64 位操作数减少到更小的值（该值仍与原始值一致）：

// pseudo code -- not c
a = 0x1234567890abcdefULL;
a = 0x1234 << 48 + 0x5678 << 32 + 0x90ab << 16 + 0xcdef;
a % N === ((0x1234 * (2^48 % N) +     // === means 'is congruent'
           (0x5678 * (2^32 % N)) +    // ^ means exponentation
           (0x90ab * (2^16 % N)) + 
           (0xcdef * 1)) % N;

中间值只能用（小）乘法计算

，最后的余数（%N）有可能用倒数乘法计算。