Hundredsoft

除算 a = x / y があったとして
回復法を使うと被除数のbit数分の加算・減算を繰り返し行うことになる
式を変形して、

a = (x * ((2^k)/y) >> k  (k:=被除数のbit数)

とすれば、逆数を求める部分((2^k)/y)の回復法は特殊な被除数のため、簡単なものに変形できる。

Bigint iDiv(Bigint x, Bigint y){
  Bigint a(0), m(1);
  int xb = x.length(); // 被除数のbit数
  int yb = y.length(); // 除数のbit数
  int n = xb - yb + 1; // ループ回数(bit差+1)

  m <<= yb-1;
  while (n--){
    a <<= 1;
    if (m >= y){
      m -= y;
      a |= 1;
    }
    m <<= 1;
  }
  a *= x;
  a >>= (xb - 1);

  // 誤差修正(ここでのaは,正解より1or2小さい場合がある)
  m = y * a;
  while(x > m){
    m += y;
    if (x > m)
      a += 1;
  }
  return a;
}

と書ける。
計算量は最大でもbit差程度の加減算と２回の乗算なので
bit差が数100のオーダーならNewton法を使うより有利かも。

ニュートン法を使った２進多桁の整数除算

(注)ここでのBigintクラスは、多倍長整数を格納する仮想のクラスであり、実在するものではありません。

---

Tags: プログラムメモ