为什么整数除法在许多脚本语言中会向下舍入?

Why does integer division round down in many scripting languages?

在我测试过的语言中,- (x div y )不等于-x div y;我已经在 Python 中测试了 //,在 Ruby 中测试了 /,在 Perl 6 中测试了 divC has a similar behavior.

该行为通常符合规范,因为 div 通常定义为 the rounding down of the result of the division, however it does not make a lot of sense from the arithmetic point of view, since it makes div behave in a different way depending on the sign, and it causes confusion such as

这个设计决定背后是否有一些特定的理由,或者只是 div 从头开始​​定义的?显然 Guido van Rossum uses a coherency argument 在一个博客 post 中解释了它是如何在 Python 中完成的,但是如果你选择四舍五入,你也可以有一致性。

(灵感来自 this question by PMurias in the #perl6 IRC channel

因为整数除法的含义是完整答案包括余数。

正如宝拉所说,是因为余数。

该算法基于Euclidean division

在Ruby中,你可以写出这个重建股息的一致性:

puts (10/3)*3 + 10%3
#=> 10

在现实生活中也是一样的。 10 个苹果和 3 个人。好吧,你可以把一个苹果切成三个,但要超出设定的整数。

对于负数也保持一致性:

puts (-10/3)*3 + -10%3 #=> -10
puts (10/(-3))*(-3) + 10%(-3) #=> 10
puts (-10/(-3))*(-3) + -10%(-3) #=> -10

商总是向下取整(沿负轴向下),提示如下:

puts (-10/3) #=> -4
puts -10%3 #=> 2

puts (10/(-3)) #=> -4
puts 10%(-3) # => -2

puts (-10/(-3)) #=> 3
puts -10%(-3) #=> -1 

理想情况下,我们希望有两个操作 divmod,满足每个 b>0:

  1. (a div b) * b + (a mod b) = a
  2. 0 <= (a mod b) < b
  3. (-a) div b = -(a div b)

然而,这在数学上是不可能的。如果以上都成立,我们将有

1 div 2 = 0
1 mod 2 = 1

因为这是 (1) 和 (2) 的唯一整数解。因此,根据 (3),我们也会有

0 = -0 = -(1 div 2) = (-1) div 2

根据 (1),这意味着

-1 = ((-1) div 2) * 2 + ((-1) mod 2) = 0 * 2 + ((-1) mod 2) = (-1) mod 2

使得 (-1) mod 2 < 0 与 (2) 相矛盾。

因此,我们需要放弃(1)、(2)、(3)中的一些属性。

一些编程语言放弃了(3),并使div向下舍入(Python,Ruby)。

在某些(极少数)情况下,该语言提供多个除法运算符。例如,在Haskell中我们有div,mod只满足(1)和(2),类似于Python,我们也有quot,rem只满足(1)和( 3).后一对运算符将除法 舍入到零 ,代价是 return 负余数,例如,我们有 (-1) `quot` 2 = 0(-1) `rem` 2 = (-1)

C#也放弃了(2),允许%到return一个负余数。连贯地,整数除法向零舍入。 Java、Scala、Pascal、C,从C99开始,也是采用这种策略。

浮点运算由 IEEE754 定义,考虑到数字应用,默认情况下,以非常严格定义的方式舍入到最接近的可表示值。

计算机中的整数运算不是通用国际标准定义的。语言(尤其是 C 系列语言)授予的操作倾向于遵循底层计算机提供的任何内容。有些语言定义的某些操作比其他语言更稳健,但为了避免在当时可用(和流行)的计算机上实现过于困难或缓慢,将选择一个非常接近其行为的定义。

因此,整数运算倾向于 环绕 溢出(对于加法、乘法和左移),并且 向负无穷大舍入 当产生不精确的结果时(除法和右移)。 这两个都是简单的截断在二进制补码运算中整数各自的末端;处理极端情况的最简单方法。

其他答案讨论了语言可能与除法一起提供的余数或模数运算符的关系。不幸的是,他们倒退了。 余数取决于除法的定义,而不是相反,而模数可以独立于除法定义 - 如果两个参数都为正并且除法四舍五入,则结果为一样,所以很少有人注意到。

大多数现代语言都提供余数运算符或模数运算符,很少同时提供。一个库函数可能会为关心差异的人提供另一种操作,即余数保留被除数的符号,而模数保留除数的符号。

Wikipedia has a great article on this,既有历史也有理论。


只要一种语言满足欧几里德除法属性即(a/b) * b + (a%b) == a,flooring除法和截断除法都是连贯的并且在算术上是合理的。


当然人们喜欢争论一个明显正确另一个明显错误,但它更多的是圣洁的war而不是理智的讨论,而且通常更多地与选择他们早期首选的语言比什么都重要。他们也经常倾向于主要为他们选择的 % 争论,尽管先选择 / 然后再选择匹配的 % 可能更有意义。

  • 地板(如Python):
    • 不亚于 Donald Knuth 的权威建议。
    • % 后面的除数符号显然是所有学生中大约 70% 的猜测
    • 运算符通常读作modmodulo而不是remainder
    • "C does it"——这甚至不是真的。1
  • 截断(如 C++):
    • 使整数除法与 IEEE 浮点数除法更加一致(默认舍入 mode)。
    • 更多的 CPU 实现了它。 (历史上不同时期可能不正确。)
    • 运算符被读作modulo而不是remainder(尽管这实际上反对他们的观点)。
    • 除法 属性 在概念上更多地是关于余数而不是 modulus。
    • 运算符读作mod而不是modulo,所以应该遵循Fortran的区分。 (这听起来可能很傻,但可能是 C99 的关键。参见 this thread。)
  • "Euclidean"(就像 Pascal——/ 楼层或截断取决于符号,所以 % 永远不会是负数):
    • Niklaus Wirth 认为,没有人会对积极的 mod 感到惊讶。
    • Raymond T. Boute 后来争辩说,您不能天真地使用其他任何规则来实现欧几里德除法。

许多语言同时提供这两种功能。通常——如在 Ada、Modula-2、一些 Lisp、Haskell 和 Julia 中——它们使用与 mod 相关的名称作为 Python 风格的运算符,并使用 rem 作为C++ 风格的运算符。但并非总是如此——例如,Fortran 调用相同的东西 modulomod(如上文针对 C99 所述)。


不知道为什么Python,Tcl、Perl等有影响力的脚本语言大多选择flooring。如问题中所述,Guido van Rossum 的回答仅解释了为什么他必须选择三个一致答案之一,而不是为什么他选择了他所做的那个。

但是,我怀疑 C 的影响是关键。大多数脚本语言(至少最初)是用 C 实现的,并从 C 中借用了它们的运算符库存。C89 的实现定义 % 显然已损坏,并且不适合 "friendly" 语言,如 Tcl 或 Python。 C调用运算符"mod"。所以他们使用 modulus,而不是 remainder。


1.不管这个问题怎么说——而且很多人用它作为论据——C 实际上 有与 Python 和朋友相似的行为。 C99 需要截断除法,而不是地板。 C89 允许,也允许 mod 的任一版本,因此不能保证除法 属性,并且无法编写可移植代码来执行有符号整数除法。那只是坏了。

此答案解决了 sub-part 其他(优秀)答案未明确解决的问题。您注意到:

you can have coherency also if you choose to round up.

其他答案解决了向下舍入(向 -∞)和截断(向 0 舍入)之间的选择,但没有比较向上舍入(向∞)。

涉及性能原因,更喜欢在双 s-complement 机器上舍入,这也适用于舍入。但是还有更多避免四舍五入的重要语义原因。)

这个答案直接解决了为什么四舍五入不是一个很好的解决方案。

四舍五入打破了 elementary-school 预期

中的示例为基础,通常非正式地说如下:

If I evenly divide fourteen marbles among three people, each person gets four marbles and there are two marbles left over.

的确,这是多少学生第一次被教除法(在被介绍给fractions/decimals之前)。一个学生可能会写 14 ÷ 3 = 4 remainder 2。由于引入时间太早,我们非常希望我们的 div 运算符保留此 属性.

或者,更正式地说,在 中讨论的三个属性中,第一个 ((a div b) × b + (a mod b) = a) 是迄今为止最重要的。

但是四舍五入打破了这个 属性。如果 div 向上舍入,则 14 div 3 returns 5。这意味着上面的等式可以简化为 15 + (13 mod 4) = 13——而对于 modany 定义则不是这样。同样,less-formal/elementary-school 方法也不走运——或者至少需要引入负弹珠:“每个人得到 5 个弹珠,还剩下负 1 个弹珠”。

(四舍五入到最接近的整数也会打破 属性,如上例所示,这意味着四舍五入。)

因此,如果我们想保持基本期望,我们不能四舍五入。通过四舍五入 table,您在问题中链接的 coherency argument 足以证明四舍五入是合理的。