多倍長整数の除算: Burnikel-Ziegler 法
多倍長整数の除算: Burnikel-Ziegler 法
この記事では基数を
乗算の計算量を
競技プログラミングでの実装はニュートン法で実装している人が多い印象ですが、精度の管理などややこしいので実用には実装が簡潔でわかりやすい Burnikel-Ziegler 法 がよく用いられているようです。
参考: 競プロでの提出例
実用されている例としては Go, Java(OpenJDK), JavaScript(v8) のランタイム実装で使われています。
また、.NET の BigInteger
は愚直計算による実装で遅かったので Burnikel-Ziegler 法での実装での PR を出しました。
この記事の説明は Burnikel と Ziegler の論文 Fast Recursive Division の説明に基づきますが、変数名は変更しています。
導入
ここで
また、下記のような表記を導入します。
-
と書いたときは[A_3, A_2, A_1] の桁数A がn の倍数であり、下位3 桁をn/3 、その次のA_0 桁をn/3 、上位A_1 桁をn/3 とする。A_2 -
と書いたときは[A_2, A_1] の桁数A がn の倍数であり、下位2 桁をn/2 、上位A_0 桁をn/2 とする。A_1
という具合です。
桁が小さいとき・桁の差が小さいときの除算(愚直な計算)
ひとまず
論文の RecursiveDivision
関数では
2n 桁 / n 桁の除算
そうでなければ、
-
桁 /3n 桁の除算により2n となる[A_3,A_2,A_1] = Q_1 B + S を求める。Q_1, S -
桁 /3n 桁の除算により2n となる[S_1,S_0,A_0] = Q_0 B + R を求める。Q_0, R
このようにすると 2 回の
2n 桁 / n 桁の除算の図解
A/B を考える
| A_3 | A_2 | A_1 | A_0 | / | B_1 | B_0 |
Aは以下の和で表される
| Q_1 B | |
| | S_1 | S_0 | A_0 |
=
| Q_1 B | |
| | Q_0 B |
| | | R_1 | R_0 |
3n 桁 / 2n 桁の除算
以下、
- 商の概算
を求める\widehat{Q}
-
ならばA_2 \lt B_1 (\widehat{Q} = [A_2, A_1]/B_1 桁 /2n 桁の除算)n -
ならばA_2 \ge B_1 \widehat{Q} = \beta^n - 1 -
なのだからA \lt B \beta^n にはならない気がするA_2 \gt B_1
-
また、
- あまりの概算
を求める\widehat{R}
まず
を導出します。
すると
として、あまりの概算が求められます。
- 実際の商とあまりの導出
// 擬似コード
// 実際には配列で保持されている
R_hat = S * pow(β, n) + A_0 - D;
while(R_hat < 0)
{
R_hat += B;
Q_hat++;
}
というようなロジックを記述して、
- 補足
実際の値は配列で保持しているため、値は符号なしの非負整数として扱いたいです。そのため、「
実際には下記のようにするのが良いでしょう。
// 擬似コード
// 実際には配列で保持されている
R_hat = S * pow(β, n) + A_0;
while(R_hat < D)
{
R_hat += B;
Q_hat++;
}
R_hat -= D;
3n 桁 / 2n 桁の除算の図解
A/B を考える
| A_2 | A_1 | A_0 | / | B_1 | B_0 |
Aは以下の和で表される
| Q B_1 | |
| | Q B_2 |
| | R |
[A_2, A_1]/B_1 を考える
| A_2 | A_1 | / | B_1 |
[A_2, A_1] は以下の和
| Q_hat B_1 |
| | S |
Q_hat, S を用いて A を表す
| Q_hat B_1 | |
| | S | A_0 |
Q_hat, R_hat が Q, R と同じ形をみたすように R_hat を定義したい。R_hat が負になる可能性は一旦無視する。
| Q_hat B_1 | |
| | Q_hat B_2 |
| | R_hat |
以下の方程式がたてられる
| S | A_0 |
=
| Q_hat B_2 |
| R_hat |
R_hat について解くと
| S | A_0 |
| -Q_hat B_2 |
2n 桁 / n 桁の除算の実践
-
14926421 / 7894 - 上半分の計算:
149264 / 7894 -
→1492 / 78 \widehat{Q}=19, S=10 \widehat{R} = 1064 - 19 \times 94 = 1064 - 1786 = -722 \widehat{Q} = \widehat{Q}-1, \widehat{R} += 7894 Q = 18, R=7172
-
- 下半分の計算:
717221 / 7894 -
→7172 / 78 \widehat{Q}=91, S=74 \widehat{R} = 7421 - 91 \times 94 = 7421 - 8554 = -1133 \widehat{Q} = \widehat{Q}-1, \widehat{R} += 7894 Q = 90, R=6761
-
- 上半分の計算:
Q=1890, R=6761
任意桁の除算
-
を正規化するA, B
同様に
※各変数の解説
Burnikel-Ziegler 法では除数の桁数を半分ずつに分割していくので、桁数の素因数に
除数の桁数が
- 24 桁で除算
- 分割して 12 桁で除算
- 分割して 6 桁で除算
- 分割して 3 桁で除算: 奇数なので/
を下回るので愚直計算DIV\_LIMIT
- 26 桁で除算
- 分割して 13 桁で除算: 奇数なので愚直計算
- 28 桁で除算
- 分割して 14 桁で除算
- 分割して 7 桁で除算: 奇数なので愚直計算
- 32 桁で除算
- 分割して 16 桁で除算
- 分割して 8 桁で除算
- 分割して 4 桁で除算:
を下回るので愚直計算DIV\_LIMIT
と桁数が
つまり
下記の表を見ると、
除数の桁数 | 愚直計算に移行する桁数 |
---|---|
-
を分割A
以下のような
-
ならばA \lt \dfrac{\beta^{n}}{2} としますt=2 - そうでなければ、
をみたす最小の整数A \lt \dfrac{\beta^{l n}}{2} についてl としますt=l
- 計算する
上位の桁から順にあまりを求めていきます。
// 擬似コード
// 実際には配列で保持されている
Z[t-2] = [A[t-1], A[t-2]];
Q[t-2] = Z[t-2] / B;
R[t-2] = Z[t-2] % B;
for(int i = t-3; i>=0; i--)
{
Z[i] = [R[i+1], A[i]];
Q[i] = Z[i] / B;
R[i] = Z[i] % B;
}
A/B を考える
| A_{t-1} | A_{t-2} | A_{t-3} | ... | A_0 | / | B |
A を複数の和で表すと下記のようになる
| A_{t-1} | A_{t-2} | A_{t-3} | ... | A_0 |
=
| B Q_{t-2} | |
| | R_{t-2} | A_{t-3} | ... | A_0 |
=
| B Q_{t-2} | |
| | B Q_{t-3} |
| | R_1 | A_0 |
=
| B Q_{t-2} | |
| | B Q_{t-3} |
| | B Q_0 |
| | R_0 |
求める商は
ただし、
任意桁の除算の実践
任意桁除算を
57543907443 / 532 -
の桁数を補正:B A=575439074430, B=5320 -
を分割:A 最上位の桁数がA=[0000, 5754, 3907, 4430] と同じにならないようにすることに注意。B -
を計算[0000, 5754] / 5320 - 上半分の計算:
000057 / 5320 -
→0000 / 53 \widehat{Q}=0, S=0 \widehat{R} = 0057 - 0 \times 20 = 57 - 0 = 57 Q = 0, R=57
-
- 下半分の計算:
005754 / 5320 -
→0057 / 53 \widehat{Q}=1, S=4 \widehat{R} = 0454 - 1 \times 20 = 454 - 20 = 434 Q = 1, R=434
-
Q_2 = [00, 01] = 1, R_2 = 434
- 上半分の計算:
-
を計算[434, 3907] / 5320 - 上半分の計算:
043439 / 5320 -
→0434 / 53 \widehat{Q}=8, S=10 \widehat{R} = 1039 - 8 \times 20 = 1039 - 160 = 879 Q = 8, R=879
-
- 下半分の計算:
087907 / 5320 -
→0879 / 53 \widehat{Q}=16, S=31 \widehat{R} = 3107 - 16 \times 20 = 3107 - 320 = 2787 Q = 16, R=2787
-
Q_1 = [08, 16] = 816, R_1 = 2787
- 上半分の計算:
-
を計算[2787, 4430] / 5320 - 上半分の計算:
278744 / 5320 -
→2787 / 53 \widehat{Q}=52, S=31 \widehat{R} = 3144 - 52 \times 20 = 3144 - 1040 = 2104 Q = 52, R=2104
-
- 下半分の計算:
210430 / 5320 -
→2104 / 53 \widehat{Q}=39, S=37 \widehat{R} = 3730 - 39 \times 20 = 3730 - 780 = 2950 Q = 39, R=2950
-
Q_0 = [52, 39] = 5239, R_0 = 2950
- 上半分の計算:
-
Q=[Q_2, Q_1, Q_0] = [1,0816,5239]=108165239, R=R_0=2950 -
の補正を外す:R Q=108165239, R=295
Discussion