模除

維基百科,自由的百科全書
  商數 () 和   餘數 () 作為被除數 () 的函數時的圖像。左側是除數為正的情況,右側除數為負。從上至下分別使用了:向零取整、向下取整和歐幾里德除法

模除(又稱模數取模操作取模運算等,英語:modulo 有時也稱作 modulus)得到的是一個數除以另一個數的餘數。

給定兩個正整數:被除數 除數 a modulo n (縮寫為 )得到的是使用歐幾里德除法 的餘數。 舉個例子:計算表達式 "" 得到 1,因為 (5 除以 2 商 2 餘1);而 "" 得到 0,因為 ;注意:如果使用計算器做除法,不能整除時,你不會得到商,而是會得到一個小數,如:

雖然通常情況下 都是整數,但許多計算系統允許其他類型的數字操作,如:對浮點數取模。一個整數對 取模的結果範圍為: 0 到 恆等於 0; 則是未定義的,在程式語言里可能會導致除零錯誤)。 有關概念在數論中的應用請參閱模算數

為負數時,通常的定義就不適用了,不同的程式語言對結果有不同的處理。

定義與餘數的計算[編輯]

不同程式語言下整數取模運算的符號
程式語言 操作符 結果與...同符號
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:) 被除數

在數學中,取模運算的結果就是歐幾里德除法的餘數。當然也有許多其他的定義方式。計算機和計算器有許多種表示和儲存數字的方法,因此在不同的硬件環境下、不同的程式語言中,取模運算有着不同的定義。

幾乎所有的計算系統中, 得到商 和餘數 均滿足以下式子:

 

 

 

 

( 1 )

然而這樣做,當餘數非 0 時,餘數的符號仍然是有歧義的:餘數非 0 時,它的符號有兩種選擇,一個正、一個負。[註 2] 通常情況下,在數論中總是使用正餘數。但在程式語言中,餘數的符號取決於程式語言的類型和被除數 a 或除數 的符號。 標準 PascalALGOL 68 總是使用 0 或正餘數;另一些程式語言,如 C90 ,當被除數 和除數 都是負數時,C90 標準並沒有做具體的規定,而是留給編譯器去定義並實現[6]。 在大多數系統上 時未定義的,雖然有些系統定義它就等於 。更多詳情參見表格。

  • 很多取模的實現都使用了截斷除法,此時商由截斷函數定義定義 ,因此由等式 1 有,餘數和被除數符號一致。商向零取整:結果等於普通除法所得的小數靠近 0 方向的第一個整數。
  • 高德納[7]定義的取底除法的商由取底函數定義:。因此由等式 1 有,餘數和除數符號一致。因為使用了取底函數,商總是向下取整,即使商已經是負數。
  • Raymond T. Boute[8]使用的歐幾里得定義中,餘數總是非負的 ,這與歐幾里得算法是一致的。

在這種情況下:

或者等價的:

這裏的 符號函數,因此

  • Common Lisp 也定義了自己的捨入除法和進位除法,商分別定義為
  • IEEE 754英語IEEE 754-1985 定義了一個取余函數,商被定義為 ,依據捨入約定英語IEEE 754-1985#Rounding floating-point numbers取整。因此餘數的符號選定為最接近0

常見錯誤[編輯]

當取模的結果與被除數符號相同時,可能會導致意想不到的錯誤。

舉個例子:如果需要判斷一個整數是否為奇數,有人可能會測試這個數除 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橢圓曲線密碼,它們的實現過程均使用了取模運算。

參見[編輯]

腳註[編輯]

  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. 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. 
  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) (英語).