剰余演算

剰余演算（じょうよえんざん）は、ある数値（被除数、）を別の数値（除数、）で除算し、余り（剰余、）を取得する演算である。モジュロ演算（）とも呼ばれる剰余演算（モジュロ演算 / mod）とは - 意味をわかりやすく - IT用語辞典 e-Words。

英語のは「剰余の」という意味を持つ形容詞のほか、「〜を法として」という意味を持つ副詞・前置詞でもあり、「」は「Nを法として」という意味になるmoduloの意味・使い方・読み方｜英辞郎 on the WEB。ここで「法」とはすなわち除数を意味する。

という単語はカール・フリードリヒ・ガウスが1801年に合同算術の説明で初めて使用したが、その後、さまざまな意味で用いられるようになった。

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

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

数論における古典的な関連事項については合同算術を参照。

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

ほぼすべてのコンピュータシステムにおいて、 を  で除算した商  および剰余  は下記の条件を満たす。


ところが、剰余が0でない場合、その符号は不確定なものとなる。数論上は、余りは常に正の数となるが、プログラミング言語によっては  および  の符号によって剰余の符号が正となるか負となるかが定められる。標準的なPascalおよびAlgol68では、除数が負数であっても正の剰余（または0）を出力する。しかし、C89/C90規格以前のC言語やC++03規格以前のC++など、プログラミング言語によっては  または  が負の数の場合の結果の符号は特に言語仕様で規定されておらず、実装定義（処理系依存）とされていることもある整数に対する除算と剰余算の丸め結果を規定 - cpprefjp C++日本語リファレンス。詳細は後述の表を参照のこと。多くのシステムでは  の 0 での剰余は未定義だが、いくつかは  を出力するように定義されている。

Daan Leijenはこのように記している。

 ありがちなミス 

被除数の符号に剰余の結果が依存する場合、失敗を引き起こす場合がある。

例えば、ある整数が奇数であるかどうかを調べたい場合、下記の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(a, n) のように表記する。剰余演算子として "%"、"mod"、"Mod"などを用意しているプログラミング言語もあり、
a % n
または
a mod n
と表記する。

 剰余算出の代替手段 
mod 関数または演算子が用意されていないか、正しく機能しない環境であっても、下記のように算出できる。ここで、int()は小数点以下を切り捨てた値を生成する。

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

このほか除数 n が2のべき乗である場合に限り、後述のように、除数より1少ない値と論理積を取って算出する方法が有効である。

 ビット演算による効率化 
剰余演算は、除算を行って余りを得る実装となるので、その分の処理時間を必要とする。特殊な場合においては、いくつかのハードウェア上でより高速な計算方法が存在する。

たとえば、数値の内部表現に2進法を用いているコンピュータでは、2のべき乗の剰余を計算する場合に、下記のようにビットごとのAND演算を利用することができる。
x % 2n == x & (2n - 1)

例を示す（x は正の整数とする）。
x % 2 == x & 1
x % 4 == x & 3
x % 8 == x & 7

剰余演算よりもビット演算のほうが効率よく処理できるデバイスやソフトウェアでは、この変換によってより高速に計算することができる。

最適化をするコンパイラには、2のべき乗による剰余演算を検出し、自動的にAND演算に変換するものもある。これによって、プログラマは性能を犠牲にすることなく、読みやすいソースコードを記述することができる。ただし、AND演算による場合、出力は常に正の数となるので、C言語のように剰余演算の結果の符号が被除数によって定まる言語では同じ動作はしない。したがって、被除数が負になる場合は、特別な注意が必要である。

 剰余演算の等価性 
他の数学的演算と同様に、剰余演算についてもいくつかの演算を導出、または拡張することができる。そうすることで、ディフィー・ヘルマン鍵交換のような暗号学分野の証明が容易となるだろう。
 同一性:
 　（冪等）
  正の整数  の場合。
  が素数であって  の約数でない場合、フェルマーの小定理によって  となる。
逆数:

  はモジュラ逆数を表す。これは  と  とが互いに素である場合にだけ、次式で定義される。
 分配則:


 分数（定義）:  右辺が定義できる場合。そうでない場合は未定義。
 逆数の乗算: 


以下の表では「演算子」と総称されているが、実際には演算子ではなく関数（サブルーチン）による実装となっている言語もあることに注意されたい。

+ さまざまなプログラミング言語の整数剰余演算子 言語 演算子 符号 ActionScript  %  被除数と同一 Ada mod  除数と同一 rem  被除数と同一 ASP  Mod  未定義 ALGOL-68  ÷×, mod  常に正   mod  被除数と同一 APL  |  除数と同一 AppleScript  mod  被除数と同一 AWK  %  被除数と同一 BASIC  Mod  未定義 bash  %  被除数と同一 bc  %  被除数と同一 C90 (ISO/IEC 9899:1990) 以前 %  実装による div  被除数と同一 C++03 (ISO/IEC 14882:2003) 以前 %  実装による div  被除数と同一 C99 (ISO/IEC 9899:1999) 以降  %, div  被除数と同一open-std.org, section 6.5.5 C++11 (ISO/IEC 14882:2011) 以降  %, div  被除数と同一 C#  %  被除数と同一   %  被除数と同一 Clojure  mod  除数と同一 COBOL  FUNCTION MOD  除数と同一 CoffeeScript %  被除数と同一 %%  除数と同一CoffeeScript operators ColdFusion  %, MOD  被除数と同一 Common Lisp mod  除数と同一 rem  被除数と同一 D  %  被除数と同一 Dart  %  常に正 remainder()  被除数と同一 Eiffel  \\  被除数と同一 Erlang  rem  被除数と同一 Euphoria mod  除数と同一 remainder  被除数と同一 F#  %  被除数と同一 FileMaker  Mod  除数と同一 Forth  mod  実装による FORTRAN mod  被除数と同一 modulo  除数と同一 Frink  mod  除数と同一  (GML)  mod  被除数と同一 GDScript  %  被除数と同一 Go  %  被除数と同一 Haskell mod  除数と同一 rem  被除数と同一 Haxe  %  被除数と同一 J  |~  除数と同一 Java %  被除数と同一 Math.floorMod  除数と同一 JavaScript  %  被除数と同一 Julia mod  除数と同一 rem  被除数と同一 LibreOffice  =MOD()  除数と同一 Lua 5  %  除数と同一 Lua 4  mod(x,y)  除数と同一   MOD  被除数と同一   mod(x,y)  除数と同一 Maple   e mod m   常に正 Mathematica  Mod  除数と同一 MATLAB mod  除数と同一 rem  被除数と同一 Maxima mod  除数と同一 remainder  被除数と同一   %  被除数と同一 Microsoft Excel  =MOD()  除数と同一 Minitab  MOD  除数と同一 mksh  %  被除数と同一 Modula-2  MOD  除数と同一 MUMPS  #  除数と同一 NASM NASMX  %  符号なし剰余演算子  %%  符号付き剰余演算子 Oberon  MOD  除数と同一 OCaml  mod  被除数と同一 Occam  \  被除数と同一 Pascal (Delphi)  mod  被除数と同一 Pascal (ISO-7185 および ISO-10206)  mod  常に正 Perl  %  除数と同一 PHP  %  被除数と同一 PIC Basic Pro  \\  被除数と同一 PL/I  mod  除数と同一 (ANSI PL/I) PowerShell  %  被除数と同一   modulo  被除数と同一 Prolog (ISO 1995) mod  除数と同一 rem  被除数と同一 PureBasic  %,Mod(Number,Divisor)  被除数と同一 Python %  除数と同一 math.fmod  被除数と同一 Racket  remainder  被除数と同一   MOD  被除数と同一 R  %%  除数と同一 REXX  //  被除数と同一 RPG  %REM  被除数と同一 Ruby  %, modulo()  除数と同一  remainder()  被除数と同一 Rust  %  被除数と同一 Scala  %  被除数と同一 Scheme modulo  除数と同一 remainder  被除数と同一 Scheme R6RS mod  常に正r6rs.org mod0  0に近い側  mod  除数と同一 rem  被除数と同一  modulo  除数と同一 rem  被除数と同一 Smalltalk \\  除数と同一 rem:  被除数と同一 SQL (SQL:1999)  mod(x,y)  被除数と同一 Standard ML mod  除数と同一 Int.rem  被除数と同一 Stata  mod(x,y)  常に正 Swift  %  被除数と同一 Tcl  %  除数と同一   %  被除数と同一 Turing  mod  除数と同一 Verilog (2001)  %  被除数と同一 VHDL mod  除数と同一 rem  被除数と同一 Visual BasicMod被除数と同一   IDIV  被除数と同一   %  被除数と同一 Mod()  除数と同一 Z3 theorem prover  div, mod  常に正

いくつかの言語では浮動小数点数オペランドに対しても剰余演算子が利用できるようになっているが、IEEE 754準拠の剰余ではなく、通例整数オペランドに対する剰余と似た仕様となっている。そのため、IEEE準拠の剰余を求めるライブラリ関数が別途用意されていることも多い。Javaでは、メソッドが用意されている。C#やVB.NETのような.NET言語では、Math.IEEERemainder()メソッドが用意されているMath.IEEERemainder(Double, Double) Method (System) | Microsoft Learn。

+ さまざまなプログラミング言語の浮動小数点数剰余演算子 言語 演算子 符号 C90 (ISO/IEC 9899:1990) 以前  fmod  被除数と同一 C99 (ISO/IEC 9899:1999) 以降 fmod  被除数と同一 remainder  0に近い側 C++03 (ISO/IEC 14882:2003) 以前  std::fmod  被除数と同一 C++11 (ISO/IEC 14882:2011) 以降 std::fmod  被除数と同一 std::remainder  0に近い側 C#  %  被除数と同一 Common Lisp mod  除数と同一 rem  被除数と同一 D  %  被除数と同一 Dart  %  常に正 remainder()  被除数と同一 F#  %  被除数と同一 FORTRAN mod  被除数と同一 modulo  除数と同一 Go  math.Mod  被除数と同一 Haskell (GHC)  Data.Fixed.mod'  除数と同一 Java  %  被除数と同一 JavaScript  %  被除数と同一 Microsoft Excel  =MOD()  除数と同一 OCaml  mod_float  被除数と同一 Perl  POSIX::fmod  被除数と同一 Raku  %  除数と同一 PHP  fmod  被除数と同一 Python %  除数と同一 math.fmod  被除数と同一 REXX  //  被除数と同一 Ruby %, modulo()  除数と同一 remainder()  被除数と同一 Scheme R6RS flmod  常に正 flmod0  0に近い側 Standard ML  Real.rem  被除数と同一 Swift  %  被除数と同一  %  被除数と同一 Mod()  除数と同一

 脚注 

 注釈 

 出典 

 関連項目 
Modulo 曖昧さ回避ページ
冪剰余
巡回群

Category:プログラミング言語の構文
Category:合同算術
Category:二項演算