| 模除 | 您所在的位置：网站首页 › 新安一高严不严 › 模除 |
模除
 建議将餘數併入此條目或章節。（討論）
 商數 (q) 和 餘數 (r) 作為被除數 (a) 的函數時的圖像。左侧是除数为正的情况，右侧除数为负。从上至下分别使用了：向零取整、向下取整和欧几里德除法。
模除（又稱模数、取模操作、取模運算等，英語：modulo 有时也称作 modulus）得到的是一个数除以另一个数的余数。 给定两个正整数：被除数 a 和除数 n，a modulo n (缩写为 a mod n)得到的是使用欧几里德除法时 a/n 的余数。 举个例子：计算表达式 "5 mod 2" 得到 1，因为 5÷2=2...1（5 除以 2 商 2 餘1）；而 "9 mod 3" 得到 0，因为 9÷3=3...0；注意：如果使用计算器做除法，不能整除时，你不会得到商，而是会得到一个小数，如：5÷2=2.5。 虽然通常情况下 a 和 n 都是整数，但许多计算系统允许其他类型的数字操作，如：对浮点数取模。一个整数对 n 取模的结果范围为： 0 到 n − 1（a mod 1 恒等于 0；a mod 0 则是未定义的，在编程语言里可能会导致除零错误）。 有关概念在数论中的应用请参阅模算數。 当 a 和 n 均为负数时，通常的定义就不适用了，不同的编程语言对结果有不同的处理。 目录 1 定義与余数的计算 2 常见错误 3 记号 4 等价性 5 性能问题 6 用途 7 參見 8 脚注 9 参考文献 定義与余数的计算[编辑] 不同程式語言下整数取模运算的符号 程式語言 操作符 结果与...同符号 AutoLISP (rem d n)[1] 被除数[註 1] AWK % 被除数 BASIC Mod 未定义 C (ISO 1999) %, div 被除数[2] C++ (ISO 2011) %, div 被除数 C# % 被除数 Clojure mod 除数 rem 被除数 CoffeeScript % 被除数 %% 除数[3] Dart % 非负 remainder() 被除数 Erlang rem 被除数 F# % 被除数 Fortran mod 被除数 modulo 除数 Go % 被除数 Haskell mod 除数 rem 被除数 Julia %, mod, rem 除数 Kotlin % 被除数 Java % 被除数 Math.floorMod 除数 JavaScript % 被除数 Lua 5 % 除数 Mathematica Mod[a, b] 除数 MATLAB mod 除数 rem 被除数 Pascal (ISO-7185 and -10206) mod 非负 Perl % 除数 PHP % 被除数 Prolog (ISO 1995[4]) mod 除数 rem 被除数 Python % 除数 math.fmod 被除数 Racket remainder 被除数 R语言 %% 除数 Ruby %, modulo() 除数 remainder() 被除数 Rust % 被除数 Scala % 被除数 Scheme R6RS[5] mod 非负 mod0 最靠近0的数[5] SQL (SQL:2012) % 被除数 Swift % 被除数 Verilog (2001) % 被除数 VHDL mod 除数 rem 被除数 Visual Basic Mod 被除数 WebAssembly i32.rem_s, i64.rem_s 被除数 x86 汇编（英语：x86 assembly language） IDIV 被除数 不同程式語言下浮点数取模运算的符号 程式語言 操作符 结果与...同符号 C (ISO 1999) fmod 被除数 remainder 最靠近0的数 C++ (ISO 2011) std::fmod 被除数 std::remainder 最靠近0的数 C# % 被除数 Common Lisp mod 除数 rem 被除数 Dart % 非负 remainder() 被除数 F# % 被除数 Fortran mod 被除数 modulo 除数 Go math.Mod 被除数 Haskell (GHC) Data.Fixed.mod' 除数 Java % 被除数 JavaScript % 被除数 Perl6 % 除数 PHP fmod 被除数 Python % 除数 math.fmod 被除数 Ruby %, modulo() 除数 remainder() 被除数 Scheme R6RS flmod 非负 flmod0 最靠近0的数 Swift truncatingRemainder(dividingBy:) 被除数在数学中，取模运算的结果就是欧几里德除法的余数。当然也有许多其他的定义方式。计算机和计算器有许多种表示和储存数字的方法，因此在不同的硬件环境下、不同的编程语言中，取模运算有着不同的定义。 几乎所有的计算系统中，n 除 a 得到商 q 和余数 r 均满足以下式子： q ∈ Z a = n q + r | r | ( a n ) {\displaystyle r=a-n\operatorname {trunc} \left({\frac {a}{n}}\right)} 高德纳[7]定义的取底除法的商由取底函数定义：q = [a/n]。 因此由等式 1 有，余数和除数符号一致。因为使用了取底函数，商总是向下取整，即使商已经是负数。 r = a − n [ a n ] {\displaystyle r=a-n\left[{\frac {a}{n}}\right]} Raymond T. Boute[8]使用的欧几里得定义中，余数总是非负的 0 ≤ r，这与欧几里得算法是一致的。在这种情况下： n > 0 ⇒ q = [ a n ] {\displaystyle n>0\Rightarrow q=\left[{\frac {a}{n}}\right]} n [ − a n ] {\displaystyle n | n | [ a | n | ] {\displaystyle r=a-|n|\left[{\frac {a}{\left|n\right|}}\right]} Common Lisp 也定义了自己的舍入除法和进位除法，商分别定义为 q = round(a/n) 和 q = -[-a/n]。IEEE 754（英语：IEEE 754-1985） 定义了一个取余函数，商被定义为 a/n，依据舍入约定（英语：IEEE 754-1985#Rounding floating-point numbers）取整。因此余数的符号选定为最接近0。 常见错误[编辑]当取模的结果与被除数符号相同时，可能会导致意想不到的错误。 举个例子：如果需要判断一个整数是否为奇数，有人可能会测试这个数除 2 的余数是否为 1： bool is_odd(int n) { return n % 2 == 1; }但在一个取模结果与被除数符号相同的编程语言里，这样做是错的。因为当被除数 n 是奇数且为负数时， n mod 2 得到 −1，此时函数返回“假”。 一种正确的实现是测试取模结果是否为 0，因为余数为 0 时没有符号的问题： bool is_odd(int n) { return n % 2 != 0; }或者考虑余数的符号，有两种情况：余数可能为 1 或 -1。 bool is_odd(int n) { return n % 2 == 1 || n % 2 == -1; } 记号[编辑]一些计算器有取模 mod() 按钮，很多编程语言里也有类似的函数，通常像 mod(a, n) 这样。 有些语言也支持在表达式内使用 "%"、"mod" 或 "Mod" 作为取模或取余操作符。 a % n或 a mod n或者在一些没有 mod() 函数的环境中使用等价的： （注意 'int' 事实上等价于截断函数a/n，进行了向 0 取整） a - (n * int(a/n)) 等价性[编辑]一些取模操作，经过分解和展开可以等同于其他数学运算。这在密码学的证明中十分有用，例如：迪菲-赫爾曼密鑰交換。 恒等式： (a mod n) mod n = a mod n 对所有的正数 x 有：nx mod n = 0 如果 p 是一个质数，且不为 b 的因数，此时由费马小定理有：abp−1 mod p = a mod p 逆运算： [(−a mod n) + (a mod n)] mod n = 0. b−1 mod n 表示模反元素。当且仅当 b 与 n 互质时，等式左侧有定义：[(b−1 mod n)(b mod n)] mod n = 1。 分配律： (a + b) mod n = [(a mod n) + (b mod n)] mod n ab mod n = [(a mod n)(b mod n)] mod n d mod (abc) = (d mod a) + a[(d \ a) mod b] + ab[(d \ a \ b) mod c]，符号 \ 是欧几里德除法中的除法操作符，运算结果为商 c mod (a+b) = (c mod a) + [bc \ (a+b)] mod b - [bc \ (a + b)] mod a. 除法定义：仅当式子右侧有定义时，即 b、n 互质时有：a/b mod n = [(a mod n)(b−1 mod n)] mod n，其他情况为未定义的。 乘法逆元：[(ab mod n)(b−1 mod n)] mod n = a mod n. 性能问题[编辑]可以通过依次计算带余数的除法实现取模操作。特殊情况下，如某些硬件上，存在更快的实现。 例如：2 的 n 次幂的模，可以通过逐位与运算实现： x % 2n == x & (2n - 1)例子，假定 x 为正数： x % 2 == x & 1 x % 4 == x & 3 x % 8 == x & 7在进行位操作比取模操作效率更高的设备或软件环境中，以上形式的取模运算速度更快。[9] 编译器可以自动识别出对 2 的 n 次幂取模的表达式，自动将其优化为 expression & (constant-1)。这样可以在兼顾效率的情况下写出更整洁的代码。这个优化在取模结果与被除数符号一致的语言中（包括 C 语言）不能使用，除非被除数是无符号整数。这是因为如果被除数是负数，则结果也是负数，但 expression & (constant-1) 总是正数，进行这样的优化就会导致错误，无符号整数则没有这个问题。 用途[编辑] 取模运算可用于判断一个数是否能被另一个数整除。对 2 取模即可判断整数的奇偶性；从 2 到 n-1 取模则可判断一个数是否为质数。 進制之間的轉換。 用于求取最大公约数的輾轉相除法使用取模运算。 密码学中的应用：从古老的凯撒密码到现代常用的RSA、椭圆曲线密码，它们的实现过程均使用了取模运算。 參見[编辑] 模 (消歧义)和模 (术语)（英语：modulo (jargon)） —— “模数（Modulo）”这个词的许多用法，都是 1801 年卡爾·弗里德里希·高斯引入模算數时产生的。 模幂运算 同餘 脚注[编辑] ^ 在 Visual LISP IDE 里测试可知结果与被除数同符号。 (rem 13 3)=>1; (rem -13 3)=>-1; (rem 13 -3)=>1; (rem -13 -3)=>-1 ^ 从数学上讲，正和负只是满足不等式的无穷多个解中的两个 参考文献[编辑] ^ AutoCAD 2018 帮助: rem (AutoLISP). Autodesk, Inc. [2018-07-12] （中文）. ^ ISO/IEC JTC. The ISO C99 Standard (ISO/IEC 9899:TC3 Committee Draft) (PDF). open-std.org: 6.5.5: 94. 2007-09-07 [2018-07-12]. （原始内容 (pdf)存档于2018-06-24） （英语）. If the quotient a/b is representable, the expression (a/b)*b + a%b shall equal a. ^ jashkenas. CoffeeScript Language Reference - Operators and Aliases. coffeescript.org. [2018-07-12]. （原始内容存档于2018-07-11） （英语）. % works just like in JavaScript, while %% provides “dividend dependent modulo” ^ J.P.E. Hodgson. Prolog: The ISO directives, control constructs and builtins.. 1999-04-12 [2018-07-12]. （原始内容存档于2017-12-25） （英语）. A conforming processor is required to support the arithmetic operations specified by the following tables. They conform to the ISO/IEC 10967-1 Language Independent Arithmetic standard. ^ 5.0 5.1 ROBERT BRUCE FINDLER, JACOB MATTHEWS. Revised6 Report on the Algorithmic Language Scheme. r6rs.org. 2007-09-26 [2018-07-12]. （原始内容存档于2018-03-15） （英语）. ^ Jones, Derek M. The New C Standard: An Economic and Cultural Commentary (PDF). Addison-Wesley. 2003 [2018-07-11]. ISBN 9780201709179. （原始内容 (PDF)存档于2018-07-11） （英语）. ^ Knuth, Donald. E. The Art of Computer Programming. Addison-Wesley. 1972 （英语）. ^ Boute, Raymond T. The Euclidean definition of the functions div and mod. ACM Transactions on Programming Languages and Systems (ACM Press (New York, NY, USA)). April 1992, 14 (2): 127–144. doi:10.1145/128861.128862 （英语）. ^ Horvath, Adam. Faster division and modulo operation - the power of two. July 5, 2012. （原始内容存档于2018-03-05） （英语）. |
高德纳[7]定义的取底除法的商由取底函数定义：q = [a/n]。
![{\displaystyle r=a-n\left[{\frac {a}{n}}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0be02e2b4b3fd15eb8415bc7a03ead062bb6fc28)
Raymond T. Boute[8]使用的欧几里得定义中，余数总是非负的 0 ≤ r，这与欧几里得算法是一致的。
![{\displaystyle n0\Rightarrow q=\left[{\frac {a}{n}}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5794a68643a0faadfb7d047f44fff61522a022e4)
n
[
−
a
n
]
{\displaystyle n
|
n
|
[
a
|
n
|
]
{\displaystyle r=a-|n|\left[{\frac {a}{\left|n\right|}}\right]}
![{\displaystyle r=a-|n|\left[{\frac {a}{\left|n\right|}}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d35b5b335ea296ae334223b404ab073be740b502)
Common Lisp 也定义了自己的舍入除法和进位除法，商分别定义为 q = round(a/n) 和 q = -[-a/n]。IEEE 754（英语：IEEE 754-1985） 定义了一个取余函数，商被定义为 a/n，依据舍入约定（英语：IEEE 754-1985#Rounding floating-point numbers）取整。因此余数的符号选定为最接近0。
常见错误[编辑]
【本文地址】