Guido van Rossum写了一篇博客文章,解释了为什么在Python中,整数除法(例如,a // b
)是"地板除法"——商四舍五入到负无穷大。相应地,a % b
的符号与b
的符号相匹配。
这与 C 不同,在 C 中,商四舍五入为零,a % b
的结果具有a
符号。
Python还使用楼层除法,相应的"模数匹配除数符号",用于浮点数。该博客文章声称这在某些情况下可能是不准确的(其中C的"模符号匹配分率符号"将是准确的)。这是真的吗?有没有具体的例子?
简介
下面的证明比我想要的要长,但这个问题已经好几天没有回答了,它应该得到一个答案。
在进入证明之前,让我直观地解决这个问题。如果我们定义模来返回x% y 的结果,该结果在 [−y/2, +y/2] 中(对于正 y),那么结果总是x或通过添加y的(正或负)倍数来减少。如果结果是x,则它是可表示的,因为x是以可表示的形式给出的。如果结果被简化,那么它必然是 y 中低数字的位置值的倍数,并且它的最大数字位置不大于y中的最大数字位置,因此它适合浮点格式并且是可表示的。
另一方面,如果我们定义模以返回 [0, y] 中的 x %y 的结果,则必须通过添加y来增加一个小的负x。当 x 较小时,它可能在比 y 更低的位置有数字,并且当它这样做时,添加 y 的结果必须在 x 的最低位置有一个非零数字,但它也必须在比小x更高的位置有一个非零数字(因为y在更高的位置添加一个数字)。因此,结果需要的位数多于浮点格式的位数,并且结果不可表示。
一个简单的例子是 −2−60% 1。数学结果是 1−2−60,但这不能仅用有效数中的 53 位表示;它需要位置值从 2−1到 2−60的位,这需要 60 位。
对称模是精确的
首先,让我们看看对称模的定义使得x% y 在 [−y/2, +y/2] 中,对于正y总是有一个可表示的结果。我也假设 x 是正数,但负 x 和/或负y的参数是对称的,x= 0 的结果是微不足道的。
x% y 被定义为 r,使得 r =x−q •y对于某个整数 q,通常我们在 r 或q上定义一些约束,以便r是唯一确定的(或者当结果在某个区间的端点处时,至少通常具有一定的灵活性唯一确定)。由于q是一个整数,如果x和y都是某个数字 g 的整数倍(可能是也可能不是整数),那么r也是g的整数倍。
在浮点格式中,数字使用符号、基数b(大于 1 的整数)、以b为基数的固定数p和指数e表示。表示的数字是 be× ±位数字。让我们将各个数字写为 d p−1 dp−2dp−3...d2d1d0.
考虑输入x和y。使用 xi表示用于表示 x 的基数b数字,使用 ex 表示用于表示 x 的指数,同样,对于y,我们有 x =xp−1...x0×bex和 y=yp−1...y0×bey.
请注意,x 和 y 都是 b ex和bey中较小者的倍数,因此r也必须是。
如果 b e y ≤ b ex,则r是bey的倍数。另外, |R|必然小于y。这意味着我们可以将r表示为rp−1±...r0× b e y —r足够小,这些带有指数 e y 的数字足够大以表示其值,并且因为它是bey的倍数,所以它不需要任何指数较小的数字。因此,r可以用浮点格式表示。
现在考虑 b ex<<em>bey。还假设 y 是归一化的,我们的意思是它的前导数字yp−1不为零。(如果为零,则通过减小其指数以将非零数字移动到前导位置来找到y的规范化表示。那么上述段落适用。如果 y 没有非零数字,则为零,并且未定义x%y。然后x<<em>y。在这种情况下,r要么是x 要么是x−y,因为这两个中的一个在 [−y/2, +y/2] 中。如果r是x,那么它是可表示的,因为x是可表示的。如果r是x − y,则x≥ 1/2y,并且|R|≤x.由于r是bex和 |R|<<em>x,我们必须能够将r表示为±rp−1...r0×bex.
不对称模可能不精确
上面的证明告诉我们,对称模是精确的,因为结果总是不变的x或x在幅度上减小到足以使所有必需的数字都适合浮点格式。这告诉我们如何打破模定义,使得 x % y 在 [0,y] 中:选择一个必须增加幅度的x。
我们有 y =yp−1...y0×bey.设y规范化,如上所述。对于x,选择任何负值、具有 e x