模运算¶
假设 \(a\) 是被除数（dividend），\(n\) 是除数（divisor），\(q\) 是商（quotient），\(r\) 是余数（remainder），模运算
\[ r = a \bmod n \]
最基本的要求是
\[ \left\{\begin{array}{l} q \in \mathbb{Z} \\ a=nq+r \\ |r|<|n| \end{array}\right. \]
当 \(n=0\) 时，模运算的结果通常是未定义的。
余数的符号¶
尽管有上面的要求，\(r\) 的符号仍然有歧义。余数 \(r\) 的符号与计算商 \(q\) 时使用的取整函数有关。参考：Modulo - Wikipedia
| 取整方式 | 商 | 余数 |
|---|---|---|
truncate，向零取整，只取整数部分 | \(q = \mathrm{truncate} \left(\dfrac{a}{n} \right)\) | 符号与被除数 \(a\) 一致 |
floor，向下取整 | \(q=\left\lfloor \dfrac{a}{n} \right\rfloor\) | 符号与除数 \(n\) 一致 |
ceil，向上取整 | \(q=\left\lceil \dfrac{a}{n} \right\rceil\) | 符号与除数 \(n\) 相反 |
round，银行家舍入 | \(q=\mathrm{round} \left(\dfrac{a}{n} \right)\) | IEEE Remainder，范围 \(\left[ -\dfrac{n}{2},\dfrac{n}{2} \right]\) |
| 欧几里得除法 | \(q=\mathrm{sgn}(n) \left\lfloor \dfrac{a}{\|n\|} \right\rfloor\) | 非负 |
当被除数和除数都是正数时，truncate、floor 和 欧几里得除法 方式的结果一样。
不同实现¶
在 C / C++ / C# / Go / Java 等语言中，% 运算符使用 truncate 方式，在 Python / Lua 5 等语言中 % 使用 floor 方式。
在数学中常用 欧几里得除法 方式
\[ a \bmod n = a - |n| \left\lfloor \dfrac{a}{|n|} \right\rfloor \]
因为它具有良好的数学性质。
性质 1¶
\[ (a \pm b) \bmod p = ((a \bmod p) \pm (b \bmod p)) \bmod p \]
性质 2¶
\[ ab \bmod p = ((a \bmod p)(b \bmod p)) \bmod p \]
性质 3¶
\[ a^b \bmod p = (a \bmod p)^b \bmod p \]
相关文章