两种取模运算

0x00 前言

最近在学离散数学,开始接触一点基础的数论知识。

在讲扩展欧几里得算法 (Extended Euclidean Algorithm)的时候,发现数学上用的取模运算和计算机语言普遍实现的算法不一样。

其实在很久以前,学Python的时候就有此疑问(Python实现的是数学上用的取模),但是由于我懒,我并没有深入理解这两种取模的具体细节,于是就有了这篇文章。

0x01 问题引入

如果你有幸学过C和Python,就应该清楚两种语言中的取模(%)的实现是不一样的,这种实现上的差异可以在操作数是负数的时候表现出来。

请看下面的两个例子:

mod.c
#include <stdio.h>
int main(void)
{
printf("%d", -8 % 7);
return 0;
}
mod.py
print(-8 % 7)

你会发现,这两个程序同样是在求8mod7-8 \bmod 7, 但是运行结果却不一样:

  • C语言的执行结果是1-1
  • Python的执行结果是66

这是为什么呢?(自问自答的屑

0x02 原因解析

原因是C语言和Python采用了不同的对于取模的定义:

  • C语言采用截断式取模(truncated modulus)
  • Python采用向下取整式取模(floor modulus)

我们知道,我们对于取模运算的定义是:

amodb=ab(a\b)a \bmod b = a - b \cdot (a \backslash b)

两种定义对于a\ba \backslash b的解释不同:

  • 截断式取模采用截断式整数除法,即直接截断小数位,只保留整数位
  • 向下取整式取模采用向下取整式整数除法,即先进行浮点除法,再对结果进行向下取整

这也是两种取模方式名称的由来。

0x03 结果验证

按照上述原理,我们可以验证上面的C代码和Python代码。

计算8mod7-8 \bmod 7

871.142857-\frac{8}{7} \approx -1.142857

截断式取模:

8mod7=87×(8\7)=87×(1)=1-8 \bmod 7 = -8 - 7 \times (-8 \backslash 7) = -8 - 7 \times (-1) = -1

向下取整式取模:

1.142857=2\lfloor-1.142857\rfloor = -2

8mod7=87×(8\7)=87×(2)=6-8 \bmod 7 = -8 - 7 \times (-8 \backslash 7) = -8 - 7 \times (-2) = 6

0x04 尾注

  1. 对于整除运算,C和Python中也采用相应的实现,即
    • C语言中,-8 / 7 == -1
    • Python中,-8 // 7 == -2
  2. 在一些资料中,截断式取模运算不叫作取模(modulus)运算,而叫做求余(remainder)运算,以与向下取整式取模运算区分。(有一些人还称后者为真·取模(true modulus)运算)
文章作者: wxx9248
文章链接: https://blog.wxx9248.tk/2021/02/15/Two-Types-of-Modulus/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 wxx9248 的博客