何时使用quotRem和divMod的差异有用？

Question

来自 Haskell 报告：

如果 y 非零，则 quot、rem、div 和 mod 类方法满足以下规律：

(x `quot` y)*y + (x `rem` y) == x
(x `div`  y)*y + (x `mod` y) == x

quot 是向零取整的整数除法，而 div 的结果是向负无穷取整。

例如：

Prelude> (-12) `quot` 5
-2
Prelude> (-12) `div` 5
-3

有哪些示例能够说明结果截断方式的差异很重要？

- grom

Answer 1

许多语言都有一个“mod”或“%”运算符，它可以在向0截断的除法后给出余数; 例如C、C++和Java，而且可能C#也是这样说的：

(-11)/5 = -2
(-11)%5 = -1
5*((-11)/5) + (-11)%5 = 5*(-2) + (-1) = -11.

Haskell 的 quot 和 rem 旨在模拟这种行为。我可以想象在某些人为情况下，与某些 C 程序的输出兼容可能是可取的。

Haskell 的 div 和 mod，以及随后 Python 的 / 和 %，遵循数学家（至少是数论学家）的约定，在除法时总是向下截断（不是朝0方向--而是朝负无穷大方向），以便余数始终是非负数。因此在 Python 中，

(-11)/5 = -3
(-11)%5 = 4
5*((-11)/5) + (-11)%5 = 5*(-3) + 4 = -11.

Haskell的div和mod遵循这种行为。

- ShreevatsaR

---

技术上，mod 的符号遵循第二个操作数的符号，以使余数始终为非负数。 - newacct

保持性质：当且仅当 x = q*y + r 时，(q,r) = divMod x y。运行一个示例，它的工作原理很巧妙。 - luqui

@luqui：不是这样解释的。你总是可以有 x=qy+r，其中 r 是非负数；例如，如果 divMod 11 (-5) = (-2, 1)（而不是 (-3,-4)），你仍然有 "11 = (-2)(-5) + 1"。因此，你的条件并不强制 mod 的符号遵循第二个操作数。顺便说一下，x=q*y+r 这个性质对 quotRem 也总是成立的，总是存在无限多个 (q,r) 对使得 x=q*y+r 成立（当且仅当 r=0 时只有一个解，除此之外恰好有两个解满足 |r|<q）。 - ShreevatsaR

嗯，也许 mod 是在弥补 div 中某些相关设计决策的影响？不太确定... - luqui

实际上，虽然C99和C++11确实指定了截断为0的定义，但早期版本则将其定义为实现定义，因此“与C兼容”不太可能（或至少是不好的）是其他语言或程序采用截断为0的原因。 - abarnert

但在Python中，11％-5 == -4，结果为负数。当被除数> 0且除数< 0时，如何符合“数学家的惯例”，然后a％b为<0？ - Rick

Answer 2

这并不是对您问题的直接回答，但在x86的GHC上，对Int类型进行quotRem运算会编译为单个机器指令，而divMod需要更多的运算。因此，如果您处于速度关键的部分，并且只处理正数，那么使用quotRem是更好的选择。

- luqui

---

为了解决SPOJ primes问题，使用rem而不是mod使得我的测试文件在32位Ubuntu，Haskell Platform 2011下运行时间从5.533秒缩短到了4.758秒。这意味着更快的版本比原来快了16%。 - Tim Perry

@TimPerry，我不认为这是正确的。如果你在整个程序中只做了一个mod操作，并且看到了同样的改进，那该怎么办呢？ - luqui

我曾经说过，当我将我的质数代码中的mod调用更改为rem时，我看到了20%的加速。这不是一个理论性的评论，而是对一个事件的描述。我只改变了一件事情（虽然在多个地方），但我看到了20%的加速。似乎20%的加速确实发生了。 - Tim Perry

@TimPerry 啊，我以为“更快的版本”是指 rem，而不是你修改后的程序。（虽然我不确定为什么我会认为如果你是这个意思，你就不会直接说 rem...） - luqui

在许多架构中，包括x86，在除以非常数时，使用朝零舍入截断除法比向负无穷舍入截断除法略快，但是当除以许多常数值，特别是2的幂时，朝零舍入截断要快得多（例如一条指令与3条指令相比）。我认为，对速度敏感的代码往往会有更多的“快速”除法而不是慢速除法。 - supercat

Answer 3

一个简单的例子，在测试一个整数是偶数还是奇数时，就显得很重要。

let buggyOdd x = x `rem` 2 == 1
buggyOdd 1 // True
buggyOdd (-1) // False (wrong!)

let odd x = x `mod` 2 == 1
odd 1 // True
odd (-1) // True

今日免费次数已满, 请开通会员/明日再来

let odd x = x `rem` 2 /= 0
odd 1 // True
odd (-1) // True

总的来说，请记住，对于 y > 0，x mod y 总是返回大于等于 0 的值，而 x rem y 返回 0 或与 x 同号的值。

- namin