c++ - 单词分割算法

Question

我为嵌入式平台开发软件，需要一个单词划分算法。

问题如下：给定一个由 32 位字序列表示的大整数（可以是多个），我们需要将它除以另一个 32 位字，即计算商（也是大整数）和余数 ( 32 位）。

当然，如果我在 x86 上开发这个算法，我可以简单地使用 GNU MP，但是这个库对于嵌入式平台来说太大了。此外，我们的处理器没有硬件整数除法器（整数除法在软件中执行）。然而，处理器具有相当快的 FPU，因此诀窍是尽可能使用浮点运算。

任何想法如何实现这一点？

Answer 1

看一下这个：该算法使用浮点将整数 a[0..n-1] 除以单个单词 'c' 进行 64x32->32 除法。商 'q' 的四肢只是打印在一个循环中，如果你愿意，你可以将其保存在一个数组中。请注意，您不需要 GMP 来运行算法 - 我只是用它来比较结果。

#include <gmp.h>

// divides a multi-precision integer a[0..n-1] by a single word c
void div_by_limb(const unsigned *a, unsigned n, unsigned c) {

  typedef unsigned long long uint64;
  unsigned c_norm = c, sh = 0;
  while((c_norm & 0xC0000000) == 0) { // make sure the 2 MSB are set
     c_norm <<= 1; sh++;
  }
  // precompute the inverse of 'c'
   double inv1 = 1.0 / (double)c_norm, inv2 = 1.0 / (double)c;
   unsigned i, r = 0;

   printf("\nquotient: "); // quotient is printed in a loop
   for(i = n - 1; (int)i >= 0; i--) { // start from the most significant digit
      unsigned u1 = r, u0 = a[i];
      union {
        struct { unsigned u0, u1; };
        uint64 x;
      } s = {u0, u1}; // treat [u1, u0] as 64-bit int
      // divide a 2-word number [u1, u0] by 'c_norm' using floating-point
      unsigned q = floor((double)s.x * inv1), q2;
      r = u0 - q * c_norm;
      // divide again: this time by 'c'
      q2 = floor((double)r * inv2);

      q = (q << sh) + q2; // reconstruct the quotient
      printf("%x", q);
  }

  r %= c; // adjust the residue after normalization
  printf("; residue: %x\n", r);
}

int main() {
  mpz_t z, quo, rem;
  mpz_init(z); // this is a dividend
  mpz_set_str(z, "9999999999999999999999999999999", 10);
  unsigned div = 9; // this is a divisor
  div_by_limb((unsigned *)z->_mp_d, mpz_size(z), div);
  mpz_init(quo); mpz_init(rem);
  mpz_tdiv_qr_ui(quo, rem, z, div); // divide 'z' by 'div'
  gmp_printf("compare: Quo: %Zx; Rem %Zx\n", quo, rem);
  mpz_clear(quo);
  mpz_clear(rem);
  mpz_clear(z);
  return 1;
}

Answer 2

听起来像是经典的优化。而不是除以D，乘以0x100000000/D然后除以0x100000000。后者只是一个字移，即微不足道。计算乘数有点困难，但不是很多。

另请参阅这篇详细的文章以获取更详细的背景信息。

Answer 3

我相信查找表和Newton Raphson逐次逼近是硬件设计人员使用的规范选择（他们通常买不起完整的硬件划分的大门）。您可以在准确性和执行时间之间进行权衡。