4

組み込みプラットフォーム用のソフトウェアを開発しており、1語の除算アルゴリズムが必要です。

問題は次のとおりです。32ビットワードのシーケンスで表される大きな整数（多くの場合もあります）が与えられた場合、それを別の32ビットワードで除算する必要があります。つまり、商（これも大きな整数）と余り（ 32ビット）。

確かに、このアルゴリズムをx86で開発している場合は、GNU MPを使用するだけで済みますが、このライブラリはembdeddeプラットフォームには大きすぎます。さらに、私たちのプロセッサにはハードウェア整数除算器がありません（整数除算はソフトウェアで実行されます）。ただし、プロセッサのFPUは非常に高速であるため、可能な限り浮動小数点演算を使用するのがコツです。

これを実装する方法はありますか？

4

3 に答える 3

1

古典的な最適化のように聞こえます。で割る代わりにD、で乗算し0x100000000/Dてからで除算し0x100000000ます。後者は単なるワードシフト、つまり些細なことです。乗数の計算は少し難しいですが、それほど多くはありません。

はるかに詳細な背景については、この詳細な記事も参照してください。

于 2012-08-10T14:11:18.740 に答える
1

これを見てください。アルゴリズムは、64x32-> 32除算の浮動小数点を使用して、整数a[0..n-1]を単一の単語「c」で除算します。商「q」の手足はループで出力されるだけです。必要に応じて、配列に保存できます。アルゴリズムを実行するのにGMPは必要ないことに注意してください。私は、結果を比較するためだけに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;
}
于 2012-08-10T16:48:31.527 に答える
1

ルックアップテーブルとニュートンラフソン逐次近似は、ハードウェア設計者（通常、ハードウェアを完全に分割するためのゲートを買う余裕がない）が使用する標準的な選択であると思います。精度と実行時間の間のトレードオフを選択できます。

于 2012-08-10T21:07:45.343 に答える