大数除的“伪O(1)”算法（类似小学算术）

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 大数除伪O（1）算法

? ? 前段时间在做计算器的大型实验，有一个版本要求大数运算，加减乘倒还好，除，觉得很难写。所以就在网上搜索了，不少博客，但是好像都是一个大数除以一个整数的方法，并没有大数除以大数的方法。总不能，用被减数一直减减数在那循环计数吧。遇到100000000000000000000/1这种极端情况，那还不得减到，猴年马月去！！

? ?后来，自己绞尽脑汁，想出来一种方法，觉得还不错，所以跟大家分享一下。

? ?直接描述有些抽象，那我就直接举个例子吧！

? ?比如，74811232478273232312332除以78233。

? ?其实，本质还是模仿减法。像（1）74811232478273232312332这个数，除以（2）78233很难算，但是我们可以除得大一点除以99999,，也就到了100000，结果非常明显，就是除去后5位的字符串，即（3）748112324782732323（删去12332）。这时，拿这个近似的解，即（3）重新反乘除数（2），得到一个非常接近原被除数的值，拿被除数减去这个值，得到一个剩余值（4）。然后再用循环去减减数，每减一次，循环计数加一，直至（4）小于等于0。最后将计数值加到（3）上即可。虽然看上去，复杂度降低了不少，但遇到像5894989289284928/11232这种情况，两数相减后，被减数位数可能减少很少，甚至不减少，复杂度仍降不下来。后来，想到了这个问题，又做了一点优化，可以利用循环不断地去模拟第一步，直至剩下来的数的值的位数达到和减数一样，或者小于减数，此时，只要再减上几遍，即可得到答案。

? ? 这样之后，似乎的确降到了O（1）的复杂度，其实不然，因为这其间还调用了大数除法，效率的高低，同时还取决于你写的乘法，故称，这种算法为“伪O（1）大数除法”。最常见，也是最低效的，大数乘法是模拟小学生数学，效率一般，比较高效的有以四位为单位计算，或者利用傅里叶变换计算。有兴趣的大神可自行研究，此处就不赘述了。至于，这个方法的实现代码，也并不是很难，看懂了的写起来应该没有什么问题，此处就不贴代码了

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 2014-12-01