剰余演算

剰余演算（じょうよえんざん）は、ある数値（被除数、テンプレート:Lang-en-short）を別の数値（除数、テンプレート:Lang-en-short）で除算し、余り（剰余、テンプレート:Lang-en-short）を取得する演算である^[1]^[2]。モジュロ演算（テンプレート:Lang-en-short）とも呼ばれる^[3]。

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

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

概要

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

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

数論における古典的な関連事項については合同算術を参照。テンプレート:-

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

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

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

テンプレート:NumBlk

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

テンプレート:Bulleted list

Daan Leijenはこのように記している。テンプレート:Quote

ありがちなミス

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

例えば、ある整数が奇数であるかどうかを調べたい場合、下記の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 関数または演算子が用意されていないか、正しく機能しない環境テンプレート:Efnであっても、下記のように算出できる。ここで、int()は小数点以下を切り捨てた値を生成する。

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

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

ビット演算による効率化

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

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

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

例を示す（x は正の整数とする）。

x % 2 == x & 1

x % 4 == x & 3

x % 8 == x & 7

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

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

剰余演算の等価性

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

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

テンプレート:Visible anchor

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

さまざまなプログラミング言語の整数剰余演算子
言語	演算子	符号
ActionScript	`%`	被除数と同一
Ada	`mod`	除数と同一
Ada	`rem`	被除数と同一
ASP	`Mod`	未定義
ALGOL-68	`÷×, mod`	常に正
テンプレート:仮リンク	`mod`	被除数と同一
APL	`\|`	除数と同一
AppleScript	`mod`	被除数と同一
AWK	`%`	被除数と同一
BASIC	`Mod`	未定義
bash	`%`	被除数と同一
bc	`%`	被除数と同一
C90 (ISO/IEC 9899:1990) 以前	`%`	実装による
C90 (ISO/IEC 9899:1990) 以前	`div`	被除数と同一
C++03 (ISO/IEC 14882:2003) 以前	`%`	実装による^[7]
C++03 (ISO/IEC 14882:2003) 以前	`div`	被除数と同一
C99 (ISO/IEC 9899:1999) 以降	`%`, `div`	被除数と同一^[8]
C++11 (ISO/IEC 14882:2011) 以降	`%`, `div`	被除数と同一
C#	`%`	被除数と同一
テンプレート:仮リンク	`%`	被除数と同一
Clojure	`mod`	除数と同一
COBOL テンプレート:Efn	`FUNCTION MOD`	除数と同一
CoffeeScript	`%`	被除数と同一
CoffeeScript	`%%`	除数と同一^[9]
ColdFusion	`%, MOD`	被除数と同一
Common Lisp	`mod`	除数と同一
Common Lisp	`rem`	被除数と同一
D	`%`	被除数と同一^[10]
Dart	`%`	常に正
Dart	`remainder()`	被除数と同一
Eiffel	`\\`	被除数と同一
Erlang	`rem`	被除数と同一
Euphoria	`mod`	除数と同一
Euphoria	`remainder`	被除数と同一
F#	`%`	被除数と同一
FileMaker	`Mod`	除数と同一
Forth	`mod`	実装による
FORTRAN	`mod`	被除数と同一
FORTRAN	`modulo`	除数と同一
Frink	`mod`	除数と同一
テンプレート:仮リンク (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)`	除数と同一
テンプレート:仮リンク	`MOD`	被除数と同一
テンプレート:仮リンク	`mod(x,y)`	除数と同一
Maple	`e mod m`	常に正
Mathematica	`Mod`	除数と同一
MATLAB	`mod`	除数と同一
MATLAB	`rem`	被除数と同一
Maxima	`mod`	除数と同一
Maxima	`remainder`	被除数と同一
テンプレート:仮リンク	`%`	被除数と同一
Microsoft Excel	`=MOD()`	除数と同一
Minitab	`MOD`	除数と同一
mksh	`%`	被除数と同一
Modula-2	`MOD`	除数と同一テンプレート:Efn
MUMPS	`#`	除数と同一
NASM NASMX	`%`	符号なし剰余演算子
NASM NASMX	`%%`	符号付き剰余演算子
Oberon	`MOD`	除数と同一テンプレート:Efn
OCaml	`mod`	被除数と同一
Occam	`\`	被除数と同一
Pascal (Delphi)	`mod`	被除数と同一
Pascal (ISO-7185 および ISO-10206)	`mod`	常に正
Perl	`%`	除数と同一テンプレート:Efn
PHP	`%`	被除数と同一
PIC Basic Pro	`\\`	被除数と同一
PL/I	`mod`	除数と同一 (ANSI PL/I)
PowerShell	`%`	被除数と同一
テンプレート:仮リンク	`modulo`	被除数と同一
Prolog (ISO 1995)	`mod`	除数と同一
Prolog (ISO 1995)	`rem`	被除数と同一
Python	`%`	除数と同一
Python	`math.fmod`	被除数と同一
Racket	`remainder`	被除数と同一
テンプレート:仮リンク	`MOD`	被除数と同一
R	`%%`	除数と同一
REXX	`//`	被除数と同一
RPG	`%REM`	被除数と同一
Ruby	`%, modulo()`	除数と同一
Ruby	`remainder()`	被除数と同一
Rust	`%`	被除数と同一
Scala	`%`	被除数と同一
Scheme	`modulo`	除数と同一
Scheme	`remainder`	被除数と同一
Scheme R⁶RS	`mod`	常に正^[12]
Scheme R⁶RS	`mod0`	0に近い側^[12]
テンプレート:仮リンク	`mod`	除数と同一
テンプレート:仮リンク	`rem`	被除数と同一
テンプレート:仮リンク	`modulo`	除数と同一
テンプレート:仮リンク	`rem`	被除数と同一
Smalltalk	`\\`	除数と同一
Smalltalk	`rem:`	被除数と同一
SQL (SQL:1999)	`mod(x,y)`	被除数と同一
Standard ML	`mod`	除数と同一
Standard ML	`Int.rem`	被除数と同一
Stata	`mod(x,y)`	常に正
Swift	`%`	被除数と同一
Tcl	`%`	除数と同一
テンプレート:仮リンク	`%`	被除数と同一
Turing	`mod`	除数と同一
Verilog (2001)	`%`	被除数と同一
VHDL	`mod`	除数と同一
VHDL	`rem`	被除数と同一
Visual Basic	`Mod`	被除数と同一
テンプレート:仮リンク	`IDIV`	被除数と同一
テンプレート:仮リンク	`%`	被除数と同一
テンプレート:仮リンク	`Mod()`	除数と同一
Z3 theorem prover	`div`, `mod`	常に正

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

さまざまなプログラミング言語の浮動小数点数剰余演算子
言語	演算子	符号
C90 (ISO/IEC 9899:1990) 以前	`fmod`	被除数と同一^[14]
C99 (ISO/IEC 9899:1999) 以降	`fmod`	被除数と同一
C99 (ISO/IEC 9899:1999) 以降	`remainder`	0に近い側
C++03 (ISO/IEC 14882:2003) 以前	`std::fmod`	被除数と同一
C++11 (ISO/IEC 14882:2011) 以降	`std::fmod`	被除数と同一
C++11 (ISO/IEC 14882: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	`%`	被除数と同一
テンプレート:仮リンク	`%`	被除数と同一
テンプレート:仮リンク	`Mod()`	除数と同一

脚注

テンプレート:脚注ヘルプ

注釈

テンプレート:Notelist

出典

テンプレート:Reflist

剰余演算

目次

概要

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

ありがちなミス

剰余演算の表記

剰余算出の代替手段

ビット演算による効率化

剰余演算の等価性

テンプレート:Visible anchor

脚注

注釈

出典

関連項目

ナビゲーションメニュー

剰余演算

概要

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

ありがちなミス

剰余演算の表記

剰余算出の代替手段

ビット演算による効率化

剰余演算の等価性

テンプレート:Visible anchor

脚注

注釈

出典

関連項目

ナビゲーション メニュー

検索

ナビゲーションメニュー