トップQs
タイムライン
チャット
視点
剰余演算
ウィキペディアから
Remove ads
剰余演算(じょうよえんざん)は、ある数値(被除数、英: 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 が負数の場合については、単純な定義はなく、プログラミング言語によってどのように定義されるかが異なっている。
Remove ads
剰余演算による余りの算出
要約
視点
数学的には、剰余演算の結果はユークリッド除法における余りのことである。しかし、別の法則に従って算出されることもある。コンピュータやその他の計算機は数値の保持や処理方法がさまざまなので、剰余演算の定義はプログラミング言語や動作するハードウェアによって、それぞれ規定されている。
ほぼすべてのコンピュータシステムにおいて、a を n で除算した商 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]
Remove ads
ありがちなミス
被除数の符号に剰余の結果が依存する場合、失敗を引き起こす場合がある。
例えば、ある整数が奇数であるかどうかを調べたい場合、下記の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言語のように剰余演算の結果の符号が被除数によって定まる言語では同じ動作はしない。したがって、被除数が負になる場合は、特別な注意が必要である。
Remove ads
剰余演算の等価性
要約
視点
他の数学的演算と同様に、剰余演算についてもいくつかの演算を導出、または拡張することができる。そうすることで、ディフィー・ヘルマン鍵交換のような暗号学分野の証明が容易となるだろう。
Remove ads
各プログラミング言語における仕様
要約
視点
以下の表では「演算子」と総称されているが、実際には演算子ではなく関数(サブルーチン)による実装となっている言語もあることに注意されたい。
いくつかの言語では浮動小数点数オペランドに対しても剰余演算子が利用できるようになっているが、IEEE 754準拠の剰余ではなく、通例整数オペランドに対する剰余と似た仕様となっている。そのため、IEEE準拠の剰余を求めるライブラリ関数が別途用意されていることも多い。Javaでは、Math.IEEEremainder()
メソッドが用意されている。C#やVB.NETのような.NET言語では、Math.IEEERemainder()
メソッドが用意されている[16]。
Remove ads
脚注
関連項目
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads