整除和取余是两个看起来非常简单明确的基本数学运算，但是在不同编程语言的实现中，其实存在着很多的差异，需要注意一下。

数论中的整除和取余

我们从这两个概念的数学定义出发，在数论中的整除和取余定义为：对于整数 \(a,b \in \mathbb{Z}\)，其中 \(b \neq 0\)，存在唯一的商 \(q\in \mathbb{Z}\) 和余数 \(r \in \mathbb{Z}\)，使得 \[ a = b \,q + r \] 对于余数要求 \(0 \le r < b\)，即余数是一个非负的且不超过除数的整数。

虽然初等数论主要关注的都是整数，通常不会涉及对实数的整除和取余运算，但是我们仍然可以直接将上述定义推广到实数中：对于实数 \(a,b \in \mathbb{R}\)，其中 \(b \neq 0\)，存在唯一的商 \(q\in \mathbb{Z}\) 和余数 \(r \in \mathbb{R}\)，使得 \[ a = b \,q + r \] 对于余数要求 \(0 \le r < b\)，即余数是一个非负的且不超过除数的实数。

数论中要求在任何情况下，商是一个整数，余数是一个非负的且绝对值不超过商的数。

计算机中的整除和取余

虽然在数论中已经提供了对于整数和实数在所有情况下的整除以及取余的定义，但是在计算机实践中并没有完全采纳这套定义，而是遵循了与之略微不同的规则， 在出现负数和出现浮点数的情况下，与数论中的定义会产生显著差异。 并且非常离谱的是，一共存在好几种候选的具体规则，不同的编程语言可能选择了不同的规则！

在计算机语言中，对于数 \(a,b\)（可能是整数或浮点数，这里不做区分），称满足如下要求的整数 \(q\) 和数 \(r\) 为商和余数 \[ a = b \,q + r, q \in \mathbb{Z}, |r| < |b| \] 注意：这里的要求比数论中定义更弱，它没有要求 \(r\) 非负。 事实上，这些要求不足以称为定义，因为在非整除的情况下，我们事实上可以找到两个满足要求的余数 \(r_1 < 0 < r_2\)，它们对应的商也不同，在数轴上这代表着在一个一般点两侧最靠近的两个整除点。到底选哪一个作为余数？我们必须明确说明这一点才能得到一个完整的定义。

考虑到对 \(a,b \in \mathbb{N}\) 习惯用法（也就是数论中的定义）的兼容性，我们希望满足：在 \(a,b>0\)时，选择的余数 \(r>0\)。 但是在其它情况下呢？通常有如下几种策略：（这里按照余数的选取策略进行了分类，实际上也可以按照商的选取策略进行分类）

  1. 要求 \(r\) 始终非负；
  2. 要求 \(r\) 的符号始终与被除数 \(a\) 一致；
  3. 要求 \(r\) 的符号始终与除数 \(b\) 一致；
  4. 要求 \(r\) 选择 \(r_1,r_2\) 中更靠近0的那个，也就是绝对值最小的那个。（这个并不能保证正整数整除的余数非负，通常只用于浮点数）

各种策略的示例如下表

取余策略 \(4 \div 3\) \((-4) \div 3\) \(4 \div (-3)\) \((-4) \div (-3)\)
余数符号非负（数论） 商 1, 余数 1 商 -2, 余数 2 商 -1, 余数 1 商 2, 余数 2
余数符号与被除数相同（截断除法） 商 1, 余数 1 商 -1, 余数 -1 商 -1, 余数 1 商 1, 余数 -1
余数符号与除数相同（向下整除） 商 1, 余数 1 商 -2, 余数 2 商 -2, 余数 -2 商 1, 余数 -1
余数绝对值最小化（误差最小化） 商 1, 余数 1 商 -1, 余数 -1 商 -1, 余数 1 商 1, 余数 -1

注：这个表格无法展示第二个和第四个策略的区别，把4改成2再进行测试，就可以观察到两者确实是不同的策略。

这几种策略都有各自的出发点和合理性，因此哪一个也无法占据绝对的主导地位：

  • 余数符号非负（数论）：保证余数符号非负的想法是最容易理解的，它是为了保持与数论中的定义一致。
  • 余数符号与被除数相同（截断除法）：在很多编程语言中实现的除法实际上都是截断除法 \(q = \text{trunc}(\frac{a}{b})\)，这里的截断是选取可表示的数集中最靠近 \(0\) 的数，即向 0 截断。这个做法导致我们始终会选择绝对值偏小的整数作为商，即选择靠近0的整除点来近似被除数，此时余数的符号就会和被除数保持一致。
  • 余数符号与除数相同（向下整除）：如果我们将整除定义为始终向下截断：\(q = \left[\frac{a}{b}\right]\)，这会导致\(q \le \frac{a}{b}\)，此时余数的符号会和除数保持一致。
  • 余数绝对值最小化（误差最小化）：这个可以保证 \(b\,q\) 作为 \(a\) 的最优近似，保证 \(b\,q\) 是可表示的数集中最靠近 \(a\) 的那个数。

值得注意的是，截断除法有一个独特的好处，在整除运算中可以直接将分子分母的负号提出来，满足 \[ (-a)/b = a/(-b) = -(a/b) \] 这可能是它被编程语言普通采用的原因之一。

编程语言中的实现

C/C++

对于两个整数之间的整除/和取余%，执行的策略都是截断除法，即保证余数符号与被除数相同，这也包括将其打包到一起的div函数。

对于浮点数之间则有两类实现：

  • fmod和std::fmod：保证余数符号与被除数相同；
  • remainder和std::remainder：保证余数的绝对值最小化。

MATLAB

常用的包括两个函数：

  • mod：返回的余数保证符号与除数相同；
  • rem：返回的余数保证符号与被除数相同。

Python

在Python中，整除//对应的策略是向下取整，例如 

1
2
3
print((-4)//3) # -2
print(4//(-3)) # -2
print((-4)//(-3)) # 1

%保证保证余数符号和除数一致（从而与//相匹配）。

在math和numpy模块中提供了很多工具：

  • numpy.mod：行为与内置的%一致，即保证余数符号和除数一致；（numpy.remainder是它的别名）
  • math.fmod，numpy.fmod：调用的是C语言中的fmod实现，即保持余数符号和被除数一致。

Mathematica

在Mathematica中的Mod函数采用的策略为：保证余数符号与除数一致。

小结

数学中的整除和取余的概念在计算机中并没有被完美地继承，而是根据具体情况采用了不同的实现，看起来比较混乱：

  • 截断除法可以保证余数的符号与被除数一致，并且运算中可以将符号提出，便于底层实现，因此在C/C++中被默认采用；
  • 保证余数的符号与除数一致的做法更适合于科学计算，一些高级语言例如Python，MATLAB和Mathematica默认选择了这种策略，但是它们也为其它策略（主要是C/C++所提供的截断除法）提供了对应的接口。

应用示例

在科学计算的编程实践中，我们通常需要在周期性的问题中对浮点数取余，以保证余数始终落在一个周期范围内， 我们可以保证作为除数的周期是正数，但是对于被除数却无法保证，并且我们希望得到的余数也是非负的，即保证余数的符号与除数相同。

我们考虑在不同语言中将x平移到 \([0,T]\) 周期中。

在C/C++中，如果希望使用fmod，因为fmod只能保证余数符号和被除数一致，我们必须加一个补丁来保证范围 

1
2
3
// [0,T]
x = std::fmod(x, T);
if (x < 0) {x += T;}

在MATLAB中，应该使用mod函数，例如 

1
2
% [0,T]
x = mod(x, T);

在Python中，我们不能直接使用C++的fmod在Python中的衍生品math.fmod和numpy.fmod，应该使用np.mod函数，例如 

1
2
# [0,T]
x = np.mod(x, T)