2006-09-27
取余，真的那么简单吗？
关键字: 取余 数学 计算机 模计算 mod
取余的概述
取余 是一个比较常见的运算，在各种编程语言中均有相应的运算符（Java/C的%, Pascal/Delphi的mod等等），我们使用的也比较多，比如
问题的产生
这样一个问题： -3 % 2 = ? 我们可以使用这样一段Java程序来验证：
运行，结果是：
不过问题就在这：记得按照以前的数学书中的叙述，似乎不是这样的，于是将书翻了出来，在 Concrete Mathematics 的82页，看到：
也就是说，x mod y等于 x 减去 y 乘上 x与y的商的下界。于是，上面的-3 mod 2就变成了
奇怪的事情发生了。这个结果与上面程序计算得出的结果不一致。同样，我们使用Mathematics画出图像，来考察-5~5对2取余的情况：
在该图中，同样可以看出，-3对2取余的结果是1，而不是程序计算出来的-1。为何会有这样的结果呢？
程序计算结果原因分析
使用以下一段Delphi程序来考察：
编译后，查看汇编，关键的计算部分如下：
在上面的代码中，首先将-3赋值给eax(ecx为临时中间变量)，然后将2赋值给ebx，之后执行一条idiv指令。执行该指令后，商在eax中，余数在edx中。这样，与书上结论不一样的原因就出来了：按照书上的定义，应该首先做除法，得到浮点数，然后取其下界。如果附点数是正的，其下界相当与取整；如果浮点数是负的，相当于将小数部分抹去再减一，而idiv指令根本没有计算浮点并取下界的过程，所以造成与数学中的mod定义不一致。实际上，严格的说，我们在程序中使用的余数，其定义为：
这就是二者的区别。这个区别，对于正数，二者计算出的结果是相等的，但是负数就不相等了。这就意味着，如果以后在使用数学中余数相关定理的时候，要注意计算机中余数的计算和数学定义不是完全一致的，所以在计算机上，对于负数，数学定理并不完全适用。当然，对于正数，二者是没有区别的。至于为什么计算机上要这么实现，我想恐怕还是历史原因，最早的计算机如果这样计算除法（取余是靠除法来完成的），那么就涉及到浮点数的计算以及取下界，这样，将比较大的降低效率，所以实现成了这样的方式，一直沿用至今。
取余 是一个比较常见的运算，在各种编程语言中均有相应的运算符（Java/C的%, Pascal/Delphi的mod等等），我们使用的也比较多，比如
5 % 3 = 2, 10 % 2 = 0.
问题的产生
这样一个问题： -3 % 2 = ? 我们可以使用这样一段Java程序来验证：
System.out.println("result:" + (-3)%2);
运行，结果是：
result:-1
不过问题就在这：记得按照以前的数学书中的叙述，似乎不是这样的，于是将书翻了出来，在 Concrete Mathematics 的82页，看到：
也就是说，x mod y等于 x 减去 y 乘上 x与y的商的下界。于是，上面的-3 mod 2就变成了
奇怪的事情发生了。这个结果与上面程序计算得出的结果不一致。同样，我们使用Mathematics画出图像，来考察-5~5对2取余的情况：
在该图中，同样可以看出，-3对2取余的结果是1，而不是程序计算出来的-1。为何会有这样的结果呢？
程序计算结果原因分析
使用以下一段Delphi程序来考察：
var i,j,k:Integer; begin i:=-3; j:=2; k:=i mod j; ShowMessage(IntToStr(k)); end;
编译后，查看汇编，关键的计算部分如下：
Unit1.pas.30: i:=-3; 00486D84 B9FDFFFFFF mov ecx,$fffffffd Unit1.pas.31: j:=2; 00486D89 BB02000000 mov ebx,$00000002 Unit1.pas.32: k:=i mod j; 00486D8E 8BC1 mov eax,ecx 00486D90 99 cdq 00486D91 F7FB idiv ebx 00486D93 8BDA mov ebx,edx
在上面的代码中，首先将-3赋值给eax(ecx为临时中间变量)，然后将2赋值给ebx，之后执行一条idiv指令。执行该指令后，商在eax中，余数在edx中。这样，与书上结论不一样的原因就出来了：按照书上的定义，应该首先做除法，得到浮点数，然后取其下界。如果附点数是正的，其下界相当与取整；如果浮点数是负的，相当于将小数部分抹去再减一，而idiv指令根本没有计算浮点并取下界的过程，所以造成与数学中的mod定义不一致。实际上，严格的说，我们在程序中使用的余数，其定义为：
x - y(x div y)
这就是二者的区别。这个区别，对于正数，二者计算出的结果是相等的，但是负数就不相等了。这就意味着，如果以后在使用数学中余数相关定理的时候，要注意计算机中余数的计算和数学定义不是完全一致的，所以在计算机上，对于负数，数学定理并不完全适用。当然，对于正数，二者是没有区别的。至于为什么计算机上要这么实现，我想恐怕还是历史原因，最早的计算机如果这样计算除法（取余是靠除法来完成的），那么就涉及到浮点数的计算以及取下界，这样，将比较大的降低效率，所以实现成了这样的方式，一直沿用至今。
发表评论
chinakite
我的相册
共 4 张
最近加入圈子
最新评论
-
java.lang.NoClassDefFoun ...
是这样的,但是加包的时候还是有问题
-- by anlongstar -
取余，真的那么简单吗？
按照我这个晚上的研究你所说的在数学上的定义这个[x/y]在java中应该对应的是 ...
-- by cddcdd -
前天晚上冲动了一把
哈哈，有激情是好事！
-- by ouspec -
Java读取桌面路径的方法
多謝! 又學多了一個知識!
-- by 毛冬
评论排行榜