pub struct ConstDiv { /* private fields */ }Expand description
定数除算。
除算命令は重いので、加減算や乗算で置き換えることを考える。 同じ値で何度も除算する際には、あらかじめ置き換える値を先に求めておくことで高速化できる。
以下、$d$ による除算を行うとする。$d = 2^s$ であれば $s$ bit 右シフトするだけなので、$2$ べきではないとする。magic number $M_d$ とシフト幅 $s$ を求めておき、次の式に基づいて計算する。 $$ \lfloor n/d\rfloor = \left\lfloor\frac{M_d\cdot n}{2^s}\right\rfloor. $$ $M_d$ は、ある $0\le r\lt d$ が存在して次の形になる。 $$ M_d = \frac{2^s+r}{d} = 1+\left\lfloor\frac{2^s-1}{d}\right\rfloor. $$
$M_d$ と $s$ が満たすべき性質について考える。$0\le n\lt 2^w$ に対して常に次の式が成り立ってほしい。$w$ はワードサイズで、ここでは $w=64$ とする。 $$ \lfloor n/d\rfloor = \left\lfloor\frac{2^s+r}{d}\cdot\frac{n}{2^s}\right\rfloor = \left\lfloor\frac{n\vphantom{2^s}}{d} + \frac{r\cdot n}{2^s}\right\rfloor. $$
有理数と床関数の性質から、$r\cdot n/2^s \lt 1/d$ が常に成り立てばよい。
このとき、$0\le M_d\lt 2^{w+1}$ をみたす $M_d$ が存在することを示す。
すなわち、$\lfloor M_d/2^w\rfloor\in\{0, 1\}$ となる。todo!()
さて、$M_d$ が見つかったとする。$0\le M_d\lt 2^w$ であれば上の式に基づいて、
直接計算できる。一方で、$2^w\le M_d\lt 2^{w+1}$ の場合はワードサイズに収まらないので、
少々工夫する必要がある。$M_d-2^w$ はワードサイズに収まるので、それを利用する。
todo!()
References
- Warren, Henry S. Hacker’s delight. Pearson Education, 2013.