модуль оптимизации в с

Question

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

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

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

Answer 1

Вы упоминаете Хакеры Восторг, и у него есть ответ. См. Раздел Целочисленное разделение по константам, включение в компилятор (без знака). Реализуйте это.

Тогда, конечно, не запускайте это каждый раз, когда вы выполняете модуль, это будет намного хуже, чем наивный модуль. Создайте массив результатов, которые вы получите для 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 по 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-битных целых чисел.

Answer 2

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

#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. После хакера 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) 

если a = 1. Это можно записать в виде:

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

или, следуя обозначениям Гарольда:

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