64bit乗算剰余演算向け除算処理 素案

64bit乗算剰余は除数が奇数であればこの方法（Barrett Reductionの亜種）よりも、モンゴメリ乗算を用いたほうが（モンゴメリ乗算の方が乗算回数が少ないため）適切だと思いますが一応。
2024/04/29 7頁目～10頁目 除数63.5bit、除数23.5bit、除数64bit、除数32bit 版の実装案を追記。

Transcript

1. 高速化チャレンジ問題 (for C, C++, Rust, Assembler, etc.): 非負整数 が与えられる。 を で除算した 商 と 余り をそれぞれ求めて答えよ。 制約: 実行時間制限: 2秒 64bit乗算剰余演算向け除算処理 素案 Mizar/みざー <http://github.com/mizar> 1
2. 非負整数 が与えられる。 を で除算した 商 と 余り をそれぞれ求めて答えよ。 素直に C++ (gcc) で実装すると、 128bit ÷ 64bit の除算は __udivmodti4 , __udivti3 , __umodti3 など (128bit整数除算を行うコンパイラ組み込み関数) が用いられる。 除数 で 繰り返し 割り算するという処理の性質を用いて、それらの関数以上にどう高速化 できるかがポイント。 https://godbolt.org/z/c4xboP1s9 AtCoder Library では 除数32bit までを想定した Barrett Reduction の実装がある、これを 若干変形して考える。 https://github.com/atcoder/ac-library/blob/master/atcoder/internal_math.hpp#L22-L61 64bit乗算剰余演算向け除算処理 素案 Mizar/みざー <http://github.com/mizar> 2
3. 非負整数 が与えられる。 を で除算した 商 と 余り をそれぞれ求めて答えよ。 方針: 非負整数 を用いて を と近似し、 の近似値を で求める。 ( : Multiplier Value / Magic Number, : Shift Count) 以下のいずれかを満たす の最小値 (もしくは ) を使い、 とする。 の場合 の場合 64bit乗算剰余演算向け除算処理 素案 Mizar/みざー <http://github.com/mizar> 3
4. :被除数、 :除数、 :商、 :剰余、 :乗定数、 :論理右シフト数 の場合 の場合 64bit乗算剰余演算向け除算処理 素案 Mizar/みざー <http://github.com/mizar> 4
5. 非負整数 が与えられる。 を で除算した 商 と 余り をそれぞれ求めて答えよ。 が 64bit整数に収まらないケースの補足: もしくは、 を満たす、 非負整数 が となる組しかない場合: とすると であるから 64bit乗算剰余演算向け除算処理 素案 Mizar/みざー <http://github.com/mizar> 5
6. 関連する問題 yukicoder No.2440 Accuracy of Integer Division Approximate Functions https://yukicoder.me/problems/no/2440 個のクエリが与えられる。 番目のクエリ では、整数 が与えられる。 かつ となるような 整数 がいくつあるかを数え上げ、 とお く。この整数 を答えよ。 実行時間制限: 2秒 入力はすべて整数 64bit乗算剰余演算向け除算処理 素案 Mizar/みざー <http://github.com/mizar> 6
7. 除数63.5bit版 除数 , 被除数 の前提条件 除数 に対応する定数 の求め方 定数 を用いた の求め方 ※ の時は、前提より であるため、同様の式にて成り立つ。 64bit乗算剰余演算向け除算処理 素案 Mizar/みざー <http://github.com/mizar> 7
8. 除数31.5bit版 除数 , 被除数 の前提条件 除数 に対応する定数 の求め方 定数 を用いた の求め方 ※ の時は、前提より であるため、同様の式にて成り立つ。 64bit乗算剰余演算向け除算処理 素案 Mizar/みざー <http://github.com/mizar> 8
9. 除数64bit版 除数 , 被除数 の前提条件 除数 に対応する定数 の求め方 定数 を用いた の求め方 ※ の時は、前提より であるため、同様の式にて成り立つ。 64bit乗算剰余演算向け除算処理 素案 Mizar/みざー <http://github.com/mizar> 9
10. 除数32bit版 除数 , 被除数 の前提条件 除数 に対応する定数 の求め方 定数 を用いた の求め方 ※ の時は、前提より であるため、同様の式にて成り立つ。 64bit乗算剰余演算向け除算処理 素案 Mizar/みざー <http://github.com/mizar> 10