有效地实现floored / euclidean整数除法
地板划分是指结果总是向下（朝-∞），而不是0：
是否有可能在C / C ++中有效地实现floored或euclidean整数除法？
（显而易见的解决方案是检查股息的标志）
五年后我正在重新审视这个问题，因为这对我也很重要。 我对x86-64的两个纯C版本和两个内联汇编版本进行了一些性能测量，结果可能很有趣。
经过测试的分层变体是：
- 我已经使用了一段时间了;
- 上面提到的轻微变体只使用一个分区;
- 前一个，但在内联汇编中手工实现; 和
- 在汇编中实现的
CMOV版本。
以下是我的基准程序：
#include #include #include #ifndef VARIANT #define VARIANT 3 #endif #if VARIANT == 0 #define floordiv(a, b) (((a) < 0)?((((a) + 1) / (b)) - 1):((a) / (b))) #elif VARIANT == 1 #define floordiv(a, b) ((((a) < 0)?((a) - ((b) - 1)):(a)) / (b)) #elif VARIANT == 2 #define floordiv(a, b) ({ \ int result; \ asm("test %%eax, %%eax; jns 1f; sub %1, %%eax;" \ "add $1, %%eax; 1: cltd; idivl %1;" \ : "=a" (result) \ : "r" (b), \ "0" (a) \ : "rdx"); \ result;}) #elif VARIANT == 3 #define floordiv(a, b) ({ \ int result; \ asm("mov %%eax, %%edx; sub %1, %%edx; add $1, %%edx;" \ "test %%eax, %%eax; cmovs %%edx, %%eax; cltd;" \ "idivl %1;" \ : "=a" (result) \ : "r" (b), \ "0" (a) \ : "rdx"); \ result;}) #endif double ntime(void) { struct timeval tv; gettimeofday(&tv, NULL); return(tv.tv_sec + (((double)tv.tv_usec) / 1000000.0)); } void timediv(int n, int *p, int *q, int *r) { int i; for(i = 0; i < n; i++) r[i] = floordiv(p[i], q[i]); } int main(int argc, char **argv) { int n, i, *q, *p, *r; double st; n = 10000000; p = malloc(sizeof(*p) * n); q = malloc(sizeof(*q) * n); r = malloc(sizeof(*r) * n); for(i = 0; i < n; i++) { p[i] = (rand() % 1000000) - 500000; q[i] = (rand() % 1000000) + 1; } st = ntime(); for(i = 0; i < 100; i++) timediv(n, p, q, r); printf("%g\n", ntime() - st); return(0); }
我使用GCC 4.9.2用gcc -march=native -Ofast编译了这个，在我的Core gcc -march=native -Ofast的结果如下。 从运行到运行，结果是相当可重复的 - 它们总是以相同的顺序着陆，至少。
- 变体0：7.21秒
- 变体1：7.26秒
- 变体2：6.73秒
- 变体3：4.32秒
因此， CMOV实施至少可以将其他人从水中吹走。 让我感到惊讶的是，变种2出现了相当广泛的纯C版本（变体1）。 我原以为编译器应该能够发出至少和我一样高效的代码。
以下是一些其他平台，供比较：
AMD Athlon 64 X2 4200+，GCC 4.7.2：
- 变体0：26.33秒
- 变体1：25.38秒
- 变体2：25.19秒
- 变式3：22.39秒
Xeon E3-1271 v3，GCC 4.9.2：
- 变体0：5.95秒
- 变体1：5.62秒
- 变体2：5.40秒
- 变体3：3.44秒
我写了一个测试程序来对这里提出的想法进行基准测试：
#include #include #include #include #define N 10000000 #define M 100 int dividends[N], divisors[N], results[N]; __forceinline int floordiv_signcheck(int a, int b) { return (a<0 ? a-(b-1) : a) / b; } __forceinline int floordiv_signcheck2(int a, int b) { return (a - (a<0 ? b-1 : 0)) / b; } __forceinline int floordiv_signmultiply(int a, int b) { return (a + (a>>(sizeof(a)*8-1))*(b-1)) / b; } __forceinline int floordiv_floatingpoint(int a, int b) { // I imagine that the call to floor can be replaced to a cast // if you can get FPU rounding control to work (I couldn't). return floor((double)a / b); } void main() { for (int i=0; i
结果：
signcheck : 61458768 signcheck2 : 61284370 signmultiply : 61625076 floatingpoint: 287315364
所以，根据我的结果，检查标志是最快的：
(a - (a<0 ? b-1 : 0)) / b
由于分支是昂贵的，因此可以更有效地提出一些免费的分支来根据符号校正结果。
请参阅Hacker’s Delight中第2章第20页，了解如何访问该符号。
是否有可能在C / C ++中有效地实现floored或euclidian整数除法？
是。
（显而易见的解决方案是检查股息的标志）
我完全同意，并且很难相信存在明显更快的替代方案。
请注意：当涉及到2的幂时，x86 sar指令执行浮动除法。
由于IEEE-754指定round -inf作为所需的舍入模式之一，我想你的问题的答案是肯定的。 但也许您可以解释一下，如果您正在编写编译器，或者知道如何使用特定的编译器来执行操作，您是否想知道如何实现该过程？