浮点数的"floor division"(例如在 Python 中)会导致不准确吗?



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 =xq •y对于某个整数 q,通常我们在 r 或q上定义一些约束,以便r是唯一确定的(或者当结果在某个区间的端点处时,至少通常具有一定的灵活性唯一确定)。由于q是一个整数,如果xy都是某个数字 g 的整数倍(可能是也可能不是整数),那么r也是g的整数倍。

在浮点格式中,数字使用符号、基数b(大于 1 的整数)、以b为基数的固定数p和指数e表示。表示的数字是 be× ±数字。让我们将各个数字写为 d p−1 dp−2dp−3...d2d1d0.

考虑输入xy。使用 xi表示用于表示 x 的基数b数字,使用 ex 表示用于表示 x 的指数,同样,对于y,我们有 x =xp−1...x0×bex和 y=yp−1...y0×bey.

请注意,x 和 y 都是 b exbey中较小者的倍数,因此r也必须是。

如果 b e y ≤ b ex,则rbey的倍数。另外, |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 要么是xy,因为这两个中的一个在 [−y/2, +y/2] 中。如果rx,那么它是可表示的,因为x是可表示的。如果rx − y,则x≥ 1/2y,并且|R|≤x.由于rbex和 |R|<<em>x,我们必须能够将r表示为±rp−1...r0×bex.

对称模可能不精确

上面的证明告诉我们,对称模是精确的,因为结果总是不变的x或x在幅度上减小到足以使所有必需的数字都适合浮点格式。这告诉我们如何打破模定义,使得 x % y 在 [0,y] 中:选择一个必须增加幅度的x

我们有 y =yp−1...y0×bey.y规范化,如上所述。对于x,选择任何负值、具有 e xbey的倍数(这意味着从 xey−1−exx0的至少一个数字不为零)。在某些情况下,y的前导数字为 1 并且从中借用,结果可能是可表示的。否则,它需要的最大数字位置与 y 的最大数字位置相同,并且它需要低于bey的数字,因此它不可表示。

相关内容

  • 没有找到相关文章

最新更新