定数除算を乗算とシフトでやるやつ

正整数 $D$ を固定したとき、色々な非負整数 $A$ に対して $\lfloor \tfrac{A}{D} \rfloor$ を求めたい。 $M, S$ を非負整数として $(A * M) >> S$ という形の演算で求めることを考える。シフトで切り捨てが入るので、 $M = \lceil \tfrac{2 ^ S}{D} \rceil$ と切り上げにするのがよさそう。誤差を考える。 $2 ^ S = Q \times D - R$ （ $Q, R$ は非負整数、 $R < D$ ）とすると、 $(A * M) >> S = \lfloor A \cdot \tfrac{2 ^ S + R}{D} \cdot \tfrac{1}{2^S} \rfloor = \lfloor \tfrac{A}{D} + \tfrac{A}{D} \cdot \tfrac{R}{2 ^ S} \rfloor$ 。 $\lfloor \tfrac{A}{D} \rfloor$ より小さくなることはないとわかる。 $A$ も求める値も整数なので、（床関数の中身が） $\tfrac{1}{D}$ 未満だけ大きくなる誤差は許容される（正しい値が求まる）。つまり、 $A < \tfrac{2 ^ S}{R}$ であればよい（ $R = 0$ のケースはシフトだけでいいので省略）。計算結果が $1$ だけ大きくなることを許容する場合、 $A < \tfrac{(D + 1) \cdot 2 ^ S}{R}$ であればよい。例えば乗算に _mm_mullo_epi32 を使う場合、扱えるのは $2 ^ {32}$ 未満の非負整数なので、 $A \times M < 2 ^ {32}$ という条件も加わる。 $S$ を全探索して、正しい値が計算できる $A$ の範囲が広いものを使う（範囲は例えば $6$ 万以下とかになるが、 $D$ の値によって違ってくる）。
（さすがに読みづらかったのでtex記法使ったけどクソ時間かかった）