在C语言中计算模数的最优方法

Question

我已经在C语言中将计算模数的成本最小化了。 假设我有一个数字x，n是将被x除的数字。

当n == 65536（恰好是2^16）时：

mod = x % n（由GCC产生的11条汇编指令） 或 mod = x & 0xffff，等同于mod = x & 65535（4个汇编指令）

所以，GCC没有对其进行如此程度的优化。

在我的情况下，n不是x^(int)，而是小于2^16的最大质数，即65521。

正如我展示n == 2^16时那样，位运算可以优化计算。 当n == 65521时，我可以执行哪些位运算来计算模数。

- hasanatkazmi

---

我无法想象任何C编译器将整数％实现为除了设置之外的单个指令IDIV（请参见Krystian的答案）。 我毫不怀疑，在同一CPU上没有任何算法可以更快地获得结果。 - Carl Smotricz

你有开启 -O2 吗？你在 n 的声明中添加了 const 关键字吗？ - P Shved

@Carl，仅仅因为它是单个指令，并不意味着它是你能得到的最快的。举个例子，在2000年，通过在纯C代码中执行多个操作（无需汇编），就可以计算出sqrt并在速度和准确性上击败处理器（我认为现在的新处理器内部也使用相同的技巧）。一个单独的指令不一定需要一个周期来计算！ - Grant Peters

@Carl：编译器通常会通过编译时常量优化除法或取余操作。通常，取余操作被转换为涉及一对乘法、一些位移和可能有一两个加法的序列。请搜索Granlund和Montgomery在此领域中的原始工作《使用乘法进行不变整数的除法》获取更多信息。 - Mark Dickinson

请注意，如果模数是编译时常量，则使用模运算更容易实现无符号参数。如果使用带符号参数进行此操作，则需要一些额外的指令。 - Accipitridae

Answer 1

首先，在得出关于GCC生成的代码的结论之前，请确保您正在查看优化后的代码（并确保这个特定的表达式确实需要进行优化）。最后，不要仅凭指令数来得出结论；可能一个11条指令序列比包含一个div指令的较短序列执行得更好。

此外，您不能得出这样的结论：因为可以使用简单的位掩码计算x mod 65536，所以任何模运算都可以以这种方式实现。考虑一下在十进制中除以10相对于除以任意数字是多么容易。

在解决了所有这些问题之后，您可以使用亨利·沃伦的《黑客秘笈》中的一些“魔术数字”技巧：

• http://www.hackersdelight.org/的存档
• http://www.hackersdelight.org/magic.htm的存档

网站上有一个补充的章节，其中包含“两种计算除法余数但不计算商的方法！”这可能对您有所帮助。第一种技术仅适用于有限的除数集，因此它在您的特定实例中无法使用。我实际上没有阅读过在线章节，因此不知道另一种技术对您来说有多可行。

- Michael Burr

---

黑客的乐趣（Hacker's Delight）和相关网站是很好的资源。请注意，如果你有一些编译器缺少的额外信息（例如，从上下文或算法分析中得知除数的可能大小的上界），有时可能比编译器更好地完成任务。 - Mark Dickinson

最后一章几乎仅限于由(2^k +/- 1)表示的值。因此，它只适用于非常狭窄的问题子集。虽然经过优化，但绝对不是通用的。因此，在我们定义的现实的广泛应用中，我看不到很多用途。 - ingyhere

Answer 2

如果x是无符号的，则x mod 65536仅相当于x & 0xffff，对于有符号的x，它会对负数给出错误的结果。对于无符号的x，即使在我的测试中使用了-O0，gcc确实将x % 65536优化为与65535进行按位与操作。

因为65521不是2的幂，所以不能简单地计算x mod 65521。在-O3下，gcc 4.3.2使用x - (x / 65521) * 65521来计算它；通过相关常量的整数乘法来完成对常量的整数除法。

- caf

---

使用处理器的整数除法功能可能不是最佳选择。在我的机器上（Intel Core 2 Duo，以 64 位模式运行），使用 gcc 4.4 和 -O3 的简单 C 测试程序将 x％65521 转换为两个乘法、两个移位和两个减法。当然，确切的方法是进行一些计时。 :) - Mark Dickinson

实际的gcc输出：https://godbolt.org/g/yjvoru。请注意，`gcc -O0不会优化int n=65536; return x % n;，因为-O0使代码在使用调试器单步跟踪时仍然执行C源代码所说的内容，甚至跳转到另一行。也就是说，在C语句之间，它会溢出/重新加载所有内容，并且除了语句内部没有任何假设。我之所以指出这一点，是因为OP说他们有一个变量n，它恰好是65536。（在这种情况下，gcc -O0只使用idiv`。）无论如何，显然计算指令数!=性能分析！ - Peter Cordes

Answer 3

如果不需要将整数完全模65521，则可以利用65521接近2 ** 16的事实。也就是说，如果x是要缩小的无符号整数，则可以执行以下操作：

unsigned int low = x &0xffff;
unsigned int hi = (x >> 16);
x = low + 15 * hi;

这里使用的是 2**16 % 65521 == 15。注意，这不是完全的约减。也就是说，从32位输入开始，你只能保证结果最多为20位，并且当然与输入模65521同余。

这个技巧可以在需要对许多操作进行模相同常数约减并且中间结果不必是其剩余类中最小元素的应用程序中使用。

例如，一个应用是实现Adler-32，它使用模数65521。这个哈希函数执行很多模65521的操作。要有效地实现它，只需要在经过精心计算的添加次数后才进行模约减。像上面所示的约减已经足够了，只有哈希的计算需要完整的模运算。

- Accipitridae

Answer 4

如果除数是2^n的形式，那么位运算才能正常工作。在一般情况下，没有这样的位运算。

- Danvil

Answer 5

如果x是一个递增的索引，而增量i已知小于n（例如在迭代长度为n的循环数组时），则完全避免使用模数。 一个循环进行中。

x += i; if (x >= n) x -= n;

is way faster than

x = (x + i) % n;

which you unfortunately find in many text books...

If you really need an expression (e.g. because you are using it in a for statement), you can use the ugly but efficient

x = x + (x+i < n ? i : i-n)

- David

---

当n不是编译时常量的2的幂时，这是正确的。如果n是2的幂，则无条件地使用n-1进行按位与运算来执行无符号取模更快。（如果n是编译时常量且类型为无符号，则编译器将为您执行此操作。） - Peter Cordes

Answer 6

作为处理2的幂次方的一种方法，可以考虑这个（大多数是C风格的）：

.
.

#define THE_DIVISOR    0x8U;  /* The modulo value (POWER OF 2). */
.
.
uint8 CheckIfModulo(const sint32 TheDividend)
{
    uint8 RetVal = 1; /* TheDividend is not modulus THE_DIVISOR. */

    if (0 == (TheDividend & (THE_DIVISOR - 1)))
    {
        /* code if modulo is satisfied */
        RetVal = 0; /* TheDividend IS modulus THE_DIVISOR. */
    }
    else
    {
        /* code if modulo is NOT satisfied */
    }
    return RetVal;
}

- gabi tomuta

---

这个是否适用于程序员知道TheDivisor是2的幂次方，但编译器不知道的情况下有用？如果除数是编译时常量，则没有任何优势。 - Peter Cordes

为什么你把 0 % 8 视为假，而把 8 % 8 视为真？0 是 8 的倍数。这个方法并不只适用于被除数大于除数的情况。你使用了有符号整数，但这也适用于负被除数。（例如，-16 在32位二进制补码表示中是 0xfffffff0，因此检查低4位仍然可以检查它是否是16的倍数。） - Peter Cordes

Peter，感谢您的观察。我来自驱动程序开发领域，因此没有考虑过负数。但是您关于0的观察在这里完全适用，我已经纠正了我的例子。 - gabi tomuta

如果您的数字被认为是非负数，则无符号类型通常是一个不错的选择。除非编译器能够证明负数是不可能的，否则它必须生成正确的代码，这对于带有有符号整数的 x / 4 等操作通常会更慢（因为 C 中有符号除法/模运算的语义）。https://godbolt.org/g/crTsWi。假设在编写驱动程序时性能很重要，请使用适合工作的正确类型，以便编译器可以生成高效的代码。 - Peter Cordes

Answer 7

如果您想要取模的常数在编译时已知，并且您有一个好的编译器（例如gcc），通常最好让编译器发挥其作用。只需声明模数为const即可。

如果您在编译时不知道常数，但是您将使用相同数字进行十亿次取模，则使用此方法http://libdivide.com/。

- blondiepassesby

Answer 8

idiv — 整数除法

idiv 指令将 64 位整数 EDX:EAX（通过将 EDX 视为最高四个字节，EAX 视为最低四个字节构造）的内容除以指定的操作数值。除法的商结果存储在 EAX 中，而余数则放置在 EDX 中。

来源：http://www.cs.virginia.edu/~evans/cs216/guides/x86.html

- Kris

---

如果分母的值在运行时不确定，且使用 idiv 或类似的操作码（取决于 CPU）可能是最佳选择。但如果分母是已知常量，则可以执行一些优化，这些优化可能比 idiv 更快。然而，现今的编译器已经了解到这些优化（以及如何使用 div 操作码得到余数），所以在 C 程序中通常无需采取任何特殊措施来利用它们的优势。 - Michael Burr