剰余演算

剰余演算（じょうよえんざん）は、ある数値（被除数、英: dividend）を別の数値（除数、英: divisor）で除算し、余り（剰余、英: remainder）を取得する演算である^[1][2]。モジュロ演算（英: modulo operation / modulus operation）とも呼ばれる^[3]。

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

英語のmoduloは「剰余の」という意味を持つ形容詞のほか、「〜を法として」という意味を持つ副詞・前置詞でもあり、「modulo N」は「Nを法として」という意味になる^[4]。ここで「法」とはdivisorすなわち除数を意味する。

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

概要

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回引くと残りがなくなる）からである^{[注釈 1]}。

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

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

剰余演算による余りの算出

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

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

${\displaystyle {\begin{aligned}q&\in \mathbb {Z} \\a&=nq+r\\|r|&<|n|\end{aligned}}}$

(1)

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

• 多くの実装においては「0への切捨て除算」が使用されている。これは商を0への切捨て関数 q = trunc(a/n) によって処理し、(1)の処理における余りは「被除数と同じ符号」となる。この場合の商は0方向に丸められる。つまり、実数での商から0の方向へ向かって直近の整数となる。
• ドナルド・クヌースは「切り下げ除算」について言及した^[6]。これは商を床関数 ${\displaystyle q=\lfloor (a/n)\rfloor }$ によって処理し、(1)の処理における余りは「除数と同じ符号」となる。床関数によって、商が負の数であっても常に負の無限大方向に丸められる。

  ${\displaystyle r=a-n\left\lfloor {\frac {a}{n}}\right\rfloor }$

• Raymond T. Bouteはユークリッド除法の手法での定義について言及している^[7]。この場合、余りは非負数（0 ≤ r）となる。後述の表では「常に正」と表記している。この定義は下記のように表すことができる。

  ${\displaystyle n>0\Rightarrow q=\left\lfloor {\frac {a}{n}}\right\rfloor }$

  ${\displaystyle n<0\Rightarrow q=\left\lceil {\frac {a}{n}}\right\rceil }$

  また、符号関数 sgn を使用すると、下記のようにも表せる。

  ${\displaystyle q=\operatorname {sgn}(n)\left\lfloor {\frac {a}{\left|n\right|}}\right\rfloor }$

  ${\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^[8]

ありがちなミス

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

例えば、ある整数が奇数であるかどうかを調べたい場合、下記の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 関数または演算子が用意されていないか、正しく機能しない環境^{[注釈 2]}であっても、下記のように算出できる。ここで、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

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

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

剰余演算の等価性

他の数学的演算と同様に、剰余演算についてもいくつかの演算を導出、または拡張することができる。そうすることで、ディフィー・ヘルマン鍵交換のような暗号学分野の証明が容易となるだろう。

• 同一性:
  • ${\displaystyle (a{\bmod {n}}){\bmod {n}}=a{\bmod {n}}}$　（冪等）
  • ${\displaystyle n^{x}{\bmod {n}}=0}$ 正の整数 x の場合。
  • ${\displaystyle n}$ が素数であって b の約数でない場合、フェルマーの小定理によって ${\displaystyle ab^{n-1}{\bmod {n}}=a{\bmod {n}}}$ となる。
• 逆数:
  • ${\displaystyle ((-a{\bmod {n}})+(a{\bmod {n}})){\bmod {n}}=0}$
  • ${\displaystyle b^{-1}{\bmod {n}}}$ はモジュラ逆数を表す。これは b と n とが互いに素である場合にだけ、次式で定義される。${\displaystyle ((b^{-1}{\bmod {n}})(b{\bmod {n}})){\bmod {n}}=1}$
• 分配則:
  • ${\displaystyle (a+b){\bmod {n}}=((a{\bmod {n}})+(b{\bmod {n}})){\bmod {n}}}$
  • ${\displaystyle ab{\bmod {n}}=((a{\bmod {n}})(b{\bmod {n}})){\bmod {n}}}$
• 分数（定義）: ${\displaystyle {\frac {a}{b}}{\bmod {n}}=((a{\bmod {n}})(b^{-1}{\bmod {n}})){\bmod {n}}}$ 右辺が定義できる場合。そうでない場合は未定義。
• 逆数の乗算: ${\displaystyle ((ab{\bmod {n}})(b^{-1}{\bmod {n}})){\bmod {n}}=a{\bmod {n}}}$

各プログラミング言語における仕様

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

さまざまなプログラミング言語の整数剰余演算子

言語	演算子	符号
ActionScript	%	被除数と同一
Ada	mod	除数と同一
	rem	被除数と同一
ASP	Mod	未定義
ALGOL-68	÷×, mod	常に正
AMPL（英語版）	mod	被除数と同一
APL	|	除数と同一
AppleScript	mod	被除数と同一
AWK	%	被除数と同一
BASIC	Mod	未定義
bash	%	被除数と同一
bc	%	被除数と同一
C90 (ISO/IEC 9899:1990) 以前	%	実装による
	div	被除数と同一
C++03 (ISO/IEC 14882:2003) 以前	%	実装による[10]
	div	被除数と同一
C99 (ISO/IEC 9899:1999) 以降	%, div	被除数と同一[11]
C++11 (ISO/IEC 14882:2011) 以降	%, div	被除数と同一
C#	%	被除数と同一
Clarion (programming language)（英語版）	%	被除数と同一
Clojure	mod	除数と同一
COBOL[注釈 3]	FUNCTION MOD	除数と同一
CoffeeScript	%	被除数と同一
	%%	除数と同一[12]
ColdFusion	%, MOD	被除数と同一
Common Lisp	mod	除数と同一
	rem	被除数と同一
D	%	被除数と同一[13]
Dart	%	常に正
	remainder()	被除数と同一
Eiffel	\\	被除数と同一
Erlang	rem	被除数と同一
Euphoria	mod	除数と同一
	remainder	被除数と同一
F#	%	被除数と同一
FileMaker	Mod	除数と同一
Forth	mod	実装による
FORTRAN	mod	被除数と同一
	modulo	除数と同一
Frink	mod	除数と同一
GameMaker: Studio（英語版） (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)	除数と同一
Liberty BASIC（英語版）	MOD	被除数と同一
MathCad（英語版）	mod(x,y)	除数と同一
Maple	e mod m	常に正
Mathematica	Mod	除数と同一
MATLAB	mod	除数と同一
	rem	被除数と同一
Maxima	mod	除数と同一
	remainder	被除数と同一
Maya Embedded Language（英語版）	%	被除数と同一
Microsoft Excel	=MOD()	除数と同一
Minitab	MOD	除数と同一
mksh	%	被除数と同一
Modula-2	MOD	除数と同一[注釈 4]
MUMPS	#	除数と同一
NASM NASMX	%	符号なし剰余演算子
	%%	符号付き剰余演算子
Oberon	MOD	除数と同一[注釈 4]
OCaml	mod	被除数と同一
Occam	\	被除数と同一
Pascal (Delphi)	mod	被除数と同一
Pascal (ISO-7185 および ISO-10206)	mod	常に正
Perl	%	除数と同一[注釈 5]
PHP	%	被除数と同一
PIC Basic Pro	\\	被除数と同一
PL/I	mod	除数と同一 (ANSI PL/I)
PowerShell	%	被除数と同一
Progress（英語版）	modulo	被除数と同一
Prolog (ISO 1995)	mod	除数と同一
	rem	被除数と同一
PureBasic	%,Mod(Number,Divisor)	被除数と同一[14]
Python	%	除数と同一
	math.fmod	被除数と同一
Racket	remainder	被除数と同一
RealBasic（英語版）	MOD	被除数と同一
R	%%	除数と同一
REXX	//	被除数と同一
RPG	%REM	被除数と同一
Ruby	%, modulo()	除数と同一
	remainder()	被除数と同一
Rust	%	被除数と同一
Scala	%	被除数と同一
Scheme	modulo	除数と同一
	remainder	被除数と同一
Scheme R6RS	mod	常に正[15]
	mod0	0に近い側[15]
Seed7（英語版）	mod	除数と同一
	rem	被除数と同一
SenseTalk（英語版）	modulo	除数と同一
	rem	被除数と同一
Smalltalk	\\	除数と同一
	rem:	被除数と同一
SQL (SQL:1999)	mod(x,y)	被除数と同一
Standard ML	mod	除数と同一
	Int.rem	被除数と同一
Stata	mod(x,y)	常に正
Swift	%	被除数と同一
Tcl	%	除数と同一
Torque Game Engine（英語版）	%	被除数と同一
Turing	mod	除数と同一
Verilog (2001)	%	被除数と同一
VHDL	mod	除数と同一
	rem	被除数と同一
Visual Basic	Mod	被除数と同一
x86アセンブリ言語（英語版）	IDIV	被除数と同一
Xbase++（英語版）	%	被除数と同一
	Mod()	除数と同一
Z3 theorem prover	div, mod	常に正

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

さまざまなプログラミング言語の浮動小数点数剰余演算子

言語	演算子	符号
C90 (ISO/IEC 9899:1990) 以前	fmod	被除数と同一[17]
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	%	被除数と同一
Xbase++（英語版）	%	被除数と同一
	Mod()	除数と同一