Truncated division 和 Euclidean division

之前一直不太理解 rust 语言中原始类型中的数值类型取模运算（mod）和除运算（division）单独提供 rem_euclid 和 div_euclid 的原因。

数学定义：

$${\displaystyle {\begin{aligned}&q,r\in \mathbb {Z} \\&a=nq+r\\&|r|<|n|\end{aligned}}}$$

在编程语言中，实现除运算根据运算取整的时候采用何种策略来区分有五种实现。

• Truncated division

$${\displaystyle q=\left[{\frac {a}{n}}\right]}$$ $${\displaystyle r=a-n\left[{\frac {a}{n}}\right]}$$

• [] 表示 rounding toward zero，向零取整。

• Floored division

$${\displaystyle q=\left\lfloor {\frac {a}{n}}\right\rfloor }$$ $${\displaystyle r=a-n\left\lfloor {\frac {a}{n}}\right\rfloor}$$

• ⌊⌋ 表示 rounding down，向负无穷取整。

• Euclidean division

$${\displaystyle q=\operatorname {sgn}(n)\left\lfloor {\frac {a}{\left|n\right|}}\right\rfloor ={\begin{cases}\left\lfloor {\frac {a}{n}}\right\rfloor &{\text{if }}n>0\\\left\lceil {\frac {a}{n}}\right\rceil &{\text{if }}n<0\\\end{cases}}}$$ $${\displaystyle r=a-|n|\left\lfloor {\frac {a}{\left|n\right|}}\right\rfloor }$$

• sgn 表示符号函数。

• ⌊⌋ 表示 rounding down，向负无穷方向取整。

• ⌈⌉ 表示 rounding up，向正无穷方向取整。

• Rounded division

$${\displaystyle q=\operatorname {round} \left({\frac {a}{n}}\right)}$$ $${\displaystyle r=a-n\operatorname {round} \left({\frac {a}{n}}\right)}$$

• round 表示 rounding half to even，四舍五入取整。

• Ceiled division

$${\displaystyle q=\left\lceil {\frac {a}{n}}\right\rceil }$$ $${\displaystyle r=a-n\left\lceil {\frac {a}{n}}\right\rceil }$$

• ⌈⌉ 表示 rounding up，向正无穷方向取整。

我常用的语言中：

• rust 的 rem 和 div 采用的 Truncated division 实现方案。
• rust 的 rem_euclid 和 div_euclid 采用的 Euclidean division 实现方案。
• javascript 的 rem( % ) 和 div ( / )采用的 Truncated division 实现方案。

Reference

• wiki_modulo