剰余演算とは? わかりやすく解説

剰余演算

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2025/04/25 00:48 UTC 版)

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

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

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

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

概要

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

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

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

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

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

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

(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]。これは商を床関数 によって処理し、(1)の処理における余りは「除数と同じ符号」となる。床関数によって、商が負の数であっても常に負の無限大方向に丸められる。
  • Raymond T. Bouteはユークリッド除法の手法での定義について言及している[7]。この場合、余りは非負数(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[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言語のように剰余演算の結果の符号が被除数によって定まる言語では同じ動作はしない。したがって、被除数が負になる場合は、特別な注意が必要である。

剰余演算の等価性

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

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

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

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

さまざまなプログラミング言語の整数剰余演算子
言語 演算子 符号
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() 除数と同一

脚注

注釈

  1. ^ 一般的な電卓を使用して除算を行う場合、商が小数点表記で出力されるので、剰余演算は直接行えないことに注意する。
  2. ^ たとえばファミリーベーシックのROMバージョン2.0Aでは、除数と被除数が等しい場合にMODの演算が正しく行われない[要出典]
  3. ^ ACUCOBOL、Micro Focus COBOLなどの実装。
  4. ^ a b 除数は正の数でなければならない。さもなければ未定義動作を引き起こす。
  5. ^ Perlでは剰余の算術演算子は機種依存となる。例示とその例外についてはPerl documentationを参照。

出典

  1. ^ MSDN 剰余演算子 (%)”. マイクロソフト. 2015年12月9日閲覧。
  2. ^ ASCII.jpデジタル用語辞典 モジュロ”. https://ascii.jp/.+2015年12月9日閲覧。
  3. ^ 剰余演算(モジュロ演算 / mod)とは - 意味をわかりやすく - IT用語辞典 e-Words
  4. ^ moduloの意味・使い方・読み方|英辞郎 on the WEB
  5. ^ 整数に対する除算と剰余算の丸め結果を規定 - cpprefjp C++日本語リファレンス
  6. ^ Knuth, Donald. E. (1972). The Art of Computer Programming. Addison-Wesley 
  7. ^ 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. 
  8. ^ Leijen, Daan (2001年12月3日). “Division and Modulus for Computer Scientists” (PDF). 2014年12月25日閲覧。
  9. ^ Horvath, Adam (2012年7月5日). “Faster division and modulo operation - the power of two”. 2015年12月9日閲覧。
  10. ^ "ISO/IEC 14882:2003 : Programming languages -- C++" (Document). 5.6.4: ISO, IEC. 2003. 二項 % 演算子は第1式を第2式で割った余りを算出する。... オペランドがともに非負の場合は余りも非負となる。しかし、そうでない場合の剰余の符号は実装定義となる。
  11. ^ open-std.org, section 6.5.5
  12. ^ CoffeeScript operators
  13. ^ Expressions”. D Programming Language 2.0. Digital Mars. 2010年7月29日閲覧。
  14. ^ Mod()”. PureBasic. Fantaisie Software. 2015年12月9日閲覧。
  15. ^ a b r6rs.org
  16. ^ Math.IEEERemainder(Double, Double) Method (System) | Microsoft Learn
  17. ^ "ISO/IEC 9899:1990 : Programming languages -- C" (Document). 7.5.6.4: ISO, IEC. 1990. fmod関数は、yが0でない場合、iが整数となるx - i * yの値を返す。結果はxと同じ符号となり、yよりも小さな絶対値をとる。

関連項目


剰余演算

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/12/31 08:29 UTC 版)

除法の原理」の記事における「剰余演算」の解説

「剰余演算」も参照 自然数 n を固定して整数 m を n で割ったとき、その剰余はただ一つ定まるから、剰余計算二項演算一種と見ることもできる剰余求め演算演算子として "mod" が用いられ次のように書く。 m mod n mod(m, n) 一部プログラミング言語C言語など)では "%" を用いて、m % n と書く。n が正のとき、剰余演算の結果は、0 以上 n 未満である。例えば、7 mod 5 = 2 であり、−7 mod 5 = 3 である。 余り等しいことを意味する等式 a mod n = b mod n は、合同式 a ≡ b (mod n) と解釈するともできる。 剰余演算は、日常レベルからRSA暗号などの計算機科学までの幅広い分野利用される

※この「剰余演算」の解説は、「除法の原理」の解説の一部です。
「剰余演算」を含む「除法の原理」の記事については、「除法の原理」の概要を参照ください。

ウィキペディア小見出し辞書の「剰余演算」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「剰余演算」の関連用語

剰余演算のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



剰余演算のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの剰余演算 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
ウィキペディアウィキペディア
Text is available under GNU Free Documentation License (GFDL).
Weblio辞書に掲載されている「ウィキペディア小見出し辞書」の記事は、Wikipediaの除法の原理 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。

©2025 GRAS Group, Inc.RSS