# [Faster remainders when the divisor is a constant: beating compilers and libdivide](https://lemire.me/blog/2019/02/08/faster-remainders-when-the-divisor-is-a-constant-beating-compilers-and-libdivide/) 重點整理

## 除數為 2 的冪
$\dfrac{n}{d}=n\cdot\dfrac{2^N}{d}\cdot\dfrac{1}{2^N}$，當 $d$ 是 2 的冪時就可以用 shift 方式加速

## 如何不透過除法求得餘數
除法可以寫成 $n = q * d + r$，也能寫成 $\dfrac{n}{d} = q + \dfrac{r}{d}$，而商就是 $\dfrac{n}{d}$ 的整數部份，餘數則是小數部份乘上除數

### 23/4

例如:$23/4 = 23*0.25 = 5.75$，$0.75*4 = 3$ 為餘數，假設我們有 fixed-point convention，$\dfrac{1}{d}$ 有 5 bits 表示整數，3 bits 表示小數，被除數 $23=00010111_b$ 與除數 $4=00000100_b$ 皆保持標準 8 bits 整數，而 $\dfrac{1}{d}=00000.010$ ，被除數乘上 $\dfrac{1}{d}$ 則為 $00010111*00000010=00101110$，$q=00101_b=5$，$f*d=00000.110*00000100=00011.000=3=r$，

如果要檢驗是否可被 $4$ 整除，就可以看小數部份是否為 $0$

### 23/6
如果是除以 $6=0.001010..._b$ 呢？考慮一個 8 bits 的近似倒數 $c$，二進位表示式都是小數部份，$0.00101011$ 近似 $6$，同樣是拿被除數 $23$ 作除法運算，$00010111*0.00101011=11.11011101$， $q=11_b=3$，$f*d=0.11011101*00000110=101.00101110$，右移 8 bits 得到 $r=101=5$，若要檢驗是否可被 $6$ 整除，以 $n=42=101010$ 舉例，$n*c=101010*0.00101011=111.00001110$，$f=0.00001110<c=0.00101011$，表示可以被整除

## 理論整理

$N$ 有幾個 bits 用來表示被除數，$F$ 有幾個 bits 用來表示小數，因此求商可以表示成 $(c*n)\ div\ 2^F$，餘數 $(((c*n)mod\ 2^F)*d)\ div \ 2^F$

以 $63$ 除以 $6$ 舉例，近似 $\dfrac{1}{6}$ 的 $c$ 是 $[2^8/6=00101011_b]$




$F=N+L$，定義 $L$ 讓 $c=[2^F/d]=[2^{N+L}/d]$，使得正確計算餘數 $r=(((c*n)mod\ 2^F)*d)\ div \ 2^F$

==小數部份== $(((c*n)mod\ 2^F)=10010101$ 與==倒數乘上餘數部份== $c*(n\ mod\ d)=c*r=00101011*11=10000001$ 是接近的

### Lemma


當 $c$ 越接近 $2^{N+L}/d$ 時，$((c*n)mod\ 2^{N+L})$ 越接近 $c*(n\ mod\ d)$，因此 $((c*n)mod\ 2^{N+L})$ 乘上 $d/2^{N+L}$ 就能計算出 $n\ mod\ d$ ($c*d\approx2^F=2^{N+L}$)


### Theorem



uint32_t d = ...; // your divisor > 0
// c = ceil ( (1 << 64) / d ) ; we take L = N
uint64_t c = UINT64_C (0 x FFFFFFFF FFFFFFFF ) / d + 1;
// fastmod computes ( n mod d ) given precomputed c
uint32_t fastmod ( uint32_t n /* , uint64_t c , uint32_t d */ ) {
    uint64_t lowbits = c * n ;
    return (( __uint128_t ) lowbits * d ) >> 64;
}