剰余演算 - 暇つぶしWikipedia

剰余演算

アルゴリズムの違いによる商(赤線)と余り(緑線)のグラフ

剰余演算（じょうよえんざん、リマインダーまたはモジュロとも呼ぶ）は、ある数値を別の数値で除算し、余りを取得する演算である [1][2]。
概要

2つの正の整数である、被除数 a および除数 n が与えられた場合、a の n による剰余（a modulo n、略して a mod n とも表記される）は、ユークリッド除法における a を n で除算した余りである。例えば、「5 mod 2」の結果は 1 である。5を2で除算した場合、商は2となり、余りは1となるからである。また、「9 mod 3」の結果は 0 である。9を3で除算した商は3となり、余りは0となる（つまり9から3を3回引くと残りがなくなる）からである [3]。

通常の場合、a と n はともに整数であるが、多くのコンピュータシステムでは他の数値型でも処理が可能である。整数 n の剰余の取りうる範囲は、0 から n − 1 までである。「n mod 1」の場合は常に 0 となる。「n mod 0」は未定義であり、プログラミング言語によっては「ゼロ除算」エラーを引き起こす。a または n が負数の場合については、単純な定義はなく、プログラミング言語によってどのように定義されるかが異なっている。

数論における古典的な関連事項については合同算術を参照。
剰余演算による余りの算出

数学的には、剰余演算の結果はユークリッド除法における余りのことである。しかし、別の法則に従って算出されることもある。コンピュータやその他の計算機は数値の保持や処理方法がさまざまなので、剰余演算の定義はプログラミング言語や動作するハードウェアによって、それぞれ規定されている。

ほぼすべてのコンピュータシステムにおいて、a を n で除算した商 q および剰余 r は下記の条件を満たす。 q ∈ Z a = n q + r 。 r 。 < 。 n 。 {\displaystyle {\begin{aligned}q\,&\in \mathbb {Z} \\a\,&=nq+r\\|r|\,&<|n|\end{aligned}}} (1)

ところが、剰余が0でない場合、その符号は不確定なものとなる。数論上は、余りは常に正の数となるが、プログラミング言語によっては a および n の符号によって剰余の符号が正となるか負となるかが定められる。標準的な PascalおよびAlgol68では、除数が負数であっても正の剰余（または0）を出力する。しかし、C90のようなプログラミング言語では、n または a が負の数の場合にはそうならないことがある。詳細は右表を参照。多くのシステムでは a の 0 での剰余は未定義だが、いくつかは a を出力するように定義されている。

多くの実装においては「0への切捨て除算」が使用されている。これは商を0への切捨て関数 q = trunc(a/n) によって処理し、(1)の処理における余りは「被除数と同じ符号」となる。この場合の商は0方向に丸められる。つまり、実数での商から0の方向へ向かって直近の整数となる。

ドナルド・クヌースは「切り下げ除算」について言及した [4]。これは商を床関数 q = ⌊ ( a / n ) ⌋ {\displaystyle q=\lfloor (a/n)\rfloor } によって処理し、(1)の処理における余りは「除数と同じ符号」となる。床関数によって、商が負の数であっても常に負の無限大方向に丸められる。 r = a − n ⌊ a n ⌋ {\displaystyle r=a-n\left\lfloor {\frac {a}{n}}\right\rfloor }

Raymond T. Bouteはユークリッド除法の手法での定義について言及している [5]。この場合、余りは非負数（0 ? r）となる。右表では「常に正」と表記している。この定義は下記のように表すことができる。 n > 0 ⇒ q = ⌊ a n ⌋ {\displaystyle n>0\Rightarrow q=\left\lfloor {\frac {a}{n}}\right\rfloor } n < 0 ⇒ q = ⌈ a n ⌉ {\displaystyle n<0\Rightarrow q=\left\lceil {\frac {a}{n}}\right\rceil }

また、符号関数 sgn を使用すると、下記のようにも表せる。 q = sgn ⁡ ( n ) ⌊ a 。 n 。 ⌋ {\displaystyle q=\operatorname {sgn}(n)\left\lfloor {\frac {a}{\left|n\right|}}\right\rfloor } r = a − 。 n 。 ⌊ a 。 n 。 ⌋ {\displaystyle r=a-|n|\left\lfloor {\frac {a}{\left|n\right|}}\right\rfloor }

Common Lispでは切り下げ除算、切り上げ除算のそれぞれについてq = round(a/n) と q = ceil(a/n) で商が与えられる。

IEEE 754-1985 の剰余は、近接丸め（英語版）を行った場合の商として定義している。したがって、剰余の符号は「0に近い側」となる。

上記はJavaScriptでの実装例だが、これらを用いて商 (quotient) を求め、商から剰余 (remainder) を求めることができる。以下は被除数 (divisor) を ±8、除数 (dividend) を ±3 としたときの計算結果である。

剰余演算のバリエーション関数被除数除数商剰余剰余の符号
truncated_mod8322被除数と同一
-83-2-2
8-3-22
-8-32-2
floored_mod8322除数と同一
-83-31
8-3-3-1
-8-32-2
euclidean_mod8322常に正
-83-31
8-3-22
-8-331
ceiled_mod833-1-
-83-2-2
8-3-22
-8-331
rounded_mod833-10に近い側
-83-31
8-3-3-1
-8-331