无符号长长的MOD操作

我需要执行由16位模数找到师unsigned long long数的余的很多操作：无符号长长的MOD操作

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），但是这个循环非常频繁地执行，所以它的速度非常关键。

来源

2014-02-27 Konstantin Isupov

我不认为你可以在这里做很多。也许用汇编语言编写它可能会有所帮助。但无论如何，100并不是“很多”。 –

一种选择是使用pthreads并行执行多个模数运算。 –

如果您的模块值范围是连续的，那么您可以只有一个变量来存储它，然后在循环中减少该变量。例如，如果你的值在（高，低）范围内，那么'for（i = low，{i <= high，i ++）;残余物[I-低] = largeNumber％I; }' – brokenfoot

可以通过乘以一个常数（其中只有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）可能用倒数乘法计算。

来源

2014-02-27 10:13:11

如果速度是至关重要的，根据本answer about branch prediction和this one，循环展开可能会有所帮助，避免了指令诱导由试验，减少了试验的次数并改善“分支预测”。

增益（或者没有，一些编译器会为你做这种优化）因体系结构/编译器而异。

在我的机器，改变环路，同时与gcc -O2增益保持操作的数量从

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]; }

是〜15％。（500000000而不是100观察更显着的时间差异）

来源

2014-02-27 10:50:21

我怀疑'我

无符号长长的MOD操作

回答

相关问题