Hundredsoft

前回同様、除算 a = x / y があったとして
式を変形して、

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

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

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

  Bigint a(0), m(0);
  while (n--){
    m |= 1;
    a <<= 1;
    if (m >= y){
      m -= y;
      a |= 1;
    }
    m <<= 1;
  }
  a *= x;
  m = 1;
  m <<= xb;
  a += m;
  return a >> (xb*2-1);
}

この方法は、被除数bit数の倍のループとなり、これが最大の減算回数になります。
しかし誤差が出ないので乗算は１回だけで済みます。
前回の方法はbit差に依存したループ回数なので多桁にも応用できますが、この方法だと被除数が大きいとループ回数が多くなってしまいます。

桁差が小さい時に有利な方法

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

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

---

Tags: プログラムメモ