天天看點

數學與程式設計——求餘、取模運算及其性質

一、求餘運算(Remainder)

(參考維基百科: http://zh.wikipedia.org/wiki/餘數  http://en.wikipedia.org/wiki/Remainder http://en.wikipedia.org/wiki/Euclidean_division http://zh.wikipedia.org/wiki/同餘)

Euclidean division:Given two integers a and b, with b ≠ 0, there exist unique integers q and r such that a = bq + r and 0 ≤ r < |b|, where |b| denotes the absolute value of b.

(術語:  a 被除數 dividend ; b 除數 divisor;q 商 quotient;r 餘數 remainder)

按照上面的定義:餘數唯一并始終大于或等于0,并可以拓展到兩個整數為正數或負數的情況。

但是,程式設計語言求餘算法并不是按照上面的定義來執行。

我們引出另一種餘數定義:a = bq + r and 0 <= |r| < |b| 。于是,我們可以發現這種情況下餘數可能不止一個。

例子:a = 43 b = 5時:

43 = 5 * 8 + 3 : q = 8;r = 3 (r > 0)

43 = 5 * 9 -  2 : q = 9;r = -2 (r < 0)

當a 和 b 含有負數時也存在這兩種餘數。

例子:a = 43 b = -5時:

43 = -5 * -8 + 3 : q = -8;r = 3 (r > 0)

43 = -5 * -9 -  2 : q = -9;r = -2 (r < 0) 

大多數程式設計語言要求餘數與被除數的正負号相同(參考自《C陷阱與缺陷》,強調了程式的可移植性問題,即被除數或除數含有負數時要謹慎對待)。這說明不同程式設計語言實作時對上述例子求餘時可能是上面不同的解。

二、取模運算 (Modulo)

(參考維基百科:http://en.wikipedia.org/wiki/Modulo_operation  http://en.wikipedia.org/wiki/Modular_arithmetic)

In computing, the modulo operation finds the remainder after division of one number by another (sometimes called modulus).

上面這句話說明,取模運算和求餘運算的目标都是一緻的。隻是不同程式設計語言時實作的方式可能不同,也就是上面所說的采用另一種餘數定義時,含有兩種餘數結果。一些語言可能會采取第一個結果;另一些語言可能會采取第二個結果;還有些語言可能會把取模和求餘分開定義,分别采取兩種結果。維基百科裡面就列出了一些程式設計語言采取的操作,常見的為以下幾種:

1.求餘結果或取模結果的正負号與被除數相同;

2.求餘結果或取模結果的正負号與除數相同;

3.求餘結果或取模結果的總是正數;

4.求餘結果或取模結果由實作定義;

5.求餘結果或取模結果為最接近0的數;

求餘運算和取模運算小結:有人會把取模運算和求餘運算分開解釋,又采用特定的語言去舉例,我認為這兩種運算目标都是一緻,隻是求餘運算傾向于數學,而取模運算傾向于計算機科學,之是以不同語言會有不同的結果,本質是因為根據求餘運算定義導緻餘數不唯一時不同程式設計語言采用了不同的結果,但他們都會根據某種依據來給出唯一的結果。這也告訴我們,程式移植時必須當心這種差别,特别是當兩個整數含有負數的情況。

三、取模運算性質

術語:

For a positive integer n, two integers a and b are said to be congruent modulo n, and written as

數學與程式設計——求餘、取模運算及其性質

一些有用的性質(可證明):

數學與程式設計——求餘、取模運算及其性質

如果a≡b(mod m),x≡y(mod m),則a+x≡b+y(mod m)。

如果a≡b(mod m),x≡y(mod m),則ax≡by(mod m)。

如果ac≡bc(mod m),且c和m互質,則a≡b(mod m) (就是說同餘式兩邊可以同時除以一個和模數互質的數)。

繼續閱讀