Struct nekolib::math::const_div::ConstDiv

pub struct ConstDiv { /* private fields */ }

定数除算。

除算命令は重いので、加減算や乗算で置き換えることを考える。 同じ値で何度も除算する際には、あらかじめ置き換える値を先に求めておくことで高速化できる。

以下、$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.

Implementations

impl ConstDiv

pub fn new(n: u64) -> Self

pub fn quot(&self, n: u64) -> u64

pub fn rem(&self, n: u64) -> u64

Trait Implementations

impl Clone for ConstDiv

fn clone(&self) -> ConstDiv

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for ConstDiv

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl PartialEq<ConstDiv> for ConstDiv

fn eq(&self, other: &ConstDiv) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl Copy for ConstDiv

impl Eq for ConstDiv

impl StructuralEq for ConstDiv

impl StructuralPartialEq for ConstDiv