檢視模除的原始碼

'''模除'''（又安到'''模數'''、'''取模操作'''、'''取模運算'''等，英語：modulo 有時乜安到 modulus）得著个係一個數除以另外一個數个餘數。

分定兩隻正整數：被除數 $ a $ 摎除數 $ n $，_ a _ modulo _ n _ ( 縮寫為 $ a { \ bmod { n } } $ ) 得著个係用歐幾里德除法个時節 $ { \ frac { a } { n } } $ 个餘數。
舉一個例仔：計算表達式 " $ 五 { \ bmod { 二 } } $ " 得著一，因為 $ 五 \ div 二=二 \ ldots 一 $（五除以二商二餘一）； 還過 " $ 九 { \ bmod { 三 } } $ " 得著零，因為 $ 九 \ div 三=三 \ ldots 零 $；注意哦：係講用計算器做除法，做毋得清忒个時節，你毋會得著商，係會得著一個小數，像係：$ 五 \ div 二=二 .五 $。

雖然一般情況下 $ a $ 摎 $ n $ 係整數，毋過當多計算系統允准其他類型个數字操作，像係：對浮點數取模。一隻整數對 $ n $ 取模个結果範圍係：零到 $ n 重點一千八百空二 $（$a { \ bmod { 一 } } $ 恆等於零；$ a { \ bmod { 零 } } $ 係吂有定義个，在程式語言里可能會造成除零錯誤）。
有關概念在數論當中个應用請參閱模算數。

當 $ a $ 摎 $n $ 都係負數个時節，一般个定義就毋適用了，無共樣个程式語言對結果有無共樣个處理。

==定義摎其他部分个算==

在數學當中，取模運算个結果就係歐幾里德除法个餘數。當然也有異多其他个定義方式。 計算機摎計算器有異多種表示摎儲存數字个方法，故所在無共樣个硬體環境下、無共樣个程式語言當中，取模運算有無共樣个定義。

做得講所有个計算系統當中，$ n $ 除 $ a $ 得著商 $ q $ 摎餘數 $ r $ 都滿足用下式子：


: :

毋過恁呢做，係講零點恁久，餘數个符號仍然係有歧義个：伸个時節毋係零點，厥仔符號有兩種選擇，一個正、一個負。一般情況下，在數論中總係使用个正數。毋過在程式語言當中，餘數个符號就愛看程式語言个類型摎被除數 _ a _ 抑係除數 $ n $ 个符號。
標準 Pascal 摎 ALGOL 六十八總係使用零抑係正部分；有兜程式語言， 像係 C 九十，除數 $ a $ 摎除數 $ n $ 都係負數个時節，C 九十標準並無做具體个規定，係留分編譯器去定義還過實現。
在大多數系統頂高 $ a { \ bmod { 零 } } $ 未定義个啊，雖然有兜系統定義佢就等於 $ a $。還較多詳細情形參見表格。

* 當多取模个實現都使用了 _ 截斷除法 _，這時商由截斷函數定義定義 $ q=\ mathrm { trunc } \ left ( { \ frac { a } { n } } \ right ) $，故所由等式'''一'''有，餘數 _ 同被除數共樣 _。商量摎零取整：結果等於普通除法所得个小數偎兼零方向个頭一個整數。


: $r=a-n \ operatorname { trunc } \ left ( { \ frac { a } { n } } \ right ) $

* 高德納定義个 _ 取底除法 _ 个商由取底函數定義：$ q=[{ \ frac { a } { n } }] $。故所由等式'''一'''有，餘數 _ 摎除數共樣个一致 _。因為使用了取底个函數，商總係跌下來整理，就算商已經係負數。


: $ r=a-n \ left [{ \ frac { a } { n } } \ right] $

* Raymond T . Boute 使用个歐幾里得定義當中，餘數總係非負个 $ 零 \ leq r $，這同歐幾里愛算法係共樣个。

在這種情形下：


: $ n > 零 \ Rightarrow q=\ left [{ \ frac { a } { n } } \ right] $


: $ n < 零 \ Rightarrow q=- \ left [- { \ frac { a } { n } } \ right] $

抑係講等價个：


: $ q=\ operatorname { sgn } ( n ) \ left [{ \ frac { a } { \ left | n \ right | } }\ right] $

這片个 $ \ mathrm { sgn } $ 係符號函數，故所


: $ r=a- | n | \ left [{ \ frac { a } { \ left | n \ right | } } \ right] $

* Common Lisp 也定義了自家个捨入除法摎進位除法，商分別定義為 $ q=\ mathrm { round } \ left ( { \ frac { a } { n } } \ right )$ 摎 $ q=- \ left [{ \ frac { -a } { n } } \ right] $。
* IEEE 七百五十四定義了一個取余函數，生理被定義為 $ { \ frac { a } { n } } $，依據盼得入約定取整。所以餘數个符號選定為 _ 最接近零 _。



==常見个錯誤==

當取模个結果摎被除數符號共樣个時節，可能造成意想都無个毋著。

舉一個例仔：假使需要判斷一隻整數係毋係奇數，有人可能會試這數除忒二次多數係毋係一：

但係在一隻取模結果摎被除數符號共樣个程式語言里，恁呢做係毋著个。因為當被除數 _ n _ 這係選數个時節，$ n { \ bmod { 二 } } $得著 − 一，這時函數返回「假」。

一種正確个試取模結果係毋係，因為餘數係零點無符號个問題：

或者考慮餘數个符號，有兩種情形：餘數可能係一隻抑講重點一千八百空二。

==記號==

一兜計算器有取模 mod ( ) 按鈕，當多程式語言也有相像个函數，一般像 mod ( _ a _ , _ n _ ) 恁呢。
有兜語言也支持在表達式內使用 " % "、" mod " 抑係 " Mod " 來做為取模抑係取余操作符。


: ` a  % n `

抑係


: ` a mod n `

抑算在一息無 mod ( ) 函數个環境當中使用這兜價數个：
（ 注意哦'int'事實上等價到截斷函數 $ { \ frac { a } { n } } $，進行了向零取整）


: ` a - ( n * int ( a / n ) ) `

==等價性==

一兜取模操作，經過分解摎展開做得等於其他數學運算。這在密碼學个證明當中蓋有用，比將講：迪菲 - 赫爾曼密鎖匙交換。

* 恆等式：
* $ ( a { \ bmod { n } } ) { \ bmod { n } }=a { \ bmod { n } }$
* 對所有个正數 $ x $ 有：$ n ^ { x } { \ bmod { n } }=零 $
* 係講 $ p $ 係一個質數，還做毋得 $ b $ 个因數，這時由費馬細定理有：$ ab ^ { p 重點一千八百空二 }{ \ bmod { p } }=a { \ bmod { p } } $
* 逆運算：
* $ [( -a { \ bmod { n } } ) + ( a { \ bmod { n } } )]={ \ bmod { n } }=零 $ .* $ b ^ { 重點一千八百空二 } { \ bmod { n } } $ 就講模反元素。係講唯一 $ b $ 摎 $ n $ 互質時，等式个左片个有定義：$ [( b ^ { 重點一千八百空二 } { \ bmod { n } } ) ( b { \ bmod { n} } )] { \ bmod { n } }=一 $。
* 分配律：
* $ ( a + b ) { \ bmod { n } }=[( a { \ bmod { n } } ) + ( b { \ bmod { n } } )] { \ bmod {n } } $
* $ ab { \ bmod { n } }=[( a { \ bmod { n } } ) ( b { \ bmod { n } } )] { \ bmod { n } } $
* $ d { \ bmod { ( } } abc )=(d { \ bmod { a } } ) + a [( d \ backslash a { \ bmod { b } } )] + ab [( d \ backslash a \ backslash b ) { \ bmod { c } }] $，符合號 \ 係歐幾里德除法當中个除法操作符，運算結果係商
* $ c { \ bmod { ( } } a + b )=( c { \ bmod { a } } ) + [bc \ backslash ( a + b )] { \ bmod{ b } } - [bc \ backslash ( a + b )] { \ bmod { a } } $ .
* 除法定義：正當式个子右片有定義个時節，就係 $ b $、$ n $ 互質時有：$ { \ frac { a } { b }} { \ bmod { n } }=[( a { \ bmod { n } } ) ( b ^ { 重點一千八百空二 } { \ bmod { n } } )] { \ bmod { n } } $，其他情況係無定義个。
* 乘法逆元：$ [( ab { \ bmod { n } } ) ( b ^ { 重點一千八百空二 } { \ bmod { n } } )] { \ bmod { n } }=a { \ bmod { n } } $ .

==性能問題==

做得通過依次計算帶餘數个除法實現取模操作。特殊情況下，像係有兜硬體項，存在還較遽个實現。
比將講：二个 n 次冪个模，做得通過逐位摎運算實現：


: ` x  % 二 n==x & ( 二 n - 一 ) `

例仔，假定 _ x _ 為正數：


: ` x  % 二==x & 一 `


: ` x  % 四==x & 三 `


: ` x  % 八==x & 七 `

在進行位操作比取模操作效率還較高个設備抑係軟體環境當中，以上形式个取模運算速度還較遽。

編譯器做得自動識別出對二个 n 次冪取模个表達式，自動摎佢優化為 ` expression & ( constant 重點一千八百空二 ) `。恁樣做得在兼顧效率个情況下寫出更加整潔个代碼。這個優化在取模結果摎被除數符號共樣个語言當中（包含 C 語言）做毋得用，除非被除數係無符號整數。這係因為係講分人除數係負數，也係負數，毋過 ` expression & ( constant 重點一千八百空二 ) ` 總係正數，進行恁樣个優化就會引起毋著，無符號整數無這個問題。

==用途==

* 取模運算可以用於判斷一個數係毋係能夠另外一個數整除。 第二名就做得判斷整數个奇偶性；對二到 $ n 重點一千八百空二 $ 取模係毋係做得判斷一隻數係毋係質數。
* 進制之間个轉換。
* 用來求最大公約數个輾轉除法使用取模運算。
* 密碼學中个應該用：對古老个凱撒密碼到現代輒常用个 RSA、橢圓曲線密碼，佢兜个實現過程都用了取模運算。

==參見==

* 模 ( 消歧義 ) 摎模 ( 術語 )——「模數（Modulo）」 這隻詞蓋多用法，都係一八零一年卡爾 ・ 弗里德里希 ・ 高斯引入模算數个時節產生个。
* 模冪運算
* 同餘

==腳註==

==參考文獻==

[[分類: 待校正]]