оптимизация модуля в c

Я пытаюсь сделать оптимизацию операции модуля на множестве целых чисел, которые я знаю наперед Делители составляют 400-3500, а дивиденды-положительные целые числа до 2^16

Я слышал о магических числах на восторге хакера, но я не мог найти способ получить магические числа для модуля для общих чисел.

И если не магическими числами, то могу ли я выполнять оптимизацию на основе имеющейся у меня информации о числах?

3 2
optimization modulus

3 ответа:

Вы упоминаете хакеров 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 by y тогда что-то вроде (не проверено, проверьте это) 

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-битные целые числа не будут задействованы.

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

Это не работает, когда индикатор add равен 1. После восторга хакера (раздел 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)

Если a = 1. Это можно записать так: 

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

Или, следуя нотации Гарольда: 

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

Рекомендую следующее, поскольку единственная полезная вещь, которую можно передать компилятору, - это знание того, что операнды находятся в ограниченном 16-битном диапазоне. Остальное пусть оптимизирует компилятор.

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