模除

维基百科,自由的百科全书
跳到导航 跳到搜索
     商數 (q) 和      余数 (r) 作为被除数 (a) 的函数时的图像。左侧是除数为正的情况,右侧除数为负。从上至下分别使用了:向零取整、向下取整和欧几里德除法

模除(又稱模数取模操作取模運算等,英语:modulo 有时也称作 modulus)得到的是一个数除以另一个数的余数。

给定两个正整数:被除数 a 和除数 na 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。

虽然通常情况下 an 都是整数,但许多计算系统允许其他类型的数字操作,如:对浮点数取模。一个整数对 n 取模的结果范围为: 0 到 n − 1a mod 1 恒等于 0;a mod 0 则是未定义的,在编程语言里可能会导致除零错误)。 有关概念在数论中的应用请参阅模算數

an 均为负数时,通常的定义就不适用了,不同的编程语言对结果有不同的处理。

定義与余数的计算[编辑]

不同程式語言下整数取模运算的符号
程式語言 操作符 结果与...同符号
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 被除数
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:) 被除数

在数学中,取模运算的结果就是欧几里德除法的余数。当然也有许多其它的定义方式。计算机和计算器有许多种表示和储存数字的方法,因此在不同的硬件环境下、不同的编程语言中,取模运算有着不同的定义。

几乎所有的计算系统中,an 得到商 q 和余数 r 均满足以下式子:

 

 

 

 

( 1 )

然而这样做,当余数非 0 时,余数的符号仍然是有歧义的:余数非 0 时,它的符号有两种选择,一个正、一个负。[註 2] 通常情况下,在数论中总是使用正余数。但在编程语言中,余数的符号取决于编程语言的类型和被除数 a 或除数 n 的符号。 标准 PascalALGOL 68 总是使用 0 或正余数;另一些编程语言,如 C90 ,当除数 a 和除数 n 都是负数时,C90 标准并没有做具体的规定,而是留给编译器去定义并实现[6]。 在大多数系统上 a mod 0 时未定义的,虽然有些系统定义它就等于 a。更多详情参见表格。

  • 很多取模的实现都使用了截断除法,此时商由截断函数定义定义 q = trunc(a/n),因此由等式 1 有,余数和被除数符号一致。商向零取整:结果等于普通除法所得的小数靠近 0 方向的第一个整数。
  • 高德纳[7]定义的取底除法的商由取底函数定义:q = ⌊a/n

    因此由等式 1 有,余数和除数符号一致。因为使用了取底函数,商总是向下取整,即使商已经是负数。

  • Raymond T. Boute[8]使用的欧几里得定义中,余数总是非负的 0 ≤ r,这与欧几里得算法是一致的。

    在这种情况下:

    或者等价的:

    这里的 sgn符号函数,因此

  • 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 表示模反元素。当且仅当 bn 互质时,等式左侧有定义:[(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.
  • 除法定义:仅当式子右侧有定义时,即 bn 互质时有: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椭圆曲线密码,它们的实现过程均使用了取模运算。

參見[编辑]

脚注[编辑]

  1. ^ 在 Visual LISP IDE 里测试可知结果与被除数同符号。 (rem 13 3)=>1; (rem -13 3)=>-1; (rem 13 -3)=>1; (rem -13 -3)=>-1
  2. ^ 从数学上讲,正和负只是满足不等式的无穷多个解中的两个

参考文献[编辑]

  1. ^ AutoCAD 2018 帮助: rem (AutoLISP). Autodesk, Inc. [2018-07-12] (中文). 
  2. ^ ISO/IEC JTC. The ISO C99 Standard (ISO/IEC 9899:TC3 Committee Draft) (PDF). open-std.org: 6.5.5: 94. Septermber 7, 2007 [2018-07-12]. (原始内容 (pdf)存档于2018-06-24) (英语). If the quotient a/b is representable, the expression (a/b)*b + a%b shall equal a. 
  3. ^ 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” 
  4. ^ 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. ^ 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) (英语). 
  6. ^ 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) (英语). 
  7. ^ Knuth, Donald. E. The Art of Computer Programming. Addison-Wesley. 1972 (英语). 
  8. ^ 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 (英语). 
  9. ^ Horvath, Adam. Faster division and modulo operation - the power of two. July 5, 2012. (原始内容存档于2018-03-05) (英语).