Guido van Rossum写了一篇a blog post文章,解释了为什么在Python中整数除法(例如,a // b
)是“floor除法”——商被舍入到负无穷大相应地,a % b
的符号与b
的符号相匹配。
这与c不同,c的商是向零取整的,a % b
的结果有a
的符号。
python还使用floor除法,相应的“模符号与除数符号匹配”来表示浮点数。博客文章声称这在某些情况下是不准确的(其中C的“模匹配红利符号”是准确的)这是真的吗?有什么具体的例子吗?
最佳答案
介绍
下面的证据比我想的要长,但这个问题已经过了好几天没有得到答复,应该得到答复。
在进入证据之前,让我直观地解释一下。如果我们定义模来返回x%y的结果,该结果为~-y/2,+y/2(对于正y),则结果总是x或通过增加(正或负)y的倍数来减少。如果结果是x,则它是可表示的,因为x是以可表示的形式给出的。如果结果被减少,那么它必然是y中低位数字的位置值的倍数,并且它的最大数字位置不大于y中的最大数字位置,因此它适合浮点格式并且是可表示的。
另一方面,如果我们定义模来返回x%y在[0,y]中的一个结果,那么一个小的负x必须通过加y来增加。当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,使得对于某些整数q,r=x=q·y,并且通常我们定义R或Q上的一些约束,使得R被唯一地确定(或者,当结果在某个区间的端点时,通常至少通常具有唯一的灵活性)。因为q是一个整数,如果x和y都是某个数g的整数倍(可能是也可能不是整数),那么r也是g的整数倍。
在浮点格式中,数字用符号、基数B(大于1的整数)、基数B位数的固定数字P和指数E表示。所表示的数字是±位数×BE。我们把各个数字写成dp-1dp-2dp-3…d2d1d0。
考虑输入x和y。使用XI表示表示X的基数B数字,和X用于X表示的指数,同样地,对于Y,我们有x=XP×1…X0×BEX和Y= YP - 1…Y0×BEY。
注意x和y都是bex和bey中较小者的倍数,所以r也必须是。
如果bey≤bex,那么r是bey的倍数。而且,r必须小于y。这意味着我们可以将r表示为±rp−1…r0×bey-r足够小,以至于这些具有指数ey的数字足够大,可以表示其值,并且,因为它是bey的倍数,所以不需要任何具有较小指数的数字。因此,r可以用浮点格式表示。
现在考虑一下bex非对称模可能不精确
上面的证明告诉我们,对称模是精确的,因为结果总是x不变或x在数量上减少到足以使所有需要的数字都符合浮点格式这告诉我们如何打破模定义,使得x%y在[0,y]中:选择一个必须增加幅度的x。
我们有y=yp-1…y0×bey。如上所述,让y正规化。对于x,选择任何负值、ex