Python 选择将整数除法舍入为负无穷大背后的数学原因是什么?

What's the mathematical reason behind Python choosing to round integer division toward negative infinity?

我知道 Python // 向负无穷大舍入,在 C++ 中 / 被截断,向 0 舍入。

这是我目前所知道的:

               |remainder|
-12 / 10  = -1,   - 2      // C++
-12 // 10 = -2,   + 8      # Python

12 / -10  = -1,     2      // C++
12 // -10 = -2,   - 8      # Python

12 / 10  = 1,      2       // Both
12 // 10 = 1,      2

-12 / -10 = 1,    - 2      // Both
          = 2,    + 8

C++:
1. m%(-n) == m%n
2. -m%n == -(m%n)
3. (m/n)*n + m%n == m

Python:
1. m%(-n) == -8 == -(-m%n)
2. (m//n)*n + m%n == m

但为什么 Python // 选择向负无穷大舍入?我没有找到任何资源来解释这一点,但只找到并听到人们含糊地说:“出于数学原因”.

例如,在Why is -1/2 evaluated to 0 in C++, but -1 in Python?中:

People dealing with these things in the abstract tend to feel that rounding toward negative infinity makes more sense (that means it's compatible with the modulo function as defined in mathematics, rather than % having a somewhat funny meaning).

但我没有看到 C++ 的 / 与模函数不兼容。在 C++ 中,(m/n)*n + m%n == m 也适用。

那么 Python 选择向负无穷大舍入的(数学)原因是什么?


另见 Guido van Rossum's old blog post on the topic

尽管我无法提供 why/how 的 正式 定义,但仍按原样选择了舍入模式,有关与 % 兼容性的引用当您认为 % 不是 相当 C++ 和 Python.

在 C++ 中,它是 remainder 运算符,而在 Python 中,它是 modulus 运算符 – 和,当两个操作数具有 不同的 符号时,它们不一定是同一件事。在以下答案中对这些运算符之间的区别有一些很好的解释:What's the difference between “mod” and “remainder”?

现在,考虑到这种差异,整数除法的舍入(截断)模式必须与两种语言中的相同,以确保您引用的关系,(m/n)*n + m%n == m,仍然有效。

这里有两个简短的程序演示了这一点(请原谅我的代码有点天真 Python – 我是该语言的初学者):

C++:

#include <iostream>

int main()
{
    int dividend, divisor, quotient, remainder, check;
    std::cout << "Enter Dividend: ";                        // -27
    std::cin >> dividend;
    std::cout << "Enter Divisor: ";                         // 4
    std::cin >> divisor;

    quotient = dividend / divisor;
    std::cout << "Quotient = " << quotient << std::endl;    // -6
    remainder = dividend % divisor;
    std::cout << "Remainder = " << remainder << std::endl;  // -3

    check = quotient * divisor + remainder;
    std::cout << "Check = " << check << std::endl;          // -27
    return 0;
}

Python:

print("Enter Dividend: ")             # -27
dividend = int(input())
print("Enter Divisor: ")              # 4
divisor = int(input())
quotient = dividend // divisor;
print("Quotient = " + str(quotient))  # -7
modulus = dividend % divisor;
print("Modulus = " + str(modulus))    # 1
check = quotient * divisor + modulus; # -27
print("Check = " + str(check))

请注意,对于不同符号(-27 和 4)的给定输入,商和 remainder/modulus 在语言之间是不同的 但也两种情况下恢复的 check 值都是正确的 .

But why Python // choose to round towards negative infinity?

我不确定 最初做出此选择的原因是否在任何地方都有记录(尽管据我所知,它可以在某些 PEP 中进行详细解释某个地方),但我们当然可以想出各种理由来解释它。

一个原因很简单,向负(或正!)无穷大舍入意味着所有数字都以相同的方式舍入,而向零舍入使零变得特殊。数学上的说法是,向 −∞ 向下舍入是 平移不变 ,即它满足方程:

round_down(x + k) == round_down(x) + k

对于所有实数 x 和所有整数 k。不向零舍入,因为,例如:

round_to_zero(0.5 - 1) != round_to_zero(0.5) - 1

当然,也存在其他论点,例如您根据与 % 运算符(表现)的兼容性(我们希望如何)引用的论点——更多内容见下文。

的确,我想说 真正的 问题是为什么 Python 的 int() 函数是 而不是 定义为将浮点参数舍入到负无穷大,因此 m // n 等于 int(m / n)。 (我怀疑是“历史原因”。)再一次,这没什么大不了的,因为 Python 至少有 math.floor() 确实满足 m // n == math.floor(m / n).


But I don't see C++ 's / not being compatible with the modulo function. In C++, (m/n)*n + m%n == m also applies.

是的,但是在 / 向零舍入的同时保留该身份需要以一种笨拙的方式为负数定义 % 。特别是,我们失去了 Python 的 % 的以下两个有用的数学性质:

  1. 0 <= m % n < n 所有 m 和所有正面 n;和
  2. (m + k * n) % n == m % n 对于所有整数 mnk

这些属性很有用,因为 % 的主要用途之一是将数字 m“环绕”到有限的长度范围 n


例如,假设我们正在尝试计算方向:假设 heading 是我们当前的 compass heading 度数(从正北顺时针计算,0 <= heading < 360)和我们想要在转动 angle 度后计算我们的新航向(如果我们顺时针转动 angle > 0,或者如果我们逆时针转动 angle < 0)。使用 Python 的 % 运算符,我们可以简单地计算出我们的新航向:

heading = (heading + angle) % 360

这在所有情况下都有效。

但是,如果我们尝试在 C++ 中使用这个公式,使用它不同的舍入规则和相应不同的 % 运算符,我们会发现环绕并不总是按预期工作!例如,如果我们开始面向西北 (heading = 315) 并顺时针旋转 90° (angle = 90),我们最终确实会面向东北 (heading = 45)。但是,如果然后 尝试逆时针转回 90° (angle = -90),使用 C++ 的 % 运算符,我们将不会在 heading = 315 处结束,因为预期,而是 heading = -45!

要使用 C++ % 运算符获得正确的环绕行为,我们需要将公式编写为:

heading = (heading + angle) % 360;
if (heading < 0) heading += 360;

或如:

heading = ((heading + angle) % 360) + 360) % 360;

(更简单的公式 heading = (heading + angle + 360) % 360 只有在我们始终保证 heading + angle >= -360 时才有效。)

这是您为除法的非平移不变舍入规则以及非平移不变 % 运算符付出的代价。

整数和实数算术都定义了它们的除法运算符,因此以下两个等式都适用于 n 和 d 的所有值。

(n+d)/d = (n/d)+1
(-n)/d = -(n/d)

不幸的是,整数算术不能以两者都成立的方式定义。对于许多用途,第一个等价比第二个更有用,但在代码将两个值相除的大多数情况下,以下其中一个适用:

  1. 两个值都是正数,在这种情况下第二个等价无关紧要。

  2. 被除数是除数的精确整数倍,在这种情况下两个等价可以同时成立。

从历史上看,处理涉及负数的除法最简单的方法是观察是否正好有一个操作数为负数,删除符号,执行除法,如果只有一个操作数为负数,则使结果为负数。这将在两种常见情况下都符合要求,并且比使用在所有情况下都支持第一个等价的方法更便宜,而不是仅当除数是股息的精确倍数时。

Python 不应该被视为使用劣质语义,而是决定在重要的情况下 通常更好的语义 值得稍微划分一下更慢即使在精确语义无关紧要的情况下

"for mathematics reasons"

考虑以下问题(在视频游戏中很常见),您的 X 坐标可能为负,并希望将其转换为图块坐标(假设 16x16 图块)和图块内的偏移量

Python的%直接给你偏移量,/直接给你平铺:

>>> -35 // 16 # If we move 35 pixels left of the origin...
-3
>>> -35 % 16 # then we are 13 pixels from the left edge of a tile in row -3.
13

(并且 divmod 同时给你两个。)

Python's a // b = floor(a/b) 采用标准 (ASCII) 数学符号。 (在德国,高斯的符号 [x] 对 floor(x) 很常见。) floor 函数非常流行(经常使用 ⇔ 很有用;google 看数百万个例子)。首先可能是因为它简单自然:“最大整数≤x”。因此,它具有许多很好的数学特性,例如:

  • 按整数 k 翻译:floor(x + k) = floor(x) + k。
  • 欧几里德除法:x = y · q + r 且 0 ≤ r < q := floor(x/y) 对于给定的 x 和 y。

我能想到的“向零舍入”函数的任何定义都将更加“人为”并且涉及 if-then(可能隐藏在绝对值 |.| 或类似物中)。我不知道 任何 数学书介绍了“向零舍入”函数。这已经是采用这个约定而不是另一个约定的充分理由。

我不会在其他答案中详述的“与模运算的兼容性”论点上长篇大论,但必须提及它,因为它当然也是一个有效论点,并且它与上面的“翻译”公式相关联。例如在三角函数中,当你需要角度模 2 π 时,你肯定需要这个除法。

这里,整数除法运算符写div,整数除法运算符写mod 余数运算符。

divmod 必须定义为,对于 ab 具有非零 b 的整数,我们有

a == (a div b)*b + (a mod b)

通常您希望 mod 结果始终介于 0(含)和 b(不含)之间,而不管 a 的符号如何。例如,a 可以是循环缓冲区的索引,而 b 可以是它的(正)大小。然后 a mod b 可以用作底层内存数组的索引,即使 a 为负数。事实上,使用 a == -1 来引用最后一个缓冲区元素非常流行。

这可能是 Python 将商舍入为负无穷大的原因。因此,无论被除数的符号如何,余数要么为零,要么具有除数的符号。这是固定除数的基于字母的图:

   ^ y = x mod 5
 4 |   *    *    *    *    *
   |  *    *    *    *    *
   | *    *    *    *    *    *
   |*    *    *    *    *    *
 0 +----*----*----*----*----*->
       -5    0    5   10   15 x

在C/C++中,事情变得有点复杂,因为整数的宽度有限。

假设a == INT_MIN,在补码表示中是2的负幂,b == 3。如果我们舍入商使得 a mod b > 0,那么 (a div b)*b 必须小于 INT_MIN,这将构成有符号整数溢出。然后效果将由实现定义。机器甚至可以中断执行,例如使用 GCC 的 -ftrapv 选项编译时。但是将整数除法和取余运算的行为具体化的基本原理是为了消除这种不确定性。

因此,C/C++ 剩下的唯一选择就是将商数舍入为零。因此,余数如果不为零,则具有被除数的符号。

缺点是固定除数的图看起来不太规则:

   ^ y = x mod 5
 4 |             *    *    *
   |            *    *    *
   |           *    *    *    *
   |          *    *    *    *
 0 |    *    *    *    *    *
   |   *    *
   |  *    *
   | *    *
-4 |*    *
   +----+----+----+----+----+->
       -5    0    5   10   15 x

因此,mod buffer-size 不会像我们希望的那样处理负索引值。在编程方面,我不喜欢这个决定,尽管我可以理解即使在极端情况下也要实现 a == (a div b)*b + (a mod b) 的基本原理。

But why Python // choose to round towards negative infinity?

根据 python-history.blogspot.com Guido van Rossum// 选择了这种行为,因为

(...)there is a good mathematical reason. The integer division operation (//) and its sibling, the modulo operation (%), go together and satisfy a nice mathematical relationship (all variables are integers):

a/b = q with remainder r

such that

b*q + r = a and 0 <= r < b

(assuming a and b are >= 0).

If you want the relationship to extend for negative a (keeping b positive), you have two choices: if you truncate q towards zero, r will become negative, so that the invariant changes to 0 <= abs(r) < otherwise, you can floor q towards negative infinity, and the invariant remains 0 <= r < b(...) In mathematical number theory, mathematicians always prefer the latter choice (...). For Python, I made the same choice because there are some interesting applications of the modulo operation where the sign of a is uninteresting. Consider taking a POSIX timestamp (seconds since the start of 1970) and turning it into the time of day. Since there are 24*3600 = 86400 seconds in a day, this calculation is simply t % 86400. But if we were to express times before 1970 using negative numbers, the "truncate towards zero" rule would give a meaningless result! Using the floor rule it all works out fine. Other applications I've thought of are computations of pixel positions in computer graphics. I'm sure there are more.

所以总结 // 行为选择是因为它与 % 行为保持一致,之所以选择后者是因为它在处理负面(1970 年开始之前)时间戳和像素方面很有用.

Python 选择将整数除法舍入为负无穷大背后的数学原因是它是数学上最一致的选项。在 Python 中,当您将两个整数相除时,结果将始终是一个浮点数。该数字将四舍五入为最接近的整数,正数向上舍入,负数向下舍入。这种一致的舍入行为导致向负无穷大行为舍入。

Python 向负无穷大舍入整数除法背后的数学原因是它给出的结果比向正无穷大舍入更一致。例如,考虑以下两个表达式:

3 / 4

-3 / 4

第一个表达式将产生值 0.75,而第二个表达式将产生值 -0.75。这是因为第一个表达式向正无穷大舍入,而第二个表达式向负无穷大舍入。