c - 计算模 25 的高效（循环）算法？

Question

我有一个代码，我正在计算 x % 25。x 总是取一个正值，但它的动态范围很大。

我发现这个计算 ax % 25 的特定代码段占用了很大的周期。我需要优化它。

由于表的内存可能很大，因此排除了预先计算的查找表。

作为第二种方法，我在下面编写了一个片段（C代码）-

mod(a, b)
{   
    int r = a;  
    while(r >= b)
    {      
        r = r - b;
    }   
    return r;
}

1.) 我怎样才能进一步优化这个代码的周期（把它挤到最大）？

2.）是否有任何完全不同的优化方法来实现 x % 25（我知道这不是一个常见的操作，但仍然在寻找人们可能在他们的经验中使用过的聪明输入，这可能会帮助我。）。

谢谢你。

-广告

编辑：

我认为在 C 中使用本机模运算符 % ，内部使用除法运算（/），这在我正在使用的处理器上成本很高。（没有 div 指令）。因此尝试查看自定义实现是否可以使用 % 运算符击败固有计算。

-广告

score 32 · Accepted Answer

我建议阅读Hacker's Delight。它描述了用于常数除数的非常快的余数算法。他们几乎肯定会击败通用算法。

更新：这里是一些示例代码......它可能可以重新设计以避免临时长长。

unsigned mod25(unsigned n)
{
    unsigned reciprocal = 1374389535; // 2^35 / 25
    unsigned div25 = ((unsigned long long)n * reciprocal) >> 35;
    return n - div25 * 25;
}

score 9 · Accepted Answer

我受到 Pax 的回答的启发，并制作了一个更通用的算法。

int mod(int a, int b) {
    int s = b;
    while (s <= a) {
        s <<= 1;
    }
    int r = a;
    while (r >= b) {
        s >>= 1;
        if (s <= r) {    
            r -= s;
        }
    }
    return r;
}

b这会减去from的两个倍数的幂，a直到找到结果。

编辑：添加if条件以使其正常工作。

例如，如果这是 100 % 7，它首先计算出 7 * 2 * 2 * 2 * 2 = 112。然后它将 112 ( ) 除以 2 并从 100 ( ) (当)s中减去它并不断地做这直到找到模数。所以，rs <= r

s = 112 / 2 = 56, r = 100 - 56 = 44
s = 56 / 2 = 28, r = 44 - 28 = 16
s = 28 / 2 = 14, r = 16 - 14 = 2

因此，100 % 7 = 2

score 9 · Accepted Answer

这是我想出的另一个解决方案：

int mod25(int x){
  /* 25 * (all powers of 2 <= INT_MAX), descending */
  if (x >= 1677721600) x -= 1677721600;
  if (x >=  838860800) x -=  838860800;
  if (x >=  419430400) x -=  419430400;
  if (x >=  209715200) x -=  209715200;
  if (x >=  104857600) x -=  104857600;
  if (x >=   52428800) x -=   52428800;
  if (x >=   26214400) x -=   26214400;
  if (x >=   13107200) x -=   13107200;
  if (x >=    6553600) x -=    6553600;
  if (x >=    3276800) x -=    3276800;
  if (x >=    1638400) x -=    1638400;
  if (x >=     819200) x -=     819200;
  if (x >=     409600) x -=     409600;
  if (x >=     204800) x -=     204800;
  if (x >=     102400) x -=     102400;
  if (x >=      51200) x -=      51200;
  if (x >=      25600) x -=      25600;
  if (x >=      12800) x -=      12800;
  if (x >=       6400) x -=       6400;
  if (x >=       3200) x -=       3200;
  if (x >=       1600) x -=       1600;
  if (x >=        800) x -=        800;
  if (x >=        400) x -=        400;
  if (x >=        200) x -=        200;
  if (x >=        100) x -=        100;
  if (x >=         50) x -=         50;
  if (x >=         25) x -=         25;
  return x;
}

这不使用除法或乘法，仅 27 次比较和最多 27 次减法。

说服自己这有点困难，但它确实有效（至少对于 x 的非负值）。

上面的代码实际上是它的展开版本：

int mod25(int x){
  int divisor;
  for(int divisor = 1677721600; divisor >= 25; divisor >>= 1) {
    if (x >= divisor) x -= divisor;
  }
  return x;
}

通过展开它，我们避免了循环比较以及以更大代码为代价的移位。如果您愿意，您甚至可以使用 Duff 的设备部分展开它，但总共只有 27 次迭代，每次迭代的代码如此之少，我倾向于一直展开它。

它是这样工作的：每个非负整数 x 都可以表示为 (n * 25) + k，其中 n 是非负整数，k 是 0 到 24 之间的整数。 k 也恰好是我们想要的结果，所以如果我们可以计算 x - (n * 25) 我们就会得到答案。不过，我们希望能够在不预先知道 n 的情况下做到这一点。

以二进制形式考虑 n。如果我们可以关闭每个 1 位，我们将得到 0。一种方法是从 2 的大幂开始并向下工作，仅当 n 的当前值大于时减去 2 的每个幂或等于 2 的幂。

由于我们正在处理 (n * 25)，我们实际上需要 2 乘以 25 的降幂。由于 k 严格小于 25，并且我们考虑的最小除数是 25，因此即使在处理 (n * 25) + k。

所以每次比较+减法都会将n的一位归零，最后我们剩下k，即余数。

score 7 · Accepted Answer

由于您希望模数为常数，因此您可以使用倒数乘法来击败它。本文展示了如何以这种方式除以常数，以及如何从中获得余数。

score 7 · Accepted Answer

哦，我的<选择之神>。我无法相信其中一些答案。

首先，重复减法，即使是 Pax 的版本，也永远不会是最优的。考虑以下：

20 % 25

使用重复减法既简单又快速，但是：

65535 % 25

将非常慢，600 多次迭代。这是 16 位数字的平均 300 次迭代。至于32位数字，好吧，甚至不要去那里。

最快的方法是使用长除法。见尼基的回答。

但是，无论如何，这就是编译器将生成的，至少，人们希望它是编译器正在生成的。最好检查一下您是否正在为小众处理器使用编译器。

加快速度的最好方法是首先不做模数。为什么你需要得到模数，你可以重新考虑代码/算法以避免模数，或者至少使模数变得微不足道。

score 7 · Accepted Answer

这是我能想到的最好的：

int mod25(int x)
{
    while((x = (x & 31) + 7 * (x >> 5)) >= 25)
        x -= 25;

    return x;
}

它近似于x % 25。x % 32 + 7 * (x/32)该值将超出的倍数25，这允许递归。

性能似乎足够：x = 2147483647(aka INT_MAX) 的值需要 11 次迭代。

score 5 · Accepted Answer

您的循环的问题在于它是 O(n) - 对于较大的 r 值，它会非常慢。我建议这样的事情：

for (int s = MAX_SHIFT; s>=0; s--)
  if (r > (b<<s)) r -= (b<<s);

但我怀疑你的编译器做的事情比这贵得多。

score 3 · Accepted Answer

如果您的 C 编译器针对的是没有除法指令的 CPU，您可以按如下方式修改您的代码：

mod(a, b) {
    int s = b + b + b + b;
    int r = a;
    while(r >= s) {
        r -= s;
    }
    while(r >= b) {
        r -= b;
    }
    return r;
}

这通过减去四个而不是一个块中的值来工作，直到最后一个，然后它切换到减去一个块。

这应该使您的代码运行速度提高大约四倍（假设4*b不在整数范围之外）。您甚至可以在一个循环8*b之前插入更多循环（比如一个）4*b以提高速度。

除此之外，手动编码汇编器可能会有所帮助，但我认为如果没有它，您会从上面的代码中找到相当大的提升。

如果您了解有关使用 mod 调用方式的更多详细信息，则可以针对您的特定情况对其进行优化。例如，如果您只想知道 16 位整数的模 25，那么下面的代码将比具有可变分母的简单循环快得多。

int mod25 (int a) {                // a has maximum value of 2^15-1 = 32767
    while (a >= 15625) a-= 15625;  // at most 2 times.
    while (a >= 625) a-= 625;      // at most 24 times.
    while (a >= 25) a-= 25;        // at most 24 times.
    return a;
}

运行测试，我发现您必须进行 1000 万次迭代才能在模代码和%运算符的使用之间出现明显差异（2 秒与 0 秒）。直到那时，它们都是 0 秒，尽管它是在快速机器上运行的（对更好）mod25并且有div指令（对%操作员更好），所以你需要在你自己的硬件上对其进行基准测试。

在不使代码不可读的情况下，这几乎是您可能获得的最快速度（尽管如果您愿意添加大量注释来解释它是如何工作的，即使这样也不应该阻止您）。

对于任何分母，一个更通用的解决方案是首先将分母加倍（为了速度而进行位移），以使随后的减法最小化。然后，当分子减少到低于增加的分母时，将分母减半并继续前进（直到分母回到起点）。

int mod (int n, int d) {
    /* dx is the adjusted denom, don't let it overflow though. */
    int dx = d;
    while (((dx << 1) >>1) == dx)
        dx <<= 1;

    /* This loop processes the dx values until they get too small. */
    while (dx >= d) {
        /* This loop subtracts the large dx value. */
        while (n >= dx)
            n -= dx;
        dx >>= 1;
    }
    return n;
}

这实际上与上述优化版本的性能相当，mod25同时提供了更通用的解决方案。

score 3 · Accepted Answer

在许多处理器上，整数乘法比整数除法更快。这篇博文展示了如何用常数整数乘法替换常数整数除法。通过重新排列数学，您可以获得余数而不是商。但是请注意，如果您使用的是中等复杂的编译器，那么这已经为您完成了。你只需要编写x % 25，编译器就会解决剩下的问题。在用 C 进行优化之前，您应该检查为您的代码生成的汇编代码，验证编译器是否已经这样做了。此外，您应该测量（分析）之前和之后的性能，以确保您确实让事情变得更快.

对于相当大的操作数，循环将比使用本机指令进行除法要慢得多。

编辑：另见本文。

score 2 · Accepted Answer

请参与一些常识。

如果您可以编写比编译器更快地计算 x % 25 的 C 代码，那么编译器将使用这种更快的方法。

原始海报做出了一个奇妙的假设，即编译器将使用除法。我在过去十年中使用的任何编译器都不会这样做。这是乘以接近 (2^32 / 25) 的常数加上一些你无法手动改进的小玩意儿。

您可以生成比编译器更快的代码来确定 x % 25 == 0 的可能性很小，因为您实际上不需要正确计算 x % 25 的代码，只需要正确计算 x % 25 的代码，如果它是 0，如果 x % 25 != 0 则不会产生 0。节省的时间可能是亚纳秒。

“如何针对各种常数 c 优化计算 x % c”是一个很好的谜题。编译器作者喜欢漂亮的谜题。他们比你更擅长解决这样的难题。特别是因为他们只需要一个适用于您必须生成通用解决方案的机器的解决方案。

score 1 · Accepted Answer

如果您不喜欢%运营商：

int mod(int a, int b) {
    int integral = a / b;
    return a - (b*integral);
}

score 1 · Accepted Answer

如果您知道这b将是 2 的幂，则可以使用按位AND而不是模运算符。但是，模数的维基百科页面似乎表明任何 C 编译器都会注意到这一点并优化模数。

score 1 · Accepted Answer

可能不是最快但相当有效的。我没有时间测试，但使用（2 的幂）* 25 的查找表，直到最大范围/2。然后做一个循环。例如，高达 3199 的范围需要 7 次迭代。

static int pow[] = {25, 50, 100, 200, 400, 800, 1600};

int mod25(int x)
{    
    int i = sizeof pow /sizeof pow[0];

    while (i--)
    {
        if (x >= pow[i])
            x -= pow[i];    
    }    
    return x;
}

如果您有一个非常大的范围但较低的值更常见，那么使用二进制印章来找到起点可能是值得的。

score 1 · Accepted Answer

int mod25(int x) {
  static int divisors[] = {2147483625, 244140625, 9765625, 390625, 15625, 625, 25};
  int i;
  for (i = 0; i < sizeof(divisors)/sizeof(int); i++) {
    int divisor = divisors[i];
    while (x >= divisor) {
      x -= divisor;
    }
  }
  return x;
}

它是如何工作的：我们希望以x25 的大倍数递减以尽可能快地降低值。当除数太大时，我们切换到 25 的较小倍数。如果除数已经下降到 25，那么我们就完成了。

您可以尝试使用不同的除数进行试验。您只想确保：

他们在下降
它们都是 25 的倍数
最后一个值为 25

在上面的代码中，我使用了 25 的最大有符号 32 位倍数加上 25 的幂，这似乎是合理的，尽管我不得不承认我不确定它是否是最优的。

（顺便说一句：如果你的编译器不做常量折叠——这将是非常i令人惊讶的——那么你可能想用一个硬编码的常量替换上限。）

score 0 · Accepted Answer

为什么不能只使用运算符%？如果这是 C 代码，并且数字是普通的“本机” int：s，那么这应该是迄今为止最快的方式。

score 0 · Accepted Answer

有没有理由不能使用 C 的内置模数运算符？

int a = x % 25;

按照您的编辑；

如果您的处理器没有内置模数支持，那么我仍然会使用 % 运算符，原因很简单，因为您的编译器会知道所讨论的处理器没有本机 % 函数，并且可能会生成 asm 代码以最佳地模拟它。

这么说吧 - 如果你能想出一个通用算法，它优于编译器使用内置运算符产生的什么，我会很着迷，尽管有特定情况（例如简单地取模 100 的 2 个最低数字等）

score 0 · Accepted Answer

我觉得这个操作x % 25需要这么长时间很奇怪（如果你使用的是内置%运算符，那就是）。大多数现代处理器应该在一条指令中执行此操作。我会寻找这段代码需要这么长时间的其他原因。

编辑：这是一个至少可以给出一些想法的算法：

256 = 6（模 25）

这意味着如果我们将一个数字写x为字节x3 x2 x1 x0，我们就有了x = 6^3*x3 + 6^2*x2 + 6*x1 + x0（mod 25）

这给出了一个减小大小的算法x：

int x0 = x & 0xFF, x1 = (x>>8) & 0xFF, x2 = (x>>16) & 0xFF, x3 = (x>>24) & 0xFF;

int y = x4;
y = (y << 2) + (y << 1) + x3;
y = (y << 2) + (y << 1) + x2;
y = (y << 2) + (y << 1) + x1;
y = (y << 2) + (y << 1) + x0;

（这里(y << 2) + (y << 1) = 4*y + 2*y = 6*y）

在此之后y将具有与 mod 25 相同的余数。x迭代这 1、2 或 3 次将y分别生成 17、11 或 9 位数。这些尺寸之一可能小到足以制作查找表。

不过，我严重怀疑这会比内置%运算符更快。

score 0 · Accepted Answer

怎么样：

int y = 0, x = (x & 0x7f); 
while (x > 25) { x -= 25; y++; }

更新：这是非常错误的 :) 但想法就在那里。

score 0 · Accepted Answer

如果您将数字保存在 BCD 或数字字节数组中，这将非常容易。不幸的是，我不知道你在你的程序中用这些数字做什么。有时看看你如何表示你的数据而不是仅仅研究算法是值得的。

score 0 · Accepted Answer

这是一个想法

static int table0[256];
static int table1[256];
static int table2[256];
static int table3[256];

// ran just once to initialize the tables
void initialMod25Tables() {
    for (int i = 0; i < 256; ++i) {
        table0[i] = i % 25;
    }
    for (int i = 0; i < 256; ++i) {
        table1[i] = (i << 8) % 25;
    }
    for (int i = 0; i < 256; ++i) {
        table2[i] = (i << 16) % 25;
    }
    for (int i = 0; i < 256; ++i) {
        table3[i] = (i << 24) % 25;
    }
}

int mod25(int x) {
    int y = table0[x & 0xFF];
    x >>= 8;
    y += table1[x & 0xFF];
    x >>= 8;
    y += table2[x & 0xFF];
    x >>= 8;
    y += table3[x & 0xFF];
    y = table0[y];
    return y;
}

score 0 · Accepted Answer

在使用大卫约翰斯通关于 Pax 算法的答案后修改的通用算法。这大大减少了循环周期，并且应该解决 Skizz 的问题。

unsigned mod(unsigned a, unsigned b) {
    if (a < b) return a;
    unsigned s = b, ret = a;
    while(ret >= b){
        while(s <= ret){
            s <<= 3;
        }
        while (s > ret && s > b) {
             s >>= 3;
        }
        if(s < b) s = b;
        while (ret >= s){
            ret -= s;
        }
    }
    return ret;
}

我已经mod(536870910, 25)作为测试用例运行了。理论上，如果 int 是 32 位，a这个函数可以毫无问题地处理的最大数量将是UINT_MAX <<= 3或大约。536870910

int mod =  mod(536870910, 25) // mod will be 10

该函数有四个while()循环。为了测试效率，我在每个循环上都设置了计数器。mod(536870910, 25)在循环计数器的情况下，while总数分别为 8、9、9 和 26。如果使用直接减法计算 536870910 % 25，则需要循环超过 21,000,000 次。

那么，为什么要尝试确定一种算法来执行%操作员已经执行的操作呢？在我的情况下，我使用类似的函数来mod()处理非常大的自定义类型的数字，因此我需要自己的算法来重载%运算符以使用我的类型。所以就我而言，该mod()函数使用特殊类型而不是无符号整数。

对于它的价值，上面函数中的<<= 3and>>=3可以改为<<=1and >>=1。当我在测试时，更大的转变似乎减少了循环周期。重要的是使用相同数量的来回移位。

score -1 · Accepted Answer

如果您只考虑数字 25，您可以使用以下事实：当且仅当整数的最后两位数是 00、25、50 或 75 时，25 除以整数。因此，要获得模数，您需要考虑最后两位数和然后减去最接近的 00、25、50 或 75。

c - 计算模 25 的高效（循环）算法？

22 回答 22

Related

Reference