# Faster Remainder by Direct Computation Applications to Compilers and Software Libraries 讀後筆記

[Faster Remainder by Direct Computation
Applications to Compilers and Software Libraries](https://arxiv.org/pdf/1902.01961.pdf)

## 3. COMPUTING THE REMAINDER DIRECTLY
藉由 $\left( \left(c*n\right)mod\ 2^{N+L}\right)$ 近似於 $\left( c*\left(n\ mod\ d\right)\right)\ when\ c\ is\ close\ to\ \dfrac{2^{N+L}}{d}$
對前者乘以 $d$ 再除以 $2^{N+L}$ 可以得到 $\left(n\ mod\ d\right)$。

#### Lemma 1
* Lemma 1 在證明 $\left( \left(c*n\right)mod\ 2^{N+L}\right)$ 的確近似於 $\left( c*\left(n\ mod\ d\right)\right)\ when\ c\ is\ close\ to\ \dfrac{2^{N+L}}{d}$
* Lemma 1 的前提假設 $2^{N+L} \leq c*d \leq 2^{N+L}+2^{L}$
可以參照 [第三題的延伸問題那篇的 4. Unsigned Division 開頭有詳細解說 ](https://gmplib.org/~tege/divcnst-pldi94.pdf)
* 對於 1/d ，為了找到合理的近似值 c/(2^(N+L)) (文章中是 m/(2^(N+L))) ，設定兩種情形找出 m*d 的範圍。
* 以下 n 都設定在條件範圍內
* 當 n=d，為了 4.1 成立，需要 1 <= m\*d/(2^(N+L))，推得 2^(N+L) <= m\*d
* 當 n=q\*d-1，注意那個 "-1" ，一般來說 n=q\*d+r，r >= 0，而這邊特地設成這樣就代表當 n=q\*d-1 帶入式子中，必然會得到 < q 的結果，也就是說帶入後可得到 q > m\*(q\*d-1)/(2^(N+L))，接著各乘上 d，得到 d\*q\*(2^(N+L)) > m\*d\*(q\*d-1)，調整一下左邊 (2\^(N+L))\*(q\*d-1)+2\^(N+L) > m\*d\*(q\*d-1)，最後得到 (m\*d-2\^(N+L))*(q\*d-1) < 2\^(N+L)
* 為了 4.1 成立，需要上面那條式子，而那條式子成立需要 m\*d-2\^(N+L) <= 2\^L
* 湊出 $c*r\ +\ 2^{L}q$ 的形式是為了能夠利用下方這條定義
* $if\ \ p-kQ\ \in\ [\ 0\ ,\ y\ )\ \ for\ \ some\ \ y\ \leq\ Q\ ,\ then\ \ p\ \ mod\ \ Q\ =\ p-kQ\ .$

#### Theorem 1
* Theorem 1 在證明 $\left(\left(c*n\right)\ mod\ 2^{N+L}\ *\ d\right)\ div\ 2^{N+L}$ 的確會等於 remainder $r$
* 在 Lemma 1 中已經得知 $\left( \left(c*n\right)mod\ 2^{N+L}\right)$ 的範圍落在 $[\ c*r\ ,\ c*r+2^{L}q\ ]$
接下來利用 $2^{N+L}\ \leq\ c*d\ \leq\ 2^{N+L}+2^{L}$ 推導證明
$if\ \ y\ \in\ [\ c*r\ ,\ c*r+2^{L}q\ ]\ ,\ then\ d*y\ \in\ [\ 2^{N+L}r\ ,\ 2^{N+L}(r+1)\ )$ .
$d*y\ \in\ [\ 2^{N+L}r\ ,\ 2^{N+L}(r+1)\ )\ \ can\ \ be\ \ represented\ \ by\ \ \dfrac{d*y}{2^{N+L}}\ \in\ [\ r\ ,\ r+1\ )$
* Theorem 1 底下有這條式子 $\Bigl\lceil 2^{N+L}/\ {d} \Bigr\rceil\ *\ d=\ 2^{N+L}+d-\left(2^{N+L}\ mod\ d\right)$
因為 $\Bigl\lceil 2^{N+L}/\ {d} \Bigr\rceil\ *\ d\ =\ \left(\dfrac{2^{N+L}-2^{N+L}\ mod\ d}{d}\ +\ 1\right)\ *\ d\ ,\ when\ d\ is\ not\ a\ power\ of\ 2.$

為何可以 pick $F\ \geq\ N+\log_2{(d)}$ ?
因為已知 $d\ \leq\ \left(2^{N+L}mod\ d\right)\ +\ 2^{L}$，而 $\left(2^{N+L}mod\ d\right)$ 的值介於 0 ~ (d-1)，要使該不等式恆成立需要 $d\ \leq\ 2^{L}$。
已知 $F\ =\ N+L$，對 $d\ \leq\ 2^{L}$ 以底數為 2 取 log 可得 $\log_2\left(d\right)\ \leq\ L$ ，將左右各加上 $N$ 可得到 $N+\log_2\left(d\right)\ \leq\ N+L=F$ 因此可以確定 $F\ \geq\ N+\log_2{(d)}$ 成立。

雖然這個取值的方法可行，但是得到的 $L$ 卻不一定是最小值，若要找到最小的 $L$ 則需回到 $d\ \leq\ \left(2^{N+L}mod\ d\right)\ +\ 2^{L}$ 找到符合最小值的 $L$。
(然而 $L$ 取最小並不一定是最好，如果為了找最小的 $L$ 而浪費太多時間反而得不償失。)
(為了便利性甚至可以直接取 $L=N$。)

#### Algorithm 2
* line 5: 當 $d\ \ is\ \ a\ \ power\ \ of\ \ two$ 可以不用走 $\left(\left(c*n\right)\ mod\ 2^{N+L}\ *\ d\right)\ div\ 2^{N+L}$ 的形式，將 $F=\log_2(d)\ ,\ c=1$ 讓式子回歸成一般的 $n\ mod\ d$ 就好。
* line 7: 依據 $d\ \leq\ \left(2^{N+L}mod\ d\right)\ +\ 2^{L}$ 找出最小的 $L$。

### 3.1 Directly Computing Signed Remainders

* 更改除數的正負號，quotient 會變，remainder 不變。
* 更改被除數的正負號，quotien 會變，remainder 會變。

### 3.2 Fast Divisibility Check with a Single Multiplication

#### Proposition 1.
* 一**奇數**除數 $d$ ，可以找到唯一的倒數 $\overline{d}$ 定義為 $d*\overline{d}\ \ mod\ \ 2^{N}\ =\ 1$

* 當存在一無號整數 $n$ 可被 $d$ 整除，假如要運算 $n\ /\ d$ 的結果，可以利用 $\overline{d}$ 做快速除法，變成只需要一個 multiplication 及一個 modulo reduction to a power of two。
* $n\ =\ a*d$
* $n\ \ div\ \ d\ =\ n*\overline{d}\ \ mod\ \ 2^{N}\ =\ a*d*\overline{d}\ \ mod\ \ 2^{N}\ =\ a*(d*\overline{d})\ \ mod\ \ 2^{N}\ =\ a\ \ mod\ \ 2^{N}\ =\ a$
* 若要運算的是 $n\ / \ (2^{K}d)$ 且 $n$ 可被 $2^{K}d$ 整除
* $n\ \ div\ \ (2^{K}d)\ =\ (n\ \ div\ \ 2^{K})*\overline{d}\ \ mod\ \ 2^{N}$

* 上述的快速除法也可作用於快速檢查一無號整數是否被 $d$ 整除。

* 根據 Lemma 1. ，當 $d$ 可以整除 $n$ ，也就是 $n\ \ mod\ \ d\ =\ 0$，等價於 $(c*n)\ mod\ 2^{N+L}\ \lt\ c$。

## 4.1 SOFTWARE IMPLEMENTATION

* Fig. 5 Unsigned divisibility test ，關於 $n * c\ <=\ c - 1$ :
* 其實就是從 $(c*n)\ mod\ 2^{N+L}\ \lt\ c$ 來的
* $n$ 為 32-bit unsigned int，$c$ 為 64-bit unsigned int，所以可以知道 $N\ =\ 32\ ,\ L\ =\ 32\ ,\ F\ =\ 64$ ，因此 $n*c$ 的結果會剛好被切分一半，分成高位的整數部份與低位小數部份，執行 $n*c$ 若不做 right-shift 只會得到低位的小數部份，而這恰好對應到 $(c*n)\ mod\ 2^{N+L}$。
* 為何不用 $\lt\ c$ 而是 $\lt= c-1$ ?
* 因為 Lemma 1. 中 $c$ 並不會出現 $0$ ，所以 $(c*n)\ mod\ 2^{N+L}\ \lt\ c$ 並不能正確判斷當 $c\ =\ 0$ 的情形。但是在實作中，當 $d\ =\ 1$ 時 $c$ 會超出變數可儲存的長度限制而得到 $0$ 。
* 實作中當 $c$ 是 $0$ 的情形，也就是 $d\ =\ 1$ ，對於所有的 $n\ \in\ [\ 0\ ,\ 2^{N}\ )$ 都會是整除，因此為了讓判斷式能正常運作就將 $\lt\ c$ 改成 $\lt=\ c-1$ ，讓判斷式能保有原先的功能，同時又能讓 $c\ =\ 0$ 的情形也能被正確判斷。( unsigned 比大小， 0 為 0000...0000 ， -1 為 1111...1111)

###### tags: `讀後筆記` `sysprog2020` `進階電腦系統理論與實作`