剰余演算

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索
アルゴリズムの違いによる商(赤線)と余り(緑線)のグラフ

剰余演算モジュロとも呼ぶ)は、コンピュータにおいて、ある数値を別の数値(と呼ばれることもある)で除算し、余りを取得する演算である[1][2]。2つの正の整数である、被除数a および 除数nが与えられる場合、an による剰余 (a modulo n、略して a mod nとも表記される)は、ユークリッド除法における an で除算した余りとなる。例えば、「5 mod 2」の結果は 1 となる。なぜなら、5を2で除算した場合は2となり、余りは1となるからである。また、「9 mod 3」の結果は0となる。9を3で除算した商は3となり余りは0となる(言い方を変えれば9から3を3回引いた場合に残りがなくなる)からである。一般的な電卓を使用して除算を行う場合、商が小数点表記で出力されるため、剰余演算は直接行えないことに注意する。

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

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

剰余演算による余りの算出[編集]

さまざまなプログラミング言語の整数剰余演算子
言語 演算子 符号
ActionScript % 被除数と同一
Ada mod 除数と同一
rem 被除数と同一
ASP Mod 未定義
ALGOL-68 ÷×, mod 常に正
AMPL英語版 mod 被除数と同一
APL | 除数と同一
AppleScript mod 被除数と同一
AWK % 被除数と同一
BASIC Mod 未定義
bash % 被除数と同一
bc % 被除数と同一
C (ISO 1990) % 実装による
div 被除数と同一
C++ (ISO 1998) % 実装による[3]
div 被除数と同一
C (ISO 1999) %, div 被除数と同一[4]
C++ (ISO 2011) %, div 被除数と同一
C# % 被除数と同一
Clarion (programming language)英語版 % 被除数と同一
Clojure mod 除数と同一
COBOL[1] FUNCTION MOD 除数と同一
CoffeeScript % 被除数と同一
%% 除数と同一[5]
ColdFusion %, MOD 被除数と同一
Common Lisp mod 除数と同一
rem 被除数と同一
D % 被除数と同一[6]
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 除数と同一[2]
MUMPS # 除数と同一
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 除数と同一
rem 被除数と同一
Python % 除数と同一
math.fmod 被除数と同一
Racket remainder 被除数と同一
RealBasic英語版 MOD 被除数と同一
R %% 除数と同一
REXX // 被除数と同一
RPG %REM 被除数と同一
Ruby %, modulo() 除数と同一
remainder() 被除数と同一
Rust % 被除数と同一
Scala % 被除数と同一
Scheme modulo 除数と同一
remainder 被除数と同一
Scheme R6RS mod 常に正[8]
mod0 0に近い側[8]
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 Assembly英語版 IDIV 被除数と同一
Xbase++英語版 % 被除数と同一
Mod() 除数と同一
Z3 theorem prover div, mod 常に正
さまざまなプログラミング言語の浮動小数点数剰余演算子
言語 演算子 符号
C (ISO 1990) fmod 被除数と同一[9]
C (ISO 1999) fmod 被除数と同一
remainder 0に近い側
C++ (ISO 1998) std::fmod 被除数と同一
C++ (ISO 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 被除数と同一
Perl 6 % 除数と同一
PHP fmod 被除数と同一
Python % 除数と同一
math.fmod 被除数と同一
REXX // 被除数と同一
Ruby %, modulo() 除数と同一
remainder() 被除数と同一
Scheme R6RS flmod 常に正
flmod0 0に近い側
Standard ML Real.rem 被除数と同一
Swift % 被除数と同一
Xbase++英語版 % 被除数と同一
Mod() 除数と同一

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

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

(1)

ところが、剰余が0でない場合、その符号は不確定なものとなる。数論上は、余りは常に正の数となるが、プログラミング言語によっては a および n の符号によって剰余の符号が正となるか負となるかが定められる。標準的なPascalおよびAlgol68は除数が負数であっても正の剰余(もしくは0)を出力する。しかし、C90のような、他のプログラミング言語では、n または a が負の数の場合にはそうならないことがある。詳細は右表を参照。多くのシステムでは a の 0での剰余は未定義だが、いくつかはaを出力するように定義されている。

  • 多くの実装においては「0への切り落とし除算」が使用されている。これは商を0への切り落とし関数 q = trunc(a/n) によって処理し、(1)の処理における余りは「被除数と同じ符号」となる。この場合の商は0方向へ丸められる。言いかえれば、実数における商から0方向へ向かって直近の整数となる。
  • ドナルド・クヌースは「切り下げ除算」について言及した[10]。これは商を床関数 によって処理し、(1)の処理における余りは「除数と同じ符号」となる。床関数によって、商が負の数であっても常に負の無限大方向に丸められる。
  • Raymond T. Bouteはユークリッド除法の手法での定義について言及している[11]。この場合、余りは非負数(0 ≤ r)となる。右表では「常に正」と表記している。この定義は下記のようにあらわすことができる。

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

  • 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()機能がない環境であっても、下記のように算出できる(「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

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

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

剰余演算の等価性[編集]

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

  • 同一性:
    • 正の整数の場合。
    • 素数であり、かつ の約数でない場合、フェルマーの小定理より となる。
  • 逆数:
    • モジュラ逆数を表す。これは 互いに素である場合にのみ、以下の数式にて定義される。
  • 分配則:
  • 分数(定義): 右辺が定義できる場合。そうでない場合は未定義。
  • 逆数の乗算:

関連項目[編集]

注釈[編集]

  • ^ Perlでは剰余の算術演算子はマシン依存となる。例示とその例外についてはPerl documentationを参照。
  • ^ 右項は正の数でなければならない。左項は定義されていない。
  • ^ ACUCOBOL、Micro Focus COBOLなどの実装。

出典[編集]

  1. ^ MSDN 剰余演算子 (%)”. マイクロソフト. 2015年12月9日閲覧。
  2. ^ ASCII.jpデジタル用語辞典 モジュロ”. http://ascii.jp/.+2015年12月9日閲覧。
  3. ^ ISO/IEC 14882:2003 : Programming languages -- C++. 5.6.4: ISO, IEC. (2003) . "二項演算子 % 左項を右項で割った余りを算出する。.... オペランドが共に負数でない場合は余りも負数ではない。しかし、そうでない場合の剰余の符号は実装によって定義される。"
  4. ^ open-std.org, section 6.5.5
  5. ^ CoffeeScript operators
  6. ^ Expressions”. D Programming Language 2.0. Digital Mars. 2010年7月29日閲覧。
  7. ^ Mod()”. PureBasic. Fantaisie Software. 2015年12月9日閲覧。
  8. ^ a b r6rs.org
  9. ^ ISO/IEC 9899:1990 : Programming languages -- C. 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. http://portal.acm.org/citation.cfm?id=128862&coll=portal&dl=ACM. 
  12. ^ Leijen, Daan (2001年12月3日). “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日閲覧。