ほとんどの数学の学生と Haskeller がよく知っているユークリッド除算定理は、次のように述べています。
2 つの整数 a と b が与えられ、b ≠ 0 の場合、a = bq + r かつ 0 ≤ r < |b| となる一意の整数 q と r が存在します。
これにより、商と剰余の従来の定義が得られます。この1992 年の論文は、それらがプログラミング言語で実装するのに最適なものであると主張しています。divModでは、被除数を常に負の無限大に丸めるのはなぜでしょうか?
div と quot の正確な違いdivModは、すでにかなりの余分な作業を行っていることを示していquotRemます。それを正しくするのはそれほど難しいことではないようです。
コード
divModの実装に基づいて、次のユークリッド スタイルの実装を作成しましたGHC.Base。私はそれが正しいと確信しています。
divModInt2 :: Int -> Int -> (Int, Int)
divModInt2 (I# x) (I# y) = case (x `divModInt2#` y) of
divModInt2# :: Int# -> Int# -> (# Int#, Int# #)
x# `divModInt2#` y#
| (x# <# 0#) = case (x# +# 1#) `quotRemInt#` y# of
(# q, r #) -> if y# <# 0#
then (# q +# 1#, r -# y# -# 1# #)
else (# q -# 1#, r +# y# -# 1# #)
| otherwise = x# `quotRemInt#` y#
これは心地よいユークリッドの結果を生み出すだけでなく、実際には GHC コードよりも単純です。明らかに、多くても 2 回の比較を実行します (GHC コードの 4 回とは対照的に)。
実際、これはおそらく、私よりもプリミティブについて詳しい人が手を加えなくても、完全にブランチレスにすることができます。
ブランチのないバージョンの要点 (おそらく、もっと詳しい人ならもっと効率的にできるはずです)。
x `divMod` y = (q + yNeg, r - yNeg * y - xNeg)
where
(q,r) = (x + xNeg) `quotRem` y
xNeg = fromEnum (x < 0)
yNeg = xNeg*(2 * fromEnum (y < 0) - 1)