取模(Mod)运算应当是我们这个高精度运算类的最后一种运算了^ ^,长达一周的高精度整数运算的介绍的尾声也即将到来~后面部分我将重点介绍模运算,并对高精度整数运算类的最终成品做一点总结。
那么模运算究竟是什么呢?按照大家通俗的理解就是除法运算中剩下的尾巴——余数。其实却实可以这样理解,首先,我们来明确一下除法的表达:

A / B = [A / B] + R / B

[]运算代表向下取整,比如[1.6] = 1。那么[A / B]实际上就是我们做除法运算后所得到的“商”(其实如果商为负数的话,这样说是不合适的,我会在下文中具体解释),而R / B则是除法运算后面的浮点数部分(假如以后有机会做高精度浮点数的运算的话,用这个式子来求是很方便的哦~)。R则是我们这次的主角——模值。
经过整理,我们就可以得到取模运算在数学上的定义:

R = A – [A / B] * B

上面这个公式中所有的运算我们之前都已经完成过了,哈哈,看来代码也就是一行的事呀,可是,一次除法运算、一次乘法运算、一次减法运算……这三个都是相对较为复杂的运算拼在一起,似乎不是很好,回忆一下上一篇文章,特别是那张图,有没有发现,余数出现在了运算的中间过程,那么我只要直接把这个数字拿走,岂不是连完整的一次除法运算都不用就可以得到了么?等等,余数和模的概念还是有点区别的,比如说:

-31 % 4
23 % -7
-11 % -5

算式中出现了负数,但是不要紧,我们可以根据之前得到的公式得到运算的结果,但在计算之前,我要做一些说明:
这个公式在计算机中使用和实际数学上的使用是有差异的,差异就在于[]运算,这个运算的定义是:对于A,[A]为小于或等于A的整数的上界,通俗讲就是小于或等于A的第一个整数。这点上,和计算机的运算有所不同,计算机采用的“向下取整”策略是去除数字的浮点部分,对于[-1.6]来说,数学上的运算应为-2,但在计算机中,却是-1,这就导致了在出现负数的模运算的时候,计算机的运算结果会和数学上定义的模运算结果出现一个符号的差异,出于约定俗称的规则,我们这里的模运算依照的是计算机的规则,所以在应用计算机模运算的结果的时候,在有负数出现的情况下,数学上的一些性质就会失效,这点需要注意。下面文字中的[]运算,均为计算机中的“舍去取整”
按照计算机模运算的规则,三个模运算的结果分别是:

-2
2
-1

记得我们的所有运算都是基于正整数和正整数的么?也就是,我们在除法运算的中间过程中所得到的余数,是不会带符号的,我们需要人为的得到余数的符号,这样才能得到正确的模值。从上面的三个例子我们初步观察得到一个假设,即:被除数的符号和模的符号相同。
在这个假设的引导下,我们来证明:

A / B = [A / B] + R / B
R = A – [A / B] * B

1: A > 0, B < 0
∴A / B < 0, [A / B] < 0
=> [A / B] >= A / B
∴[A / B] * B <= A
∴0 <= A – [A / B] * B = R
R > 0

2: A < 0, B > 0
∴A / B < 0, [A / B] < 0
=> [A / B] >= A / B
∴[A / B] * B >= A
∴0 >= A – [A / B] * B = R
R < 0

3: A < 0, B < 0
∴A / B > 0, [A / B] > 0
=> [A / B] <= A / B
∴[A / B] * B >= A
∴0 >= A – [A / B] * B = R
R < 0

4: A > 0, B > 0
∴A / B > 0, [A / B] > 0
=> [A / B] <= A / B
∴[A / B] * B <= A
∴0 <= A – [A / B] * B = R
R > 0

综上:
R 的符号与 A 的符号相同。

至此,我们就可以复制粘贴除法运算的代码,并稍作修改,用作求模了:

高精度整数运算类的功能至此就算完备了,但这真的会是最终结果么?显然不是,我们在实现各种运算的时候使用的都是最简单的模拟手算的方法,然而这样做,效率可能并不高,在这个高精度整数运算类中,各种运算的时间复杂度是这样的,这是关于数字的位数的:

加法:O(n)
减法:O(n)
乘法:O(n^2)
除法:O(n^3)
取模:O(n^3)

乘法、除法以及取模运算的时间复杂度增长率实在是太高了,然而这些运算在需要高精度整数运算的一些应用中却又必不可少。事实上,我们有很多方法来提高这些运算的时间效率及空间效率,在时间上对于乘法来说,有二分法,或者目前最快的FFT(接近于n的时间复杂度增长率),这些算法都在实际应用中得到了广泛的应用。在空间上,我们可以使用N进制来存储数字(比如100000进制),这样可以充分利用我们的int类型的容器空间,并且也会一定程度减少时间复杂度的常量系数的大小(进制的提高可以缩短存储的位数,这大家都懂)。虽然这次对于高精度运算类的介绍已经要结束,但是我在未来的文章中,仍然会对其进行改进,并介绍那些著名的优化算法,同时也会给出一些实际应用的算法实例。
以下是完整版的高精度整数运算类的代码,我对其中一些冗余的代码进行的删除:

说点什么

3 评论 在 "高精度整数运算(7)模运算&总结"

  Subscribe  
最新 最旧 得票最多
提醒

原来bug多多

函数参数使用对象而不是对象的引用,意味着在函数被唤起执行之时,这些参数将被拷贝。
如果你的对象是一个含有容器的对象,那这么做意味着容器被复制一次。
想想看一个位数长达10^n的大整数做一次运算所要被复制的东西。