最优化的计算C模数的方法

Question

我用C计算模数的成本最小化.假设我有一个数字x而n是将x除以的数字

当n == 65536(恰好是2 ^ 16)时:

mod = x%n(由GCC生成的11个汇编指令)或
mod = x&0xffff,等于mod = x&65535(4个汇编指令)

因此,海湾合作委员会并未对此进行优化.

在我的例子中,n不是x ^(int),而是小于2 ^ 16的最大素数,即65521

正如我在n == 2 ^ 16中所展示的那样,逐位运算可以优化计算.当n == 65521计算模数时,我可以执行哪些按位操作.

Answer 1

首先,确保在查看GCC正在生成的结论之前查看优化代码(并确保确实需要优化此特定表达式).最后 - 不要指望得出结论; 可能期望11指令序列比包括div指令的较短序列执行得更好.

此外,您无法得出结论,因为x mod 65536可以使用简单的位掩码计算任何mod操作都可以通过这种方式实现.考虑如何轻松除以十进制10而不是除以任意数.

完成所有这些后,您可以使用Henry Warren的Hacker's Delight书中的一些"幻数"技术:

• http://www.hackersdelight.org/
• http://www.hackersdelight.org/magic.htm

这里有一个在网站上添加章节包含"计算所得的余数,而不计算商的两种方法!",你可能会发现一些使用.第一种技术仅适用于一组有限的除数,因此它不适用于您的特定实例.我还没有真正阅读过在线章节,因此我不确切知道其他技术对您的适用程度.

Answer 2

如果x是无符号的,则x mod 65536仅等效于x和0xffff - 对于带符号的x,它给出负数的错误结果.对于无符号x,gcc确实优化x % 65536为按位和65535(在我的测试中甚至在-O0上).

因为65521不是2的幂,所以不能如此简单地计算x mod 65521.gcc 4.3.2 on -O3使用计算它x - (x / 65521) * 65521; 使用整数乘法乘以相关常数来完成常数的整数除法.

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为模数执行大量操作.为了有效地实现它,人们只能在精心计算的加法数量之后进行模块化约简.如上所示的减少就足够了,只有散列的计算才需要完整的模运算.

Answer 4

idiv \xe2\x80\x94 整数除法

\n\n

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

\n\n

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

\n