剰余演算

剰余演算（モジュロとも呼ぶ）は、コンピュータにおいて、ある数値を別の数値(法と呼ばれることもある)で除算し、余りを取得する演算である。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回引いた場合に残りがなくなる)からである。一般的な電卓を使用して除算を行う場合、商が小数点表記で出力されるため、剰余演算は直接行えないことに注意する。 通常の場合、a と n はともに整数で処理されるが、多くのコンピュータシステムでは他の数値型でも処理が可能である。整数 n の剰余の取りうる範囲は、0から n - 1 までである。「n mod 1」 の場合常に0となる。「n mod 0」 の場合は未定義であり、プログラミング言語によっては「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方向へ向かって直近の整数となる。 ドナルド・クヌースは「切り下げ除算」について言及した。これは商を床関数 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はユークリッド除法の手法での定義について言及している。この場合、余りは非負数(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 = s g n ( n ) ⌊ a | n | ⌋ {\displaystyle q=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に近い側」となる。 Daan Leijenはこう記している。 Bouteはユークリッド除法が数学的に一般的で有用なために他の方法よりも優れていることを示した。しかし、クヌースの示した切り下げ除算もまたよい定義である。幅広く使われているにもかかわらず、「0への切り落とし除算」は他の定義よりも劣っているのである。 —Daan Leijen、Division and Modulus for Computer Scientists 被除数の符号に剰余の結果が依存する場合、意外な失敗を引き起こすことがある。 例えば、ある整数が奇数であるかチェックしたい場合、下記のC++での例のように、2 で除算した余りが 1 であるかどうかを確かめればよいようにみえる。 bool is_odd(int n) { return n % 2 == 1; } しかし、使用するプログラミング言語が、剰余の符号を被除数に依存させている場合、これは正しくない。なぜなら、n が負の奇数の場合、n % 2 は -1 となるため、この関数はfalseを返す。 正しい実装のひとつは、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() 機能を実装し、mod(a, n) のように表記する。剰余演算子として "%"、"mod"、"Mod"などをサポートするプログラミング言語もあり、 a % n または a mod n と表記する。 また、mod()機能がない環境であっても、下記のように算出できる(「int()」は小数点以下を切り捨てた値を生成する)。 a - (n * int(a/n)) 剰余演算は、除算を行い余りを取得する実装となるため、その分の処理時間を必要とする。特殊な場合においては、いくつかのハードウェア上でより高速な計算方法が存在する。たとえば、2のべき乗の剰余を処理する場合、下記のようにビット単位AND演算を使用することができる。 x % 2n == x & (2n - 1) 以下に例を示す(xは正の整数とする)。 x % 2 == x & 1 x % 4 == x & 3 x % 8 == x & 7 剰余演算よりもビット演算の方が効率的に処理できるデバイスやソフトウェアでは、この変換によってより高速に計算することができる。 最適化された コンパイラには、2のべき乗による剰余演算を検出し、自動的にAND演算に変換するものもある。これによって、プログラマは性能を犠牲にすることなく、読みやすいソースコードを記述することができる。ただし、AND演算による方法の場合、出力は常に正の数となるため、C言語のように剰余演算の結果の符号が被除数によって規定される言語では同様に動作しない。したがって、被除数が負の数となる場合は特別な注意が必要である。 他の数学的演算と同様に、剰余演算についてもいくつかの演算を導出、もしくは拡張することができる。そうすることで、ディフィー・ヘルマン鍵交換のような暗号学分野の証明が容易となるだろう。 同一性: ( a mod n ) mod n = a mod n {\displaystyle (a\,{\bmod {\,}}n)\,{\bmod {\,}}n=a\,{\bmod {\,}}n} n x mod n = 0 {\displaystyle n^{x}\,{\bmod {\,}}n=0} 正の整数 x {\displaystyle x} の場合。 n {\displaystyle n} が素数であり、かつ b {\displaystyle b} の約数でない場合、フェルマーの小定理より a b n − 1 mod n = a mod n {\displaystyle ab^{n-1}\,{\bmod {\,}}n=a\,{\bmod {\,}}n} となる。 逆数: ( ( − a mod n ) + ( a mod n ) ) mod n = 0 {\displaystyle ((-a\,{\bmod {\,}}n)+(a\,{\bmod {\,}}n))\,{\bmod {\,}}n=0} b − 1 mod n {\displaystyle b^{-1}\,{\bmod {\,}}n} はモジュラ逆数を表す。これは b {\displaystyle b} と n {\displaystyle n} が互いに素である場合にのみ、以下の数式にて定義される。 ( ( b − 1 mod n ) ( b mod n ) ) mod n = 1 {\displaystyle ((b^{-1}\,{\bmod {\,}}n)\,(b\,{\bmod {\,}}n))\,{\bmod {\,}}n=1} 分配則: ( a + b ) mod n = ( ( a mod n ) + ( b mod n ) ) mod n {\displaystyle (a+b)\,{\bmod {\,}}n=((a\,{\bmod {\,}}n)+(b\,{\bmod {\,}}n))\,{\bmod {\,}}n} a b mod n = ( ( a mod n ) ( b mod n ) ) mod n {\displaystyle ab\,{\bmod {\,}}n=((a\,{\bmod {\,}}n)\,(b\,{\bmod {\,}}n))\,{\bmod {\,}}n} 分数(定義): a b mod n = ( ( a mod n ) ( b − 1 mod n ) ) mod n {\displaystyle {\frac {a}{b}}\,{\bmod {\,}}n=((a\,{\bmod {\,}}n)(b^{-1}\,{\bmod {\,}}n))\,{\bmod {\,}}n} 右辺が定義できる場合。そうでない場合は未定義。 逆数の乗算: ( ( a b mod n ) ( b − 1 mod n ) ) mod n = a mod n {\displaystyle ((ab\,{\bmod {\,}}n)\,(b^{-1}\,{\bmod {\,}}n))\,{\bmod {\,}}n=a\,{\bmod {\,}}n} Modulo 曖昧さ回避ページ 冪剰余 ^ Perlでは剰余の算術演算子はマシン依存となる。例示とその例外についてはPerl documentationを参照。 ^ 右項は正の数でなければならない。左項は定義されていない。 ^ ACUCOBOL、Micro Focus COBOLなどの実装。 ^ “MSDN 剰余演算子 (%)”. マイクロソフト. 2015年12月9日閲覧。 ^ “ASCII.jpデジタル用語辞典 モジュロ”. http://ascii.jp/.+2015年12月9日閲覧。 ^ ISO/IEC 14882:2003 : Programming languages -- C++. 5.6.4: ISO, IEC. (2003年) . "二項演算子 % 左項を右項で割った余りを算出する。.... オペランドが共に負数でない場合は余りも負数ではない。しかし、そうでない場合の剰余の符号は実装によって定義される。" ^ open-std.org, section 6.5.5 ^ CoffeeScript operators ^ “Expressions”. D Programming Language 2.0. Digital Mars. 2010年7月29日閲覧。 ^ “Mod()”. PureBasic. Fantaisie Software. 2015年12月9日閲覧。 ^ a b r6rs.org ^ ISO/IEC 9899:1990 : Programming languages -- C. 7.5.6.4: ISO, IEC. (1990年) . "fmod関数は、yが0でない場合、iが整数となるx - i * yの結果を返す。結果はxと同じ符号となり、yよりも小さな絶対値をとる。" ^ Knuth, Donald. E. (1972). The Art of Computer Programming. Addison-Wesley.  ^ Boute, Raymond T. (1992年4月). “The Euclidean definition of the functions div and mod”. ACM Transactions on Programming Languages and Systems (TOPLAS) (ACM Press (New York, NY, USA)) 14 (2): 127–144. doi:10.1145/128861.128862. http://portal.acm.org/citation.cfm?id=128862&coll=portal&dl=ACM.  ^ Leijen, Daan (2001年12月3日). “Division and Modulus for Computer Scientists (PDF)”. 2014年12月25日閲覧。 ^ Horvath, Adam (2012年7月5日). “Faster division and modulo operation - the power of two”. 2015年12月9日閲覧。