🌊

整数除算の二つの流儀

2023/02/10に公開
4

整数除算の流儀

整数除算は割り切れなかった時の商の扱い方によって何種類かに分類でき、商を0に向かって切り捨てるものと、-\inftyに向かって切り下げる(床関数)ものの2種類がよく使われます。この記事ではこれらの関係を見ていきます。

ここではquot, rem, div, modを次のように定めます。ただし、\mathrm{trunc}(x)xと同じ符号を持ち、絶対値が\lvert x\rvertを超えない最大の整数であるような整数です。

\begin{aligned} \mathrm{quot}(n,d)&:=\mathrm{trunc}(n/d), \\ \mathrm{rem}(n,d)&:=n-\mathrm{quot}(n,d)\cdot d, \\ \mathrm{div}(n,d)&:=\lfloor n/d\rfloor, \\ \mathrm{mod}(n,d)&:=n-\mathrm{div}(n,d)\cdot d \end{aligned}

quotとdivは商を返す関数、remとmodは余りを返す関数です。ここでの名前は(後述しますが)Standard MLとHaskellの流儀に沿ったものです。

余りの範囲は

\begin{aligned} 0&\le\mathrm{rem}(n,d)<\lvert d\rvert & \text{if \(n\ge 0\),} \\ -\lvert d\rvert&<\mathrm{rem}(n,d)\le 0 & \text{if \(n\le 0\),} \\ 0&\le\mathrm{mod}(n,d)<d & \text{if \(d>0\),} \\ d&<\mathrm{mod}(n,d)\le 0 & \text{if \(d<0\)} \end{aligned}

となります。\mathrm{mod}(n,d)の符号はdと同じ(または0)で、\mathrm{rem}(n,d)nと同じ符号(または0)です。

色々な言語での整数除算

いくつかの言語について、整数除算がどちらの流儀を採用しているかまとめてみました。

言語 quot / rem div / mod
C /, %, div
Java /, %
C# /, %
JavaScript (BigInt) /, %
Python //, %
Lua 5.3 //, %
Standard ML quot, rem div, mod
OCaml /, mod
Haskell quot, rem div, mod

C系の言語はquot / rem型が多いです。Standard MLとHaskellは両方提供しています。

両者の関係

n/d\ge 0またはd\mid ndnを割り切る)の場合はdiv, quotとrem, modはそれぞれ一致します。

n/d<0d\nmid ndnを割り切らない)の場合は\lfloor n/d\rfloor=\mathrm{trunc}(n/d)-1が成り立ちます。よって、

\begin{aligned} \mathrm{div}(n,d)&=\mathrm{quot}(n,d)-1, \\ \mathrm{mod}(n,d)%&=n-(\mathrm{quot}(n,d)-1)\cdot d \\ &=\mathrm{rem}(n,d)+d \end{aligned}

という関係となります。

quot / remでdiv / modを実装する

C系の言語でdiv / modの挙動が欲しくなったとします。divとmodを一気に計算する関数は次のように実装できます:

div_t divMod(int n, int d)
{
    assert(d != 0);
    assert(n != INT_MIN || d != -1); // 2の補数表現の場合、オーバーフローを起こす可能性がある
    // ちなみにC言語では2の補数表現の場合、 INT_MIN / (-1) だけでなく INT_MIN % (-1) もUBです
    int q = n / d;
    int r = n % d;
    if ((n >= 0 && d > 0) || (n <= 0 && d < 0) || r == 0) {
        return (div_t){.quot = q, .rem = r};
    } else {
        return (div_t){.quot = q - 1, .rem = r + d};
    }
}

条件 (n >= 0 && d > 0) || (n <= 0 && d < 0) がやや複雑です。符号が同じ(または0)ということなので、ビット演算を使って (n ^ d) >= 0 とできるかもしれません。(Luaの実装では実際にビット演算を使っているようです。)

div / modでquot / remを実装する

div / modがプリミティブとして用意されている言語でquot / remを一気に計算する関数は次のように実装できます:

def quotRem(n: int, d: int) -> tuple[int, int]:
    assert d != 0
    # 固定長整数の場合はオーバーフローの可能性がある
    q = n // d
    r = n % d
    if (n >= 0 and d > 0) or (n <= 0 and d < 0) or r == 0:
        return q, r
    else:
        return q + 1, r - d

他の流儀

ここでは商を0に向かって切り捨てるものと床関数で計算するものを扱いましたが、他にも「+\inftyに向かって切り上げる(天井関数)」、「最も近い整数に丸める(最近接偶数丸め)」などのバリエーションが考えられます。さらに、以下の論文

では「余りが常に非負になるようにする」流儀をユークリッド除算 (Euclidean division) と呼んで、それを推しています。

Scheme界隈の

では、上記の5つの他に、「余りが-\lvert d/2\rvert\le r<\lvert d/2\rvertを満たす」流儀(「商を最も近い整数に丸め」つつ、等距離の場合に余りを負に取る)を提案しています。

Discussion

紳士ぴんきー紳士ぴんきー

興味深い記事をありがとうございます。

一点質問です。
「余りの絶対値が常に非負になるようにする」という記述について。

「余りの値が~」などのように解釈してよろしいでしょうか。
自分の知っている絶対値は、そもそも常に非負の値をとるものです。
もしそうでない絶対値があるのならば、
簡単にで良いのでご教授いただけると幸いです。

だめぽだめぽ

これは私の書き間違いですね。「余りが常に非負になるようにする」が正しいです。ご指摘ありがとうございます。後で修正しておきます。

紳士ぴんきー紳士ぴんきー

素早く、礼儀正しい返信ありがとうございました。
今後とも記事を読ませていただきます。

余談ですが。
自分の知らない数学のジャンル
(もしくは数学の基礎理論の再編)があって
「負の値を取りうる絶対値」が存在するとしたら、
それは是非くわしく知りたいと考えてのコメントでした。
妙なコメント文ですいませんでした。

antimon2antimon2

参考までに。
Julia には整数除算関数・演算子は多数用意されています。

言語 quot/rem div/mod (other)
Julia ÷, %, div, rem fld, mod cld, fld1, mod1

演算子 ÷ は関数 div のエイリアスで、動きとしては trunc(a/b) と同様です。%rem のエイリアスです。
その他に fld("floor division" の意味)および cld("ceiling division" の意味)という関数が用意されており、それぞれ「-∞方向へ切り下げ」「+∞方向に切り上げ」です。fld1/mod1 は、この記事で言及されている「Euclidean division」の関数ですね。(2023/03/11 誤りがあったので訂正します、Euclidean Division とは無関係でした。mod10<{\rm mod1}(n,d) \le d \ {\rm if} \ d > 0, \ d \le {\rm mod1}(n,d) < 0 \ {\rm if} \ d < 0 を満たす剰余関数で、fld1 はそれに対応する除算関数({\rm mod1}(n,d) = n - ({\rm fld1}(n, d) - 1) * d)でした)。
なお / は整数どうしの除算でも結果は浮動小数点数になります。

さらに、div 関数は第3引数に丸めモードを指定することができ、どのように処理するかを細かく指定できます(RoundToZero(切り捨て、div のデフォルトの挙動)、RoundDown(切り下げ、fld 相当)、RoundUp(切り上げ、cld 相当)、RoundNearest(近接偶数丸め)、RoundNearestTiesAway(近接丸め四捨五入)、RoundNearestTiesUp(近接丸め切り上げ))。

詳しくは、Julia のマニュアル(Division functions - Mathematical Operations and Elementary Functions - The Julia Language, div - Mathematics - The Julia Language)や、(3/15 発売の)拙著書『実践Julia入門』第3章「3-1-1. 演算系(1) 除算・剰余算系」(pp157~163)を参照ください。

なおこのように細かく動きの分けられた関数・演算子が用意されているのは、Julia が数値計算を念頭に設計された言語であり、必要な演算の最適な実装を標準で用意し無駄な『車輪の再発明』をしなくて済むように考えられているからです。