整数の除算と剰余の種類

はじめに

整数同士の除算/剰余演算を行う場合、端数処理の方法によって解がことなる.
ここではそれぞれの場合についてどのような結果となるのかをまとめる.
なお、例として挙げるコードは C# で書く.

剰余の計算方法

<商> = <被除数> / <除数>
とするとき、
<剰余> = <被除数> - (<商> * <除数>)
で表せる.
例として、
<被除数> = 42
<除数> = 7
とすれば、
<商> = 42 / 7 = 6
<剰余> = 42 - (6 * 7) = 0
となる.
商が整数とならない場合における、剰余のバリエーションがこの記事の主眼である.
以下、特に注意がない場合
q := <商>
r := <剰余>
x := <被除数>
y := <除数>
であるものとする.

まとめの表

最後まで読むのは面倒かと思われるため先に一覧表を提示する.

端数処理	剰余の範囲	剰余の符号	補足等	C# における関数	Google sheets における関数
正の無限大への丸め	(-abs(y) .. abs(y))	除数と異なる符号	普通使わない	System.Math.Ceiling(double)	CEILING
負の無限大への丸め	(-abs(y) .. abs(y))	除数と同じ符号	これを使いたい時があるかも	System.Math.Floor(double)	FLOOR
0への丸め	(-abs(y) .. abs(y))	被除数と同じ符号	C# における整数の除算はこれ	System.Math.Truncate(double)	TRUNCATE/ROUNDDOWN
0から離れる丸め	(-abs(y) .. abs(y))	被除数と異なる符号	普通使わない	(実装なし？)	ROUNDUP
四捨五入	[-abs(y)/2 .. abs(y)/2]	abs(y)/2 と合同のとき、被除数と異なる符号	絶対最小剰余	System.Math.Round(double, MidpointRounding.AwayFromZero)	ROUND

この記事では扱わないが、四捨五入のような最近接丸めにも、X.5 の扱いについてバリエーションが存在する.
詳細は英語版 Wikipedia の各 Round half ～ を参照されたし.
C# における System.Math.Round(double) は銀行家の丸め(MidpointRounding.ToEven)を行う.

C# の場合、標準では剰余が被除数と同じ符号となるが、
プログラム上では剰余が常に非負であることを期待する計算も少なくない.
加えて、被除数を正負の不明な引数として受け取り、定数で割ること場合が多い.
除数が正であると分かっている場合には、負の無限大への丸めを利用した剰余を使うと都合がよい.

被除数、除数ともに符号が不明な場合、次で最小非負剰余が得られる. (どうしても if 文を使いたくない場合)

static int NonNegativeMod(int x, int y) {
  // FloorMod := 負の無限大への丸めによる剰余
  // Abs      := System.Math.Abs
  return (FloorMod(x, y) + Abs(y)) % Abs(y);
}

より一般に、剰余の範囲を [k .. k+abs(y)) にしたい場合は次のように書ける:

static int ModInSpecificRange(int x, int y, int k) {
  // FloorMod := 負の無限大への丸めによる剰余
  // Abs      := System.Math.Abs
  return FloorMod(FloorMod(x, y) - k), Abs(y)) + k;
}

各方法の詳細

正の無限大への丸め(Ceil/Rounding toward positive infinity)

一般に天井関数(Ceiling function)とよばれるものを使って端数を処理する.
これは小数としての商をそれ以上で、最小の整数に丸める方法である.
e.g. 5.7 -> 6, -5.7 -> 5
C# では System.Math.Ceiling、Google sheets では CEILING として提供されている.
整数の剰余演算に用いると、常に除数と異なる符号となる. あえて使うことはないだろう.

この端数処理に従う除算/剰余演算プログラム例

static (int q, int r) CeilDivRem(int x, int y) {
  int q = x / y;
  // C# の標準では 0への丸め が行われるため、
  // x, y の符号が同じで、かつ剰余が 0 でない場合は商をインクリメントする
  if((x ^ y) > 0 && (q * y != x)) {
    ++q;
  }
  // 得られた商で剰余を計算する
  int r = x - q * y;
  return (q, r);
}

負の無限大への丸め(Floor/Rounding toward negative infinity)

一般に床関数(Floor function)とよばれるものを使って端数を処理する.
これは小数としての商をそれ以下で、最大の整数に丸める方法である.
e.g. 5.7 -> 5, -5.7 -> -6
C# では System.Math.Floor、Google sheets では FLOOR として提供されている.

この端数処理に従う除算/剰余演算プログラム例

static (int q, int r) FloorDivRem(int x, int y) {
  int q = x / y;
  // C# の標準では 0への丸め が行われるため、
  // x, y の符号が異なり、かつ剰余が 0 でない場合は商をインクリメントする
  if((x ^ y) < 0 && (q * y != x)) {
    --q;
  }
  // 得られた商で剰余を計算する
  int r = x - q * y;
  return (q, r);
}

0への丸め(Truncate/Round down/Rounding toward zero)

日本語ではおそらく切り捨て関数と呼ぶことが多いと思われるものを使って端数を処理する. (英語では Truncate で共通認識が作られているように感じる)
これは小数としての商を、最も0方向で最も近い整数に丸める方法である.
e.g. 5.7 -> 5, -5.7 -> -5
C# では System.Math.Truncate、Google sheets では TRUNC/ROUNDDOWN として提供されている.

この端数処理に従う除算/剰余演算プログラム例

static (int q, int r) TruncDivRem(int x, int y) {
  int q = x / y;
  // C# の標準では 0への丸め が行われるため、調整は不要
  // 得られた商で剰余を計算する
  int r = x - q * y;
  return (q, r);

  // なお、自力で実装するまでもなく標準で実装されている:
  // int q = System.Math.DivRem(x, y, out int r);
  // return (q, r);

  // 当然、関数を使わずに演算子だけで計算してもよい(商と剰余両方が必要な場合は DivRem を使う方が速いかもしれないが)
  // int q = x / y;
  // int r = x % y;
  // return (q, r);
}

0から離れる丸め(Round up/Rounding away from zero)

日本語では何と呼ぶべきか不明瞭だが(切り上げ関数？)、英語版 Wikipediaには Rounding away from zero とある方法.
これは小数としての商を、最も0と反対方向で最も近い整数に丸める方法である.
e.g. 5.7 -> 6, -5.7 -> -6
C# では System.Math 内に該当する処理がないものの、Google sheets では ROUNDUP として提供されている.

この端数処理に従う除算/剰余演算プログラム例

static (int q, int r) RoundupDivRem(int x, int y) {
  int q = x / y;
  int r = x - q * y;
  // 割り切れたならばこれで計算終了
  if(r == 0) return (q, 0);

  // 除数, 被除数の符号が異なればデクリメント、同じならばインクリメント
  if((x ^ y) < 0) --q;
  else            ++q;
  // 剰余を計算しなおす
  r = x - q * y;
  return (q, r);

  // 剰余を計算しなおさず、次のように書いてもよい
  // if((x ^ y) < 0) return (q - 1, r + y);
  // else            return (q + 1, r - y);
}

四捨五入(Commercial rounding/Round half away from zero)

一般に四捨五入と呼ばれる方法. 英語でも単に Round といった場合はこれを指すものと思われる.
C# では System.Math.Round(double, MidpointRounding.AwayFromZero)、Google sheets では ROUND として提供されている.
e.g. 5.5 -> 6, 5.4 -> 5, -5.4 -> -5, -5.5 -> -6

最近接丸めは最も近い整数に丸める方法だが、最も近い整数がふたつある場合(i.e. 小数部が丁度0.5である場合)に上述した各方法のいずれかが行われる.
つまり、0から離れる(切り上げる)、0へ近づく(切り捨てる)、正の無限大へ近づく(天井を取る)、負の無限大へ近づく(床を取る)などである.
小数部が0.5になった場合の剰余の符号は、それぞれ上述している手法での符号に等しい.
表にすれば以下のようになる(h = abs(y/2) とする):

x の符号	y の符号	小数部が丁度0.5である場合の丸め方	剰余の範囲	丸め方の英名	補足
+	ANY	0から離れる	[-h .. h)	round half away from zero	通称四捨五入
-	ANY	0から離れる	(-h .. h]	round half away from zero	通称四捨五入
+	ANY	0へ近づく	(-h .. h]	round half toward zero
-	ANY	0へ近づく	[-h .. h)	round half toward zero
ANY	+	正の無限大へ近づく	[-h .. h)	round half toward positive infinity
ANY	-	正の無限大へ近づく	(-h .. h]	round half toward positive infinity
ANY	+	負の無限大へ近づく	(-h .. h]	round half toward negative infinity
ANY	-	負の無限大へ近づく	[-h .. h)	round half toward negative infinity

この端数処理に従う除算/剰余演算プログラム例

static (int q, int r) RoundDivRem(int x, int y) {
  int q;
  // 符号が異なれば(=>小数としての商が負であれば)除数の半分を引いてから割る. さもなくば、足してから割る.
  if((x ^ y) < 0) q = ((x - y / 2) / y);
  else            q = ((x + y / 2) / y);
  // 商さえ得られれば、剰余は定義通りに計算するだけ.
  int r = x - q * y;
  return (q, r);

  // Round half toward negative infinity が欲しい場合以下で q を求める:
  // int q = CeilDivRem((x - y / 2), y).q
  // Round half toward positive infinity が欲しい場合以下で q を求める:
  // int q = FloorDivRem((x + y / 2), y).q;
  // Round half toward zero が欲しい場合以下で q を求める:
  // int v = FloorDivRem(CeilDivRem(System.Math.Abs(2 * x), System.Math.Abs(y)).q, 2).q;
  // int q = ((x ^ y) < 0)? -v : v;

  // こういったことをする場合は、～DivRem ではなく商だけを返す ～Div を用意すべきかも
}