1. osanshouo

    Posted

    osanshouo
Changes in title
+剰余演算の符号は「被除数と同符号」な言語が多い, ただし Python と Ruby を除く
Changes in tags
Changes in body
Source | HTML | Preview
@@ -0,0 +1,48 @@
+いままで何気なく剰余演算, 例えば `5.5 % 2.0 == 1.5` を書いてましたが, 実は結構危うかったので報告します. 本記事の内容は全部 [wikipedia](https://ja.wikipedia.org/wiki/%E5%89%B0%E4%BD%99%E6%BC%94%E7%AE%97) に載っているんですけどね.
+
+# 剰余演算
+
+2 つの正の数 $x$, $l$ (整数でも整数でなくてもよい) が与えられたとき
+$$x = n l + r$$
+を満たす非負の整数 $n$ と実数 $r \in [ 0, l )$ が一意に存在します. そこで $n$ を __商__ (quotient), $r$ を __剰余__ (remainder) と呼び, $r$ を $x \% l$ と書きます. また, 等式
+$$r = x \% l$$
+において $x$ を __被除数__ (dividend), $l$ を __除数__ (divisor) と呼びます. ここまでは人類の常識ですね.
+
+問題は, $x$ または $l$ が負の数を取り得るように剰余演算を拡張する際に生じます. つまり, 2 つのゼロでない数 $x$, $l$ が与えられたとき, やはり $n \in \mathbb{Z}$ および適当な区間 $I$ に含まれる $r$ を用いる一意的な表示
+$$x = n l + r$$
+が存在しますが, 「適当な区間」$I$ つまり剰余 $r$ の取り得る範囲はどのように設定すべきでしょうか?
+
+この問題に対する考えられる解答としては次の 4 パターンがあり得ます.
+
+* __常に正__: $r \in [ 0, | l | )$.
+* __除数と同符号__: $l > 0$ のとき $r \in [ 0, l )$, $l < 0$ のとき $r \in ( l, 0 ]$.
+* __被除数と同符号__: $x > 0$ のとき $r \in [ 0, | l | )$, $x < 0$ のとき $x \in (-|l|, 0 ]$.
+* __0 に近い側__: $r \in ( -|l|/2, |l|/2 ]$.
+
+どの選択肢を採用するかは純粋に定義/仕様の問題です. そして困ったことに, 言語ごとに仕様が異なるのです.
+
+
+# 整数型の場合
+
+`%` 演算子として提供される整数剰余演算は, 多くの言語で __被除数と同符号__ が採用されています. これには C/C++, Go, Java, JavaScript, Julia, OCaml, PHP, Rust などが含まれます. Fortran の `mod` 関数もそうです. しかし, そうでない言語も多くあります:
+
+* __除数と同符号__: Lua, Mathematica, Python, Ruby など.
+* Lisp, Prolog, Haskell, Julia: これらの言語はいずれも `mod` が除数と同符号, `rem` が被除数と同符号の演算になっています. なお Julia では `%` は `rem` の意味です.
+
+そう, __Python/Ruby と C/C++/Julia/Rust で仕様が違う__ のです. さらに言うと, これに伴って __除算の結果__ (上の記法では整数 $n$) も両グループ間で一致しないということになります. なぜならば, (整数の場合) 商 $n = x/l$ とは $x = n l + r$ を満たす整数 $n$ ですから, 剰余 $r$ が違えば商 $n$ も変わります. 実際, Python では `-3//2 == -2`, C/C++/Rust 等では `-3/2 == -1` になります.
+
+# 浮動小数点数の場合
+
+浮動小数点数に対しても演算子 `%` が定義されている言語は限られていますが Rust と Python, Julia ではちゃんと定義されていて, 整数型のときと同じ仕様になっています. なお C/C++ は `fmod`/`std::fmod` 関数がこの機能を提供します.
+
+# 補足
+
+* Python の `math.fmod` 関数は __被除数と同符号__ な剰余演算を提供します.
+* ゼロによる剰余 ($x\%0$) はゼロ除算と同じく定義されません. Rust で検証したところ, コンパイラが気づいたらコンパイルが通らず, 通ってしまった場合, 整数ならパニックし, 浮動小数点数なら NaN になりました. Python では整数/浮動小数点数どちらもエラーになります.
+
+# 参考文献
+
+* [剰余演算 - Wikipedia](https://ja.wikipedia.org/wiki/%E5%89%B0%E4%BD%99%E6%BC%94%E7%AE%97)
+* 先行研究その1: [C++における負の整数の割り算および余りについて](https://qiita.com/MusicScience37/items/e5dea9b0f31c60f9ffe7)
+* 先行研究その2: [余り(剰余)の性質をプログラムに活かす](https://qiita.com/yaju/items/aad350c6662d9d3b77cd)
+* 先行研究その3: [負数の剰余を計算してはならない](https://shunirr.hatenablog.jp/entry/20120409/1333993409)