Struct nekolib::math::const_div::ConstDiv2

pub struct ConstDiv2 { /* private fields */ }

定数除算。

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

Barrett reduction に基づく。$a\lt n^2$ に対して、$\lfloor a/n\rfloor$ と $a\bmod n$ を求めることができる。ちゃんと考察すれば、この制約は除ける。 実際、コンパイラは同様の最適化を行う。

example::div2:
        mov     rax, rdi
        shr     rax
        ret

example::div3:
        mov     rax, rdi
        movabs  rcx, -6148914691236517205
        mul     rcx
        mov     rax, rdx
        shr     rax
        ret

example::div63:
        movabs  rcx, 292805461487453201
        mov     rax, rdi
        mul     rcx
        sub     rdi, rdx
        shr     rdi
        lea     rax, [rdi + rdx]
        shr     rax, 5
        ret

example::div64:
        mov     rax, rdi
        shr     rax, 6
        ret

example::div65:
        mov     rax, rdi
        movabs  rcx, 1135184250689818561
        mul     rcx
        mov     rax, rdx
        shr     rax, 2
        ret

fn div63(rdi: u64) -> u64 {
    let rdx = ((rdi as u128 * 0x410410410410411_u128) >> 64) as u64;
    (((rdi - rdx) >> 1) + rdx) >> 5
}

fn div64(rdi: u64) -> u64 { rdi >> 6 }

fn div65(rdi: u64) -> u64 {
    ((rdi as u128 * 0xFC0FC0FC0FC0FC1_u128) >> 66) as u64
}

for i in 0..=100000 {
    assert_eq!(div63(i), i / 63);
    assert_eq!(div64(i), i / 64);
    assert_eq!(div65(i), i / 65);
}

$$ \begin{aligned} \lfloor n/63\rfloor &= (((n-m)\gg 1) + m)\gg 5\text{, where } m=(n\cdot\lceil 2^{64}/63\rceil)\gg 64 \\ \lfloor n/64\rfloor &= n\gg 6 \\ \lfloor n/65\rfloor &= (n\cdot\lceil 2^{66}/65\rceil)\gg 66 \end{aligned} $$

剰余算については、$n\bmod d = n-\lfloor n/d\rfloor\cdot d$ に基づく。 $d$ を掛ける際には定数乗算の最適化（加減算とシフトを用いるなど）を行っていそう。

Naming

除数の 2 乗未満の入力を仮定することから 2 をつけている。

References

• https://rsk0315.hatenablog.com/entry/2021/01/18/065720#Barrett-reduction-%E3%81%AE%E8%A9%B1
• https://godbolt.org/z/snq4nvTP6

Implementations

impl ConstDiv2

pub fn new(n: u64) -> Self

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

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

Trait Implementations

impl Clone for ConstDiv2

fn clone(&self) -> ConstDiv2

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for ConstDiv2

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

Formats the value using the given formatter.

impl PartialEq<ConstDiv2> for ConstDiv2

fn eq(&self, other: &ConstDiv2) -> 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 ConstDiv2

impl Eq for ConstDiv2

impl StructuralEq for ConstDiv2

impl StructuralPartialEq for ConstDiv2