我将限制我的评论在整数除法上,因为从一级角度来看,C++中的模运算可以被视为整数除法加上反向乘法和减法实现,尽管在某些情况下,有更便宜的直接计算模数的方法,例如计算模2
n时。
在大多数平台上,基于软件仿真或迭代硬件实现,整数除法非常缓慢。但是去年根据对苹果M1的微基准测试广泛报道称,它具有极快的整数除法,可能是通过使用专用电路实现的。
自从Torbjörn Granlund和Peter Montgomery在近30年前发表了一篇开创性论文以来,人们就已经广泛知道如何使用整数乘法加上可能的移位和/或其他校正步骤来替换具有恒定除数的整数除法。这个算法通常被称为魔术乘法器技术。它需要预先计算一些与整数除数相关的参数,以用于基于乘法的仿真序列中。
Torbjörn Granlund和Peter L. Montgomery,“Division by invariant integers using multiplication”,ACM SIGPLAN Notices,Vol. 29,June 1994,pp. 61-72 (
online)。
目前,所有主要的工具链在处理整数除数为编译时常量时都采用Granlund-Montgomery算法的变体。预计算发生在编译器内部的编译时,然后编译器使用计算出的参数生成代码。一些工具链也可能使用这个算法来处理重复使用的运行时常量除数的除法。对于循环中的运行时常量除数,这可能涉及在循环之前发出一个预计算块来计算必要的参数,然后在循环内使用这些参数进行除法模拟代码。
如果一个工具链不能优化具有运行时常量除数的除法,则可以手动使用下面代码所示的相同方法。然而,这不太可能达到与基于编译器的解决方案相同的效率,因为在C++级别上不能以便携方式高效地表达所需仿真序列中使用的所有机器操作。这尤其适用于算术右移和带进位的加法。
下面的代码演示了通过乘法进行参数预计算和整数除法仿真的原理。通过投入更多的时间进行设计,很可能可以找到更有效的参数预计算和仿真实现。
#include <cstdio>
#include <cstdlib>
#include <cstdint>
#define PORTABLE (1)
uint32_t ilog2 (uint32_t i)
{
uint32_t t = 0;
i = i >> 1;
while (i) {
i = i >> 1;
t++;
}
return (t);
}
void prepare_magic (int32_t divisor, int32_t &multiplier, int32_t &add_mask, int32_t &sign_shift)
{
uint32_t divisoru, d, n, i, j, two_to_31 = uint32_t (1) << 31;
uint64_t m_lower, m_upper, k, msb, two_to_32 = uint64_t (1) << 32;
divisoru = uint32_t (divisor);
d = (divisor < 0) ? (0 - divisoru) : divisoru;
i = ilog2 (d);
j = two_to_31 % d;
msb = two_to_32 << i;
k = msb / (two_to_31 - j);
m_lower = msb / d;
m_upper = (msb + k) / d;
n = ilog2 (uint32_t (m_lower ^ m_upper));
n = (n > i) ? i : n;
m_upper = m_upper >> n;
i = i - n;
multiplier = int32_t (uint32_t (m_upper));
add_mask = (m_upper >> 31) ? (-1) : 0;
sign_shift = int32_t ((divisoru & two_to_31) | i);
}
int32_t arithmetic_right_shift (int32_t a, int32_t s)
{
uint32_t msb = uint32_t (1) << 31;
uint32_t ua = uint32_t (a);
ua = ua >> s;
msb = msb >> s;
return int32_t ((ua ^ msb) - msb);
}
int32_t magic_division (int32_t dividend, int32_t multiplier, int32_t add_mask, int32_t sign_shift)
{
int64_t prod = int64_t (dividend) * multiplier;
int32_t quot = (int32_t)(uint64_t (prod) >> 32);
quot = int32_t (uint32_t (quot) + (uint32_t (dividend) & uint32_t (add_mask)));
#if PORTABLE
const int32_t byte_mask = 0xff;
quot = arithmetic_right_shift (quot, sign_shift & byte_mask);
#else
quot = quot >> sign_shift;
#endif
quot = int32_t (uint32_t (quot) + (uint32_t (dividend) >> 31));
if (sign_shift < 0) quot = -quot;
return quot;
}
int main (void)
{
int32_t multiplier;
int32_t add_mask;
int32_t sign_shift;
int32_t divisor;
for (divisor = -20; divisor <= 20; divisor++) {
if (divisor == 0) {
divisor++;
continue;
}
printf ("divisor=%d\n", divisor);
prepare_magic (divisor, multiplier, add_mask, sign_shift);
printf ("multiplier=%d add_mask=%d sign_shift=%d\n",
multiplier, add_mask, sign_shift);
printf ("exhaustive test of dividends ... ");
uint32_t dividendu = 0;
do {
int32_t dividend = (int32_t)dividendu;
if ((divisor == (-1)) && (dividend == ((-2147483647)-1))) {
dividendu++;
continue;
}
int32_t res = magic_division (dividend, multiplier, add_mask, sign_shift);
int32_t ref = dividend / divisor;
if (res != ref) {
printf ("\nERR dividend=%d (%08x) divisor=%d res=%d ref=%d\n",
dividend, (uint32_t)dividend, divisor, res, ref);
return EXIT_FAILURE;
}
dividendu++;
} while (dividendu);
printf ("PASSED\n");
}
return EXIT_SUCCESS;
}
value*(uint64_t)range
。因此,value
必须在完整的32位范围内相对均匀地分布。 - Peter Cordes(i,j) -> i * N + j
映射,而是将其映射为(i,j) -> i * 2^K + j
,其中2^K >= N
。然后就是通过 2 的幂进行除法/模运算,这比任何整数除法算法都要快得多。因此,我的问题的解决方案与这个问题完全不同 :D - Huy Le