無符號長長的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操作

回答

相關問題