魔法の乗算 + LUT を使用する場合は、次のコードを使用します。
ランダム除数をテストする単純なテスター i.すべての i を徹底的にテストしたわけではありませんが、実行した短い期間は機能しました。テストした i の被除数 (j=0..2^32-1) のすべての 32 ビット状態で動作するようです。
実際には、i=2..64k-1 またはそのような範囲のルックアップ テーブルを事前計算します (値/0 が定義されていないため i=0 は機能せず、その魔法の乗数がすぐ外側にあるため i=1 は機能しません)。 32 ビット数の範囲)。次に、ルックアップ インデックスとして i を使用する方程式を使用して、魔法の乗数 'm' を取得します。必要に応じて変更し、私のスタイルを嫌いにならないでください。:P
#include <stdio.h>
int main() {
unsigned int i,j,k,m,c;
// compute j/i,
// compute k = 2^32/i
// instead of j/i, use m = ~(j*k)>>32
srand(time(0));
for(c=0;c<64;c++) {
// generate random divisor i's for testing, then fully test every j
i = rand()&0x7fff;
// precompute these and put into a lookup table, index on [i]
k = (((__int64)1)<<32)/i;
for(j=0;j!=-1;j++) {
// status updater so we know it's working...
if(!(j&0xfffff)) { printf("%d : %d \r", i, j); fflush(0); }
// multiply instead of divide!
m = (((__int64)j*k)+k/2)>>32;
// rare fixup
if(j - m*i >= i) m++;
if(m != j/i) {
// as long as this line doesn't print, we're ok
printf("wrong : %d %d %d got: %d should be: %d\n",
i, j, k, m, j/i);
}
}
}
}