模除
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/2/22/Divmod.svg/langzh-250px-Divmod.svg.png)
模除(又稱模數、取模操作、取模運算等,英語:modulo 有時也稱作 modulus)得到的是一個數除以另一個數的餘數。
給定兩個正整數:被除數 和除數 ,a modulo n (縮寫為 )得到的是使用歐幾里德除法時 的餘數。 舉個例子:計算表達式 "" 得到 1,因為 (5 除以 2 商 2 餘1);而 "" 得到 0,因為 ;注意:如果使用計算器做除法,不能整除時,你不會得到商,而是會得到一個小數,如:。
雖然通常情況下 和 都是整數,但許多計算系統允許其他類型的數字操作,如:對浮點數取模。一個整數對 取模的結果範圍為: 0 到 ( 恆等於 0; 則是未定義的,在程式語言里可能會導致除零錯誤)。 有關概念在數論中的應用請參閱模算數。
當 或 為負數時,通常的定義就不適用了,不同的程式語言對結果有不同的處理。
定義與餘數的計算
程式語言 | 操作符 | 結果與...同符號 |
---|---|---|
AutoLISP | (rem d n) [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 匯編 | 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:)
|
被除數 |
在數學中,取模運算的結果就是歐幾里德除法的餘數。當然也有許多其他的定義方式。計算機和計算器有許多種表示和儲存數字的方法,因此在不同的硬件環境下、不同的程式語言中,取模運算有着不同的定義。
幾乎所有的計算系統中, 除 得到商 和餘數 均滿足以下式子:
然而這樣做,當餘數非 0 時,餘數的符號仍然是有歧義的:餘數非 0 時,它的符號有兩種選擇,一個正、一個負。[註 2] 通常情況下,在數論中總是使用正餘數。但在程式語言中,餘數的符號取決於程式語言的類型和被除數 a 或除數 的符號。 標準 Pascal 和 ALGOL 68 總是使用 0 或正餘數;另一些程式語言,如 C90 ,當被除數 和除數 都是負數時,C90 標準並沒有做具體的規定,而是留給編譯器去定義並實現[6]。 在大多數系統上 時未定義的,雖然有些系統定義它就等於 。更多詳情參見表格。
- 很多取模的實現都使用了截斷除法,此時商由截斷函數定義定義 ,因此由等式 1 有,餘數和被除數符號一致。商向零取整:結果等於普通除法所得的小數靠近 0 方向的第一個整數。
- Raymond T. Boute[8]使用的歐幾里得定義中,餘數總是非負的 ,這與歐幾里得算法是一致的。
在這種情況下:
或者等價的:
這裏的 是符號函數,因此
常見錯誤
當取模的結果與被除數符號相同時,可能會導致意想不到的錯誤。
舉個例子:如果需要判斷一個整數是否為奇數,有人可能會測試這個數除 2 的餘數是否為 1:
bool is_odd(int n) {
return n % 2 == 1;
}
但在一個取模結果與被除數符號相同的程式語言里,這樣做是錯的。因為當被除數 n 是奇數且為負數時, 得到 −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' 事實上等價於截斷函數,進行了向 0 取整)
a - (n * int(a/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 到 取模則可判斷一個數是否為質數。
- 進制之間的轉換。
- 用於求取最大公約數的輾轉相除法使用取模運算。
- 密碼學中的應用:從古老的凱撒密碼到現代常用的RSA、橢圓曲線密碼,它們的實現過程均使用了取模運算。
參見
腳註
參考文獻
- ^ 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) (英語).