c - c中的模量优化

我试着对一组已知的整数进行模运算的优化
除数是400-3500，股息是2^16的正整数
我在hacker's delight上听说了魔法数字，但是我找不到一种方法来得到普通数字的模的魔法数字。
如果不是用神奇的数字，我能根据我掌握的数字信息进行优化吗？

最佳答案

你提到黑客很高兴，它有答案请参阅整型常量除法，合并到编译器中（无符号）实现它。
然后，当然，不要每次做一个模，那会比一个天真的模差得多将你得到的400-3500的结果列成一个数组，然后在计算模数时，从该数组中获取参数。
给出的代码是

struct mu {unsigned M;     // Magic number,
          int a;           // "add" indicator,
          int s;};         // and shift amount.

struct mu magicu(unsigned d) {
                           // Must have 1 <= d <= 2**32-1.
   int p;
   unsigned nc, delta, q1, r1, q2, r2;
   struct mu magu;

   magu.a = 0;             // Initialize "add" indicator.
   nc = -1 - (-d)%d;       // Unsigned arithmetic here.
   p = 31;                 // Init. p.
   q1 = 0x80000000/nc;     // Init. q1 = 2**p/nc.
   r1 = 0x80000000 - q1*nc;// Init. r1 = rem(2**p, nc).
   q2 = 0x7FFFFFFF/d;      // Init. q2 = (2**p - 1)/d.
   r2 = 0x7FFFFFFF - q2*d; // Init. r2 = rem(2**p - 1, d).
   do {
      p = p + 1;
      if (r1 >= nc - r1) {
         q1 = 2*q1 + 1;            // Update q1.
         r1 = 2*r1 - nc;}          // Update r1.
      else {
         q1 = 2*q1;
         r1 = 2*r1;}
      if (r2 + 1 >= d - r2) {
         if (q2 >= 0x7FFFFFFF) magu.a = 1;
         q2 = 2*q2 + 1;            // Update q2.
         r2 = 2*r2 + 1 - d;}       // Update r2.
      else {
         if (q2 >= 0x80000000) magu.a = 1;
         q2 = 2*q2;
         r2 = 2*r2 + 1;}
      delta = d - 1 - r2;
   } while (p < 64 &&
           (q1 < delta || (q1 == delta && r1 == 0)));

   magu.M = q2 + 1;        // Magic number
   magu.s = p - 32;        // and shift amount to return
   return magu;            // (magu.a was set above).
}

然后，通过x得到一个数的模的方法类似于（未测试，检查它）

uint64_t n = x;
// do division
n = ((n + magic[y].a) * magic[y].M) >> (32 + magic[y].s);
// get remainder
return x - y * n;

使用16位幻数可能比这更好，因此不会涉及64位整数。

关于c - c中的模量优化，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/28003334/