回復法を使った2進多桁の除算
プログラムメモ | 2010/10/03 Sun 08:14
| 除算 a = x / y があったとして
回復法を使うと被除数のbit数分の加算・減算を繰り返し行うことになる
式を変形して、
と書ける。
計算量は最大でもbit差程度の加減算と2回の乗算なので
bit差が数100のオーダーならNewton法を使うより有利かも。
ニュートン法を使った2進多桁の整数除算
(注)ここでのBigintクラスは、多倍長整数を格納する仮想のクラスであり、実在するものではありません。
Tags: プログラムメモ
回復法を使うと被除数のbit数分の加算・減算を繰り返し行うことになる
式を変形して、
とすれば、逆数を求める部分((2^k)/y)の回復法は特殊な被除数のため、簡単なものに変形できる。
a = (x * ((2^k)/y) >> k (k:=被除数のbit数)
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差程度の加減算と2回の乗算なので
bit差が数100のオーダーならNewton法を使うより有利かも。
ニュートン法を使った2進多桁の整数除算
(注)ここでのBigintクラスは、多倍長整数を格納する仮想のクラスであり、実在するものではありません。
Tags: プログラムメモ
author : HUNDREDSOFT | - | -