c - 将商和提醒划分并存储在不同的数组中

Question

标准的 div() 函数返回一个 div_t 结构作为参数，例如:

/* div example */
#include <stdio.h>      /* printf */
#include <stdlib.h>     /* div, div_t */

int main ()
{
  div_t divresult;
  divresult = div (38,5);
  printf ("38 div 5 => %d, remainder %d.\n", divresult.quot, divresult.rem);
  return 0;
}

我的情况有点不同；我有这个

#define NUM_ELTS 21433
int main ()
{
  unsigned int quotients[NUM_ELTS];
  unsigned int remainders[NUM_ELTS];
  int i;

  for(i=0;i<NUM_ELTS;i++) {
      divide_single_instruction(&quotient[i],&reminder[i]);
  }
}

我知道用于除法的汇编语言在一条指令中完成所有事情，所以我需要在这里做同样的事情以节省 cpu 周期，这基本上是将商从 EAX 和提醒从 EDX 移动到我的数组所在的内存位置被存储。如果不在我的 C 代码中包含 asm {} 或 SSE 内在函数，如何做到这一点？它必须是可移植的。

Answer 1

由于您是就地写入数组(用商和余数替换分子和分母)，您应该在写入数组之前将结果存储到临时变量。

void foo (unsigned *num, unsigned *den, int n) {
    int i;
    for(i=0;i<n;i++) {
        unsigned q = num[i]/den[i], r = num[i]%den[i];   
        num[i] = q, den[i] = r;
    }
}

生成这个主循环程序集

.L5:
        movl    (%rdi,%rcx,4), %eax
        xorl    %edx, %edx
        divl    (%rsi,%rcx,4)
        movl    %eax, (%rdi,%rcx,4)
        movl    %edx, (%rsi,%rcx,4)
        addq    $1, %rcx
        cmpl    %ecx, %r8d
        jg      .L5

有一些更复杂的情况，在第一次使用商和余数时，它有助于保存它们。例如，在通过试验除法测试素数时，您经常会看到这样的循环

for (p = 3; p <= n/p; p += 2)
    if (!(n % p)) return 0;

事实证明GCC does not use the remainder from the first division因此它执行了两次除法指令，这是不必要的。要解决此问题，您可以在第一次除法完成时保存余数，如下所示:

for (p = 3, q=n/p, r=n%p; p <= q; p += 2, q = n/p, r=n%p)
    if (!r) return 0;

这将结果速度提高了两倍。

所以一般来说，GCC 做得很好，特别是如果您在第一次计算时保存商和余数。