「剰余演算」の版間の差分

削除された内容追加された内容

インライン

2020年7月6日 (月) 00:30時点における版

剰余演算（モジュロとも呼ぶ）は、コンピュータにおいて、ある数値を別の数値(法と呼ばれることもある)で除算し、余りを取得する演算である^[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回引いた場合に残りがなくなる)からである。一般的な電卓を使用して除算を行う場合、商が小数点表記で出力されるため、剰余演算は直接行えないことに注意する。

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

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

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

さまざまなプログラミング言語の整数剰余演算子
言語	演算子	符号
ActionScript	`%`	被除数と同一
Ada	`mod`	除数と同一
Ada	`rem`	被除数と同一
ASP	`Mod`	未定義
ALGOL-68	`÷×, mod`	常に正
AMPL（英語版）	`mod`	被除数と同一
APL	`\|`	除数と同一
AppleScript	`mod`	被除数と同一
AWK	`%`	被除数と同一
BASIC	`Mod`	未定義
bash	`%`	被除数と同一
bc	`%`	被除数と同一
C (ISO 1990)	`%`	実装による
C (ISO 1990)	`div`	被除数と同一
C++ (ISO 1998)	`%`	実装による^[3]
C++ (ISO 1998)	`div`	被除数と同一
C (ISO 1999)	`%`, `div`	被除数と同一^[4]
C++ (ISO 2011)	`%`, `div`	被除数と同一
C#	`%`	被除数と同一
Clarion (programming language)（英語版）	`%`	被除数と同一
Clojure	`mod`	除数と同一
COBOL^[1]	`FUNCTION MOD`	除数と同一
CoffeeScript	`%`	被除数と同一
CoffeeScript	`%%`	除数と同一^[5]
ColdFusion	`%, MOD`	被除数と同一
Common Lisp	`mod`	除数と同一
Common Lisp	`rem`	被除数と同一
D	`%`	被除数と同一^[6]
Dart	`%`	常に正
Dart	`remainder()`	被除数と同一
Eiffel	`\\`	被除数と同一
Erlang	`rem`	被除数と同一
Euphoria	`mod`	除数と同一
Euphoria	`remainder`	被除数と同一
F#	`%`	被除数と同一
FileMaker	`Mod`	除数と同一
Forth	`mod`	実装による
FORTRAN	`mod`	被除数と同一
FORTRAN	`modulo`	除数と同一
Frink	`mod`	除数と同一
GameMaker: Studio（英語版） (GML)	`mod`	被除数と同一
GDScript	`%`	被除数と同一
Go	`%`	被除数と同一
Haskell	`mod`	除数と同一
Haskell	`rem`	被除数と同一
Haxe	`%`	被除数と同一
J	`\|~`	除数と同一
Java	`%`	被除数と同一
Java	`Math.floorMod`	除数と同一
JavaScript	`%`	被除数と同一
Julia	`mod`	除数と同一
Julia	`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`	除数と同一
MATLAB	`rem`	被除数と同一
Maxima	`mod`	除数と同一
Maxima	`remainder`	被除数と同一
Maya Embedded Language（英語版）	`%`	被除数と同一
Microsoft Excel	`=MOD()`	除数と同一
Minitab	`MOD`	除数と同一
mksh	`%`	被除数と同一
Modula-2	`MOD`	除数と同一^[2]
MUMPS	`#`	除数と同一
NASM NASMX	`%`	符号なし剰余演算子
NASM NASMX	`%%`	符号付き剰余演算子
Oberon	`MOD`	除数と同一^[3]
OCaml	`mod`	被除数と同一
Occam	`\`	被除数と同一
Pascal (Delphi)	`mod`	被除数と同一
Pascal (ISO-7185 および ISO-10206)	`mod`	常に正
Perl	`%`	除数と同一^[4]
PHP	`%`	被除数と同一
PIC Basic Pro	`\\`	被除数と同一
PL/I	`mod`	除数と同一 (ANSI PL/I)
PowerShell	`%`	被除数と同一
Progress（英語版）	`modulo`	被除数と同一
Prolog (ISO 1995)	`mod`	除数と同一
Prolog (ISO 1995)	`rem`	被除数と同一
Python	`%`	除数と同一
Python	`math.fmod`	被除数と同一
Racket	`remainder`	被除数と同一
RealBasic（英語版）	`MOD`	被除数と同一
R	`%%`	除数と同一
REXX	`//`	被除数と同一
RPG	`%REM`	被除数と同一
Ruby	`%, modulo()`	除数と同一
Ruby	`remainder()`	被除数と同一
Rust	`%`	被除数と同一
Scala	`%`	被除数と同一
Scheme	`modulo`	除数と同一
Scheme	`remainder`	被除数と同一
Scheme R⁶RS	`mod`	常に正^[8]
Scheme R⁶RS	`mod0`	0に近い側^[8]
Seed7（英語版）	`mod`	除数と同一
Seed7（英語版）	`rem`	被除数と同一
SenseTalk（英語版）	`modulo`	除数と同一
SenseTalk（英語版）	`rem`	被除数と同一
Smalltalk	`\\`	除数と同一
Smalltalk	`rem:`	被除数と同一
SQL (SQL:1999)	`mod(x,y)`	被除数と同一
Standard ML	`mod`	除数と同一
Standard ML	`Int.rem`	被除数と同一
Stata	`mod(x,y)`	常に正
Swift	`%`	被除数と同一
Tcl	`%`	除数と同一
Torque Game Engine（英語版）	`%`	被除数と同一
Turing	`mod`	除数と同一
Verilog (2001)	`%`	被除数と同一
VHDL	`mod`	除数と同一
VHDL	`rem`	被除数と同一
Visual Basic	`Mod`	被除数と同一
x86 Assembly（英語版）	`IDIV`	被除数と同一
Xbase++（英語版）	`%`	被除数と同一
Xbase++（英語版）	`Mod()`	除数と同一
Z3 theorem prover	`div`, `mod`	常に正

さまざまなプログラミング言語の浮動小数点数剰余演算子
言語	演算子	符号
C (ISO 1990)	`fmod`	被除数と同一^[9]
C (ISO 1999)	`fmod`	被除数と同一
C (ISO 1999)	`remainder`	0に近い側
C++ (ISO 1998)	`std::fmod`	被除数と同一
C++ (ISO 2011)	`std::fmod`	被除数と同一
C++ (ISO 2011)	`std::remainder`	0に近い側
C#	`%`	被除数と同一
Common Lisp	`mod`	除数と同一
Common Lisp	`rem`	被除数と同一
D	`%`	被除数と同一
Dart	`%`	常に正
Dart	`remainder()`	被除数と同一
F#	`%`	被除数と同一
FORTRAN	`mod`	被除数と同一
FORTRAN	`modulo`	除数と同一
Go	`math.Mod`	被除数と同一
Haskell (GHC)	`Data.Fixed.mod'`	除数と同一
Java	`%`	被除数と同一
JavaScript	`%`	被除数と同一
Microsoft Excel	`=MOD()`	除数と同一
OCaml	`mod_float`	被除数と同一
Perl	`POSIX::fmod`	被除数と同一
Raku	`%`	除数と同一
PHP	`fmod`	被除数と同一
Python	`%`	除数と同一
Python	`math.fmod`	被除数と同一
REXX	`//`	被除数と同一
Ruby	`%, modulo()`	除数と同一
Ruby	`remainder()`	被除数と同一
Scheme R⁶RS	`flmod`	常に正
Scheme R⁶RS	`flmod0`	0に近い側
Standard ML	`Real.rem`	被除数と同一
Swift	`%`	被除数と同一
Xbase++（英語版）	`%`	被除数と同一
Xbase++（英語版）	`Mod()`	除数と同一

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

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

{\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方向へ向かって直近の整数となる。
ドナルド・クヌースは「切り下げ除算」について言及した^[10]。これは商を床関数 $q=\lfloor (a/n)\rfloor$ によって処理し、(1)の処理における余りは「除数と同じ符号」となる。床関数によって、商が負の数であっても常に負の無限大方向に丸められる。
$r=a-n\left\lfloor {\frac {a}{n}}\right\rfloor$
Raymond T. Bouteはユークリッド除法の手法での定義について言及している^[11]。この場合、余りは非負数( $0 \leq r$ )となる。右表では「常に正」と表記している。この定義は下記のようにあらわすことができる。
$n>0\Rightarrow q=\left\lfloor {\frac {a}{n}}\right\rfloor$

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

また、符号関数 $sgn$ を使用する場合、下記のようにもあらわせる。

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

$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^[12]

ありがちなミス

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

例えば、ある整数が奇数であるかチェックしたい場合、下記の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()機能がないか、正しく機能しない環境^[5]であっても、下記のように算出できる(「int()」は小数点以下を切り捨てた値を生成する)。

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

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

ビット演算による効率化

剰余演算は、除算を行い余りを取得する実装となるため、その分の処理時間を必要とする。特殊な場合においては、いくつかのハードウェア上でより高速な計算方法が存在する。たとえば、2のべき乗の剰余を処理する場合、下記のようにビット単位AND演算を使用することができる。

x % 2ⁿ == x & (2ⁿ - 1)

以下に例を示す(xは正の整数とする)。

x % 2 == x & 1

x % 4 == x & 3

x % 8 == x & 7

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

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

剰余演算の等価性

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

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

注釈

^ Perlでは剰余の算術演算子はマシン依存となる。例示とその例外についてはPerl documentationを参照。
^ 右項は正の数でなければならない。左項は定義されていない。
^ ACUCOBOL、Micro Focus COBOLなどの実装。
^ たとえばファミリーベーシックのROMバージョン2.0Aでは、除数と被除数が等しい場合にMODの演算が正しく行われない。

出典

^ “MSDN 剰余演算子 (%)”. マイクロソフト. 2015年12月9日閲覧。
^ “ASCII.jpデジタル用語辞典モジュロ”. http://ascii.jp/.+2015年12月9日閲覧。
^ "ISO/IEC 14882:2003 : Programming languages -- C++" (Document). 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" (Document). 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. (April 1992). “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.
^ Leijen, Daan (December 3, 2001). “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日閲覧。

[1] “MSDN 剰余演算子 (%)”. マイクロソフト. 2015年12月9日閲覧。

[2] “ASCII.jpデジタル用語辞典モジュロ”. http://ascii.jp/.+2015年12月9日閲覧。

[3] "ISO/IEC 14882:2003 : Programming languages -- C++" (Document). 5.6.4: ISO, IEC. 2003.. "二項演算子 % 左項を右項で割った余りを算出する。.... オペランドが共に負数でない場合は余りも負数ではない。しかし、そうでない場合の剰余の符号は実装によって定義される。"

[C99-4] -std.org, section 6.5.5

[CoffeeScript-5] CoffeeScript operators

[6] “Expressions”. D Programming Language 2.0. Digital Mars. 2010年7月29日閲覧。

[7] “Mod()”. PureBasic. Fantaisie Software. 2015年12月9日閲覧。

[r6rs-8] r6rs.org

[9] "ISO/IEC 9899:1990 : Programming languages -- C" (Document). 7.5.6.4: ISO, IEC. 1990.. "fmod関数は、yが0でない場合、iが整数となるx - i * yの結果を返す。結果はxと同じ符号となり、yよりも小さな絶対値をとる。"

[10] Knuth, Donald. E. (1972). The Art of Computer Programming. Addison-Wesley

[11] Boute, Raymond T. (April 1992). “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.

[12] Leijen, Daan (December 3, 2001). “Division and Modulus for Computer Scientists” (PDF). 2014年12月25日閲覧。

[13] Horvath, Adam (2012年7月5日). “Faster division and modulo operation - the power of two”. 2015年12月9日閲覧。

[1]

[2]

[3]

[4]

[1]

[5]

[6]

[2]

[4]

[8]

[9]

[10]

[11]

[12]

[5]

[13]

@@ 460行目: / 460行目: @@
 もちろん、どのような奇数も、剰余は 1 または -1 となるため、下記のような実装もできる。
-<source lang="cpp">
+<syntaxhighlight lang="cpp">
 bool is_odd(int n) {
     return n % 2 == 1 || n % 2 == -1;
 }
+</syntaxhighlight>
-</source>
 == 剰余演算の表記 ==