高精度整数问题.ppt

高精度整数问题,组合数和Catalan的精确计算,福州大学04计算机(3)班 王建南 学号：030402332,算法与数据结构第二次作业解题报告,问题描述,编一个大整数模板类，用来做高精度整数（也就是任意位数的整数）的四则运算，包括 加法（addition）减法（subtraction）乘法（multiplication）除法（division）利用上面设计的大整数模板类精确地计算组合数和Catalan数。,大整数的介绍,在某些情况下(如数据加密和科学计算等方面)，我们要处理很大的整数，它无法在计算机硬件能直接表示的范围内进行处理。若用浮点数来表示它，则只能近似地表示它的大小，计算结果中的有效数字也受到限制(如C+中的Double类型有效位只有15位)。若要精确地表示大整数并在计算结果中要求精确地得到所有位数上的数字，就必须用软件的方法来实现大整数的算术运算。,需要解决的问题,大整数的表示 在利于编程实现，同时便于提高运算效率的基础上选择数据结构。这个主要是考查数据结构。我们将会发现，在数据结构上的一个小改进对效率的提高有时会有很大帮助的。而数据结构在一定程度上是可以弥补算法的不足的。大整数的运算 利用所选的数据结构，正确、高效地实现整数的四则运算。这主要考查算法。我们可以看到算法的选择对程序的效率是有绝对影响的。算法是决定程序效率的根本。,大整数的表示,由于大整数的位数太多，我们首先要做的是把它“拆”开来，放在若干个地方，然后建立不同存储地址之间的联系。很明显，线性数组(或者说是线性表)是首选。下面的存储方式很直观也是最容易想到的。对于大整数1112223334445 我们可以用一维数组来表示：数组下标：存储数据：,进位没有存放的位置,大整数的表示,但我们可以发现这种表示方法的一个不足之处：计算这个大整数加上9000000000000的结果。如果用前面的方式存储，我们会发现进位没有地方存放了。数组下标：大整数一：大整数二：结果：1为什么会出现这种情况？原因在于我们把大整数的高位存放在数组的下标小的位置。而解决这个问题的方法也很简单，就是把整数反过来存放。,这个进位可以通过扩大数组的方法来存放,大整数的表示,另一种表示方式数组下标：大整数一：大整数二：结果：1其实前一种表示方法还会有一个问题。就是高位的对齐，这个我们可以通过减法观察到，这里就不说了。基于以上原因，我们采用线性数组，同时把高位存放在下标大的地方。虽然这样子存放我们看起来不那么直观，但后面我们会看到这种存放方式的好处。,高精度加法运算,在确立了使用线性数组表示的大前提后，我们可以很容易地解决高精度加法。(这里为了简便，我就不用类实现了，同时假设那两个大整数都为正数。)1.初始化数组，数组全部元素置为0 2.用字符串读入大整数，同时以反向存储的方式 存放在数组中 3.进位标志flag置为0。从数组低位开始进行加 法运算。这里只要注意flag的更新就行了。4.反向输出结果,高精度加法运算,高精度加法举例这里我们假设我们已读入两个大整数，并且也已经被分别反向存放在数组a和数组b中了。加数a 8 7 4 2 5 9 7 80 0加数b 4 8 3 1 4 8 5 1 9 0结果c 2 6 8 3 9 7 3 00 1进位e 1 1 0 0 0 1 1 1 1 0上面的过程表示为87952478+915841384=1003793862减法亦可用相同的方法实现，只是现在标志换成借位标记而已。,前面补0的原因是为了对齐,高精度加、减法小结及其改进,我们首先要明确的一点是，选择线性数组及反向存储的方式并不是偶然的。我们可以列一个竖式，用手工模拟854+87的加法就会理解为什么要这样子处理了。而我们同时会发现，一个数组元素只存储一个位的方式有点浪费，虽然这很合乎我们的习惯。但可不可以通过增加存储位数的方法来提高效率呢？毕竟我们需要的这个一个位计算机只要4个二进制位就可以表示了，而VC给我们分配的一个int却有32位。,大整数的运算之加、减法的改进,我们来分析只存储一个位的大整数加法是怎样进行的。加数a 8 7 4 2 5 9 7 80 0加数b 4 8 3 1 4 8 5 1 9 0结果c 2 6 8 3 9 7 3 00 1进位e 1 1 0 0 0 1 1 1 1 0设i表示数组第i位数，则ci=(ai+bi+e)%10;e=(ai+bi+e)/10;,大整数的运算之加、减法的改进,所以我们如果要进行多位存储的话，我们只要把上面的计算式子改成ci=(ai+bi+e)%M;e=(ai+bi+e)/M;其中M为10的n次方，n为规定的位数。如，每个数组元素都存储4个位，则M=10000。这个改进并没有引起程序上大的变动，但它的对运算次数的减少是很有用的。做每个元素存储n位的加法，其加法的次数为只存储一位的1/n。这是因为它增大了存储密度，所以运算速度也随之提升了。,高精度加法程序,flag=0;n=min(a的位数，b的位数);M=10000;For(i=0;in|flag;i+)ci=(ai+bi+flag)%M;flag=(ai+bi+flag)/M;,习题,四川大学Online Judge 1001和1002 http:/http:/,高精度乘法,我们先来看一个小整数乘以大整数的乘法运算是如何进行的。我们模拟一下587414251047*56的执行过程。这里为了提高效率，56并没有必要被分成两个位去算，而是利用多位存储的思想来运算。大整数：7 4 0 1 5 2 4 1 4 7 8 5乘数：56进位：39 26 2 5 28 14 23 7 23 41 48 32 3 0结果：2 3 6 8 5 0 8 9 1 5 9 8 2 3所以乘法的最后结果就是32895198058632这里的关键就是进位不一定是一位的。其原理和加法多位存储的运算是一样的。,高精度乘法,现在我们来看看大整数乘以大整数是怎样进行的。还是先做手工模拟一下516541*4845412是怎么算的。我们发现它的原型就是先进行小整数乘以大整数，再把它们的和加起来的过程。其根本思想就是：设两个大整数分别为a，b(都已反向存储了)。将b按10进制展开，b=b0+10*b1+100*b2+bn*10n。其中bi为小于10的非负整数。则a*b=a*b0+a*b1*10+a*b2*100+a*bn*10n。而a*bi就是小整数乘以大整数。(后面乘10k，只要进行移位就可以实现了),高精度乘法,高精度乘法算法流程如下：读入被乘数s1，乘数s2把s1、s2分成n位一段，转成数值反向存在数组a,b中；记下b的长度mi=0;从b中取出第i位与a相乘，累加到另一数组c中；（注意：累加时错开的位数应是多少位）i+；检测i值：大于m则转,否则转打印结果,为什么结果存放在这一位？,高精度乘法程序,M=10000;p=大整数a的“位数”;/这里的位数是指多位存储时的位数q=大整数b的“位数”;for(i=0;ip;i+)flag=0;for(j=0;jq|flag;j+)ci+j+=ai*bj+flag;flag=ci+j/M;ci+j%=M;,高精度除法,联想我们是怎么进行除法运算的，就可以设计出一个算法来实现它，具体就不再赘言了。算法流程：输入被除数a，除数b（判断除数是否为零，是则结束），转2；j=length(a)-length(b)，商Q为0，转3；截取a前length(b)位，赋给R，转4；从R中逐次减去b，直到减了K次后R小于b为止，转5；把K加到商数Q末尾，转6；(-j=0)?在R后面加上bj，转4：转7；输出商数Q及余数R。,高精度除法,这里就不给出除法的程序了。但在实现时需要注意1.除法可以反向除也可以正向存储，只要做相应调整就可以2.实现时需要定义一个函数来比较两个大整数的大小，同时要用到大整数减法3.多位存储还是可以运用的。但细节上要小心,习题,四川大学Online Judge 1003、1004北京大学Online Judge 1001 http:/,组合数和Catalan的精确计算,由于Catalan函数本身是一个组合数再除以一个相对较小的整数，而除法在前面已经提过了。这里我们就只看组合数的精确求值。算法一：C(m,n)=C(m-1,n)+C(m-1,n-1)C(m,0)=1利用上面的递归式，我们可以在O(n*大整数位数)辅助空间的基础上设计出一个只用加法就能算组合数的算法。但我们看出这在实际上是不实际的。当m=10000,n=5000时，辅助空间就要达到4*5000*3009Bytes约50几M的内存。实际上，它在时间效率上也是很不理想的。,组合数和Catalan的精确计算,算法二：利用C(m,n)=m!/(n!*(m-n)!)对上式进行化简可变为C(m,n)=m*(m-1)*(m-n+1)/n!在实现上，我们如果先把m*(m-1)*(m-n+1)算出来再去除以n!的话，时间和空间的消耗都是比较大的。我当时的做法是,组合数和Catalan的精确计算,1.采用多位存储，数组每个元素存储4位2.从m开始乘到(m-n+1)时，每乘一个数k就相就地除以一个数(m-k+1)。这样即可以保证结果还是整数的同时，减慢空间的消耗。3.等乘数或除数够大时才进行相应的计算。如算100*99*50/50!一开始时我们没必要马上就把100乘到结果上去。而是等再乘上99后，再把结果乘上9900。这样可以减少很多次计算。最后我的程序计算C(5000,2500)和C(10000,5000)/50001差不多要1.7S才能出结果。对这个结果还是不大满意。于是我又想了另一种算法。,组合数和Catalan的精确计算,算法三分析一下算法二，程序运行时间主要花在高精度乘法和高精度除法上。而乘法是必需的，效率也比除法好很多，因此我们的着眼点就变成了，怎么去避免除法或将除法转换成乘法或干脆就将除法去掉。如果能将除法去掉当然是最好的了。但能不能做到呢？答案是可以。还是利用到算法二的那个化简后的式子。别看它挺长的，但我们可以保证，它的计算结果一定是整数。因为组合数本身就是一个整数，没有理由经过化简后就变成带有小数的实数。,组合数和Catalan的精确计算,利用这点，联想到小学时经常做的分数化简，只要先把分子进行分解，存放在一个数组count中，counti表示分解后因子为i的个数。再将分母也进行分解，但在分解的过程中，每次得到一个因子k，我们只要countk-就可以了。因为m的值不可能太大，而count最大只需o(m)的辅助空间，所以在空间是可行的。在时间效率上，因为避免了除法运算，所以效率上肯定会有大的改进的。利用和算法二一样的一些技巧后，我的程序计算C(5000,2500)和C(10000,5000)/50001只要0.7S就可以得到结果了。,总结,其实算法三还是可以再做改进的，如可以预先存储一个素数表，便于分解因数。同时因为分解因式后，我们要计算的其实就是aipi其中ai为素数，pi为正整数。这个可以利用二分的方法进行改进的，只要利用我们前面写的模板类。我们看到这题不论在数据结构和算法改进上都有一些小技巧。选择的数据结构要便于编程实现并要能够有效地解决问题，但一般在数据结构方面能做的改进不是很多。而算法就不一样了，它是整个程序的灵魂，在算法上改进的余地一般也是比较大的。我们只有在掌握基本数据结构的基础上，不断地学习、改进算法才能有效地解决这类题目。,Thanks For Attention,