c中的模数优化

Question

我正在尝试对我提前知道的整数集进行模运算优化分红为400-3500，分红为正整数，最大为2^16

我听说过 hacker's delight 的幻数，但我找不到获取一般数模数的幻数的方法。

如果不是幻数，我可以根据我掌握的数字信息进行优化吗？

Answer 1

你提到 Hackers 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). 
}

通过y获得数字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 位整数。

Answer 2

推荐以下内容，因为可以传递给编译器的唯一有用的东西是操作数在有限的 16 位范围内的知识。否则让编译器优化。

#include <stdint.h>
inline uint_fast16_t fast_mod(uint_fast16_t dividend, uint_fast16_t divisor) {
  return dividend % divisor;
}

Answer 3

n = ((n + magic[y].a) * magic[y].M) >> (32 + magic[y].s);

当添加指示符为 1 时，这不起作用。根据 Hacker's Delight（第 10-10 节），配额（此处表示为 q）计算如下：

q = floor(M*n/2^32)
q = q >> s

如果a = 0，并且

q = floor(M*n/2^32)
t = (q+n)>>1    // (q+n)/2
q = t >> (s-1)

if a = 1。这可以写成：

q = ((M*n)>>32 + a*n) >> s

或者，按照哈罗德的符号：

n = (((n * magic[y].M) >> 32) + n * magic[y].a) >> magic[y].s;

c中的模数优化

modulus optimization in c

c

optimization

modulus