时间复杂度取决于大整数乘法的大整数除法

时间复杂度取决于大整数乘法的大整数除法 说明书 时间复杂度取决于大整数乘法的大整数除法 技术领域 本文主要提供一种特殊的分治递归运算的大整数除法,包括整除的商值及整除后取余数,。这种算法主要应用于计算机领域～尤其是加密技术中。 论文背景 当前公开或使用的大整数除法即使采用Knuth的经典名著“The Art of Computer Programming”的第4.3.1节中的猜商值公式来计算～也需要多次试 2运算～所有这些大整数除法最大的缺点是时间复杂度:T(n) = O(n)这与大整数乘法相比差远了。因此减少试运算的次数～降低时间复杂度对大整数除法具有特别重要的意义。本文依据全新的计算理论～构造了独特的大整数除法计算方法～文中实施例使试运算出现的概率远低于现有算法～即使出现也只需一次加法运算,不仅如此～更为重要的是本文采用特殊的分治递归的方法充分利用大整数乘法～使大整数除法的时间复杂度等于大整数除法中所采用的大整数乘法的时间复杂度～例如大整数除法中采用Karatsuba乘法加速时～本文中的大整数 log3除法时间复杂度:T(n) = O(2)，如果采用其他更快的大整数乘法～本算法n 会更快～这就使数值很长的大整数除法的计算速度大幅提高～例如当被除数的长度为4194304个四字节～除数长度为2097152个四字节时～本算法中采用Karatsuba乘法加速时的速度为现有大整数除法速度的30倍左右。 论文内容 本文在这部分将推出一种全新的大整数除法计算理论，并利用该理论构造分治的大整数除法，在分治中充分利用大整数乘法，以达到加速目的。请看下面的推理: 设大整数运算过程中采用h(大于1的整数)进制， 正整数集合:Z={x| x,0并且 [x]=x } 集合1:H= {x| 0?x,h 并且x为整数} 集合2:H={x| 1?x,h 并且x为整数} 2 10003 2006.7 1 说明书 任何有限长度的大整数除法都可转化为非负大整数的除法，因此除了最后一段外，下文只涉及非负大整数除法，非负大整数除法可表示如下: C=A/B (A?0, B,0, C?0并且A和B都是整数) (1) 当A=0时，显然C=0， (2) 当A,B时，显然C的整数部分为0， (3) mm当A?B时，可通过将被除数和除数都乘以h从而使A和B都转化为不小于h的整数，并使结果C保持不变，其中m?2且m Z，因此(1)式在排除(2)、(3)后，可转? 化为下式: mC=A/B (A?B，B?h, m?2, C,0且A、B和m都是正整数) (4) 在(4)中A=(AAA…AA)h可用多项式表示如下: 123i-1i i-1i-2i-31A=Ah， Ah， Ah，…， Ah， A(5) 123i-1i 其中iZ，AHAH ( 1,r?i,且r为整数), h为进制基数， ?1?2， r? 用AA的前m项，即 H表示 i-1i-2i-3i-(-1)i-mm，，，， Ah (A=Ah Ah Ah…， Ah6) H123-1mm 设A=A，A(7)HE 则有 i-(，1)i-(，2)i-(，3)mmmA=Ah，Ah，Ah，…，Ah，A(8)E，1，2，3i-1i mmm 在(4)中B=(BBB…BB)h可用多项式表示如下: 123-1jj j-1j-2j-31B=Bh， Bh， Bh，…， Bh， B (9) 123j-1j 其中jZ，BHBH ( 1,r?j,且r为整数), h为进制基数 ?1?2， r? j-m用B=(BBB…BB)h×hB的前m项，即 123-1H表示mm j-1j-2j-3j-(-1)j-mmB=Bh，Bh， Bh，…，Bh，Bh (10) H123-1mm 其中m,j 设B=B，BHE 则有 j-(，1)j-(，2)j-(，3)mmmB=Bh，Bh，Bh，…，Bh，B (11) E，1，2，3j-1jmmm 在(4)中C=(CCC…CC)h，f可用多项式表示如下: 123k-1kC 10003 2006.7 2 说明书 k-1k-2k-31C=Ch，Ch，Ch，…，Ch，C，f (12) 123k-1kC 其中kZ，CH，CH ( 1,r?k,且r为整数), 0?f,1， h为进制基数 ?1?2 r?C 设 W=A/B H 则W=( WWW…WW)h，f可用多项式表示为 123-1Wnn -1-2-31nnnW=Wh，Wh，Wh，…，Wh，W，f (12_H) 123-1Wnn 其中nZ，WHWH ( 1,r?n,且r为整数), 0?f,1，其中h为进制基2， r??1?W数 根据前面的陈述可知: A/B?A/B 即W?C H 下面进行理论推导的第一大步骤,讨论i、j和k的关系: i-1i-2i-31=A/B=(Ah，Ah，Ah，…，Ah，A)/B C123i-1i iij-1j-2j-31,h/B = h/(Bh，Bh，Bh，…，Bh，B) 123j-1j ij-1?h/Bh 1 i-j，1得到 C,h/B 1 kkk-1i-1-23-j，1即 Ch，Ch，Ch，…，Ch，C，f, h/B 123k-1kC1 k-1i-j，1? h,h ? k,i-j，2 (13) C=A/B j-1j-2i-ji-(j，1)1 =(Ah，Ah，…，Ah，A) h/B， (Ah，…，Ah，A)/B 12j-1jj，1i-1i 为便于表述设: j-1j-2j-3A=Ah，Ah，Ah，…，Ah，A (14) J 123j-1j i-ji-(j，1)1? C=Ah/B，(Ah，…，Ah，A)/B (15) Jj，1i-1i显然当A?B时， J i-ji-(j，1)1i-j C=A/B?h，(Ah，…，Ah，A)/B?hj，1i-1i k-1k-2k-31i-j? Ch，Ch，Ch，…，Ch，C，f?h 123k-1kC ki-j? h,h ? k,i-j 又结合(13)可得 当A?B时，k=i-j，1 (16) J 接下来，推导当A,B时，k与i-j的关系: J 10003 2006.7 3 说明书 i-1i-2i-31C=A/B=(Ah，Ah，Ah，…，Ah，A) /B 123i-1i i-1i-1j-1j-2j-31?Ah/B= Ah/(Bh，Bh，Bh，…，Bh，B) 11123j-1j i-1j, Ah/h 1 i-1-j? C,Ah 1 将(12)代入得 k-1k-2k-31i-1-j Ch，Ch，Ch，…，Ch，C，f, Ah 123k-1kC1 k i-1-j? h,h ? k,i-j-1 (17) 因为A,B，且A和B都是整数，因此可得 J J A，1?B J A/B得 又由C= j-1j-2j-3 i-jC= (Ah，Ah，Ah，…，Ah，A)h/B， 123j-1j i-(j，1)1(Ah，…，Ah，A)/B j，1i-1i j-1j-2j-3 i-ji-j,(Ah，Ah，Ah，…，Ah，A)h/B，h/B 123j-1j jj i-1j-2-3-j=(Ah，Ah，Ah，…，Ah，A，1)h/B 123j-1j i-j=(A，1)h/B J ii-j-j?Bh/B=h 1k-1k-2k-3i-j? Ch，Ch，Ch，…，Ch，C，f, h 123k-1kC? k,i-j，1 结合(17)可得 当A,B时，k=i-j J 下面进行理论推导的第二大步骤,讨论C中k和W中n的关系: 设: P=W-C 则有 P= A/B -A/(B，B) =BA/(B，B)/B=CB/B HHEEHEHEH即有 P/C=B/B EH j-(，1)j-(，2)j-(，3)mmm=(Bh，Bh，Bh，…，Bh，B)/B ，1，2，3j-1jHmmm j-m , h/B H j-j-1j-2j-3j-(-1)j-mmm=h/( Bh，Bh，Bh，…，Bh，Bh) 123-1mm 10003 2006.7 4 说明书 j-j-11-mm?h/(Bh)?h 1 1-m? P/C,h 1-m? (W-C)/C,h 1-m? W/C,1，h 1-m? 1，h, W/C (19) 则有 -211--1-3mnnn 1，h, W/C=(Wh，Wh，Wh，…，Wh，W，f)/C 123-1Wnn k-21-1-1k-1k-3nn?h/C=h/(Ch，Ch，Ch，…，Ch，C，f) 123k-1kC k-1n,h/h 1--1-kmn? 1，h, h 由于m?2，h?2所以有 又由W?C可推出n?k,由这两者可得 n-1-k?0 n=k 或 n=k，1 下面进行理论推导的第三大步骤,讨论C多项式和W多项式中前m项的关 系: k--1k--2k--31k-mmmm因为0?Ch，Ch，Ch，…，Ch，C，f,h +1+2+3k-1kCmmm k--1k--2k--31k- mmmm所以可设 Ch，Ch，Ch，…，Ch，C，f,βh+1+2+3k-1kCmmm 并且0?β,1 由(19)得 1--1-2-31mnnn1，h,(Wh，Wh，Wh，…，Wh，W，f)/C 123-1Wnn -1-2-3-(-1)-nnnnmnm ?(Wh，Wh，Wh，…，Wh，Wh)/C 123-1mm -1-2-3-(-1)-k-1k-2nnnnmnm=(Wh，Wh，Wh，…，Wh，Wh)/ (Ch，Ch，123-112mm k-31Ch，…，Ch，C，f) 3k-1kC -1-2-(-1)-k-1k-2k-3nnnmnm=(Wh，Wh，…，Wh，Wh)/(Ch，Ch，Ch，…12-1123mm k-(-1)k-k-mmm，Ch，C h，βh) (20) -1mm 先将n=k代入(20)得 1-k-1k-2k-(-1)k-k-1k-2mmm1，h,(Wh，Wh，…，Wh，Wh)/(Ch，Ch，12-112mm k-3k-(-1)k-k-mmmCh，…，Ch，C h，βh) 3-1mm -1-2-1-2mmmm=(Wh，Wh，…，Wh，W)/(Ch，Ch，…，Ch，C，12-112-1mmmm β) 整理得 10003 2006.7 5 说明书 -1-2-1mmm(C-W)h，(C-W)h，…，(C-W)h，(C-W)，β，(Ch1122-1-1 1mmmm -2-31-mmm，Ch，Ch，…，Ch，C，β)h,0 (21) 23-1mm 由(21)得 -1-2mm0,(C-W)h，(C-W)h，…，(C-W)h，(C-W)，β，1122-1-1 mmmm -1-2-31-mmmm(Ch，Ch，Ch，…，Ch，C，β)h 123-1mm -1-2mm,(C-W)h，(C-W)h，…，(C-W)h，(C-W)，β，h 1122-1-1 mmmm ? -2-3mm0,(C-W)h，(C-W)h，…，(C-W)，((C-W)，β)/h，1 1122-1-1 mmmm -2-3mm,(C-W)h，(C-W)h，…，(C-W)，1，1 1122-1-1mm 考虑到定义域可推出 -2-3mm-W)h，(C-W)，1 0?(C-W)h，(C，…1122-1-1mm -2-3-2-3mmmm? (Wh，Wh，…，W)-(Ch，Ch，…，C)?1 12-112-1mm结合 W?C 推出 当n=k时，则必有结论1 (23) ---232-3mmmmWh，Wh，…，W=Ch，Ch，…，C 12-112-1mm ----2323mmmm或 Wh，Wh，…，W=Ch，Ch，…，C，1 12-112-1mm 即(CCC…C)h = ( WWW…W)h 123-1123-1mm 或者 (CCC…C)h = ( WWW…W)h-1 123-1123-1mm 将n=k，1代入(20)得 1--12-1-2-3mmmmmm1，h,(Wh，Wh，…，Wh，Wh)/(Ch，Ch，Ch12-1123mm 1，…，Ch，C，β) (24) -1mm mm ,Wh/h=W 11 ? W=1， 将W=1代入(24)可得 11 -1-232mmm(1-0)h，(W-C)h，(W-C)h…，(W-C)h，(W-C)h2132-2-3-1-2mmmm，(W-C)h-C-β -1mmm -1-2-311-mmmm,(Ch，Ch，Ch，…，Ch，C，β)h,h (25) 123-1mm -1-23mmm? (1-0)h，(W-C)h，(W-C)h…，(W-C)h，2132-2-3mm 2(W-C)h，(W-C)h,C，β，h -1-2-1mmmmm -1-2-32mmm? (1-0)h，(W-C)h，(W-C)h…，(W-C)h，2132-2-3mm 10003 2006.7 6 说明书 (W-C)h，(W-C),(C，β)/h，1 -1-2-1mmmmm -1-2-32mmm? (1-0)h，(W-C)h，(W-C)h…，(W-C)h，2132-2-3mm (W-C)h，(W-C)?1 -1-2-1mmmm -1-2-3-2-3mmmmm? (h，Wh，Wh…，Wh，W)-(Ch，Ch…，Ch，23-112-2mmmC)?1 -1m -1-2-3-2-3mmmmm又因(h，Wh，Wh…，Wh，W),(Ch，Ch…，Ch，23-112-2mmmC) ，所以当n= k，1时，则必有结论2 (26) -1m -2-3-1-2-3mmmmm (Wh，Wh，Wh…，Wh，W)-(Ch，Ch…，Ch，123-112-2mmm C)=1 且 W=1 -11m ? (CCC…C) =(WWW…WW) -1 (27) 123-1123-1mmm 讨论用分治法计算C多项式的整数部分:下面进行理论推导的第四大步骤, 由前面论述可知: W=[A/B ] 整H =[ ( WWW…WW)h，f ] 123Wn-1n = ( WWW…WW)h 123-1nn k-m，1，= ( WWW…W)h×h( WW…WW)h 123，，， nm-k-1nm-k nm-k+1n-1n ? k-m，1[A/B / h] = ( WWW…W)h (28) H123， nm-k-1当n=k时，从(28)显然可得， k-m，1[A/B / h] =( WWW…W)h H123 m-1此时结合(23)可得 k-m，1(CCC…C)h =[A/B / h] (29) 123Hm-1 k-m，1或者 (CCC…C)h =[A/B / h]-1 123Hm-1 当n=k，1时，从(28)显然可得， k-m，1[A/B / h] =(WWW…WW)h H123m-1m 此时结合(27)可得 k-m，1(CCC…C)h =[A/B / h] -1 (30) 123Hm-1 综合(29)、(30)就会发现不论n、k的关系如何，都可得 10003 2006.7 7 说明书 结论3 k-m，1(CCC…C)h =[A/B / h] 123Hm-1 k-m，1或者 (CCC…C)h =[A/B / h]-1 (31) 123Hm-1 有了结论3，就为分治计算定了基础。 C=(CCC…CC)h 整123k-1k k-m，1=(CCC…C)h×h，(CCC…CC)h 123 k-1 km-1mm+1m+2上式中的(CCC…C)h就可利用结论3即(31)来计算， 123m-1 k-m，1设W= [A/B /h]，C=(CCC…C)h , LHL123m-1计算C方法如下: L k-m，1? 计算W=[A/B /h] LH k-m，1= [(AAA…AA)h / (BBB…BB)h /h ]，并计算 123i-1i123m-1m k-m，1A?A- BWh 其中?表示将右边的计算结果赋给左边 HL ?用快速的大整数乘法计算WB LE k-m，1? 计算A?A- WB h 其中WB已在?完成 LELE k-m，1? 判断A,0是否成立，若成立则计算A?A，Bh，并计算W?W-1 LL ? 完成赋值C?W LL 下面依据本文的计算理论构造特殊的分治递归的方法，使大整数除法的时间复杂度等于 大整数除法中所采用的大整数乘法的时间复杂度。 rk/2k/2 首先请看针对特殊情况的分析，设j=k=2，A=(Bh，B)(Ch，C)，Y 其中，rLRLR k/2Z且r?2，BBC、C、Y都是非负整数，B,0，Y,(Bh，B) ?L、R、LRLLR k/2k/2则 Y=A-(Bh，B)(Ch，C) LRLR k/2k/2k/2=A-(Bh，B)Ch-(Bh，B)C LRLLRR k/2如果已知A、B=Bh，B要求余数Y则应从高位算起，计算过程可分为以下几步: LR ?计算C L k/2k/2?计算A?A-(Bh，B)Ch LRL ?计算CR k/2?计算A?A-(Bh，B)C LRR 仔细分析就会发现，如果k/2>I (I为大于2的正整数次幂的常数)，适当修改?和?， 就可在?中再对C分治，在?中再对C分治，这样计算余数Y就变成了一个递归函数的运LR 10003 2006.7 8 说明书 算了。修改之后，得到的计算方法如下: ? 判断当前要计算的商数C长度k是不是等于某整数N，若是，则采用预定算法计算C，并计算A′?A′-BC ，然后退出;若不是，则执行下一步; 1,N+F 其中所述A′就是从A中当前低端定位点的数位开始向高位延伸到第1个非0数位共同构成的大整数(如果没有非0数，则A′表示0)，A中当前低端定位点的计算方法请参后面的SuperDivision_Core_0、SuperDivision_Core_1这两个函数中的说明;B就是从B1,N+F的高位顶点开始向低位延伸的N+F位数共同构成的大整数;N应为2的非零整数次方,F,=1,由于分治计算时高位商数在完成与除数的部分乘积减后，就开始计算低一位的商数，因此会暂时留下较多的剩余数据，当F=1时，需要试运算的概率较高，当F=2时，需要试运算的概率较小，当F=3时出现试运算的概率就很小，因此 3比较好，当然也可设置F为更大的值，但太大会影响速度; 设置F= ?将C空间等分为存放高位商数C和存放低位商数C两部分; LR ?递归计算C; L ?计算A′?A′-BC; k/2+F+1,k+FL 其中所述B表示B中从高位第k/2+F+1位数开始向低位延伸到k+F位数所构k/2+F+1,k+F 成的大整数;由于前面的运算已算到B这项，因此只能将B后的F位数添加在B后面k/2+Fkk构成一个具有k/2位数的大整数参与运算，以便使用大整数乘法达到加速目的，BCk/2+F+1,k+FL就是一个k/2位大整数乘以k/2位大整数的运算，这样就可采用快速乘法来加速; ?判断A′是否小于0，若是，则计算A′?A′，B; 1,k+F 其中B表示B中从高位第1位数开始向低位延伸到第k+F位数所构成的大整数; 1,k+F ?递归计算C ; R ?计算A′?A′-BC; k/2+F+1,k+FR ?判断A′是否小于0，若是，则计算A′?A′，B; 1,k+F 在上述计算完成之后，余数Y=A，这样就完成了求模余的计算，同时也完成了计算整除商数的过程。下面用近似于C++和JAVA的函数伪码表示上述运算流程如下: void SuperDivision_Core_0(A, B, C,int k ) //调用时A、 B都是大整数对象，分别对应 { //被除数、除数、应在A、B后面预留F位空间，并将B中预留空间归0，计算完成之 //后，结束时，模余在A中，商数的整数部分在C中，当然应用时这些参数可能就是一 //个整数类型或字符串类型的数组或指针以及相关变量(含指针)共同来实现，调用(不 //含自身递归)该函数之前应满足A,B，参数k表示除数长度，也表示商数的数位长 J 10003 2006.7 9 说明书 r//k==2，rZ， ? if(A!=NULL) A.pfinger=A.pfinger+ k*2; T //首次调用时，设置好A中当前高端定位点指针A.pfingerT， //A最好为static对象(含指针) T if(k==N) //当数值较小时，常规除法更有效， { A.pfinger=A.pfinger-(N*2+F); //使A.pfinger指向A中当前低端定位点 CTC // A就是从A中当前低端定位点的数位开始向高位延伸到第1个非0数位共同构成 C //的大整数(如果没有非0数，则A表示0) C MinDivision(A,B.pfinger-F,N+F,C.pfinger ); C 中，第二个参数表示指向除数的指针，第三个参数表示 //在MinDivision //除数长度，MinDivision函数的功能是计算C，并计算A′=A′-B′C， //此处A与A′对应，不允许给C.pfinger[N]赋值，否则就会出现0覆盖 C A.pfinger=A.pfinger-N; TT return; } k/2B=Bh+B ; //将B分割为两半，并且B.pfinger=B.pfinger LRR // B.pfinger=B.pfinger+k/2 ，B.Length = B.Length =k/2 , L L R k/2C=Ch+C;//将C分割为两半，并且C.pfinger=C.pfinger LR R // C.pfinger=C.pfinger+k/2 ，C.Length =C.Length =k/2 , LL R SuperDivision_Core_0(NULL, B, C ，k/2); //递归 L L SetCurrentA(A ，A); // 设置A，如设置A.pfinger=A.pfinger -k-F; 使 TLLLT //A.pfinger指向A中当前低端定位点等 L A=A-SuperMultiply(B.pfinger -F,k/2, C.pfinger ,k/2); LLRL // SuperMultiply的功能是计算两个大整数的乘积，此处A与A′对应， L if(A<0) { //小概率事件 L FF-1F-2F-3A= A，(Bh，Bh， Bh，Bh，…，B); LLk+1k+2k+3k+F C= C-1; LL } SuperDivision_Core_0(NULL, B, C ，k/2); //递归 LR 10003 2006.7 10 说明书 SetCurrentA(A ，A ); //设置好A，如设置A.pfinger=A.pfinger -k-F; 使 TRRR T //A.pfinger指向A中当前低端定位点等 R A=A-SuperMultiply(B.pfinger -F,k/2,C.pfinger ,k/2); RRRR //此处A与A′对应， R if(A <0) { //小概率事件 R FF-1F-2F-3A=A，(Bh，Bh， Bh，Bh，…，B); RRk+1k+2k+3k+F C= C-1; RR } return ; } 容易看出函数SuperMultiply_0中两个递归后面的代码高度相似，并且很容易实现代码复用，将SuperMultiply_0修改后就得到下面的伪码函数 k ) //调用时A、 B都是大整数对象，分别对应 void SuperDivision_Core_1(A, B, C,int { //被除数、除数、应在A、B后面预留F位空间，并将B中预留空间归0，计算完成之 //后，结束时，模余在A中，商数的整数部分在C中，当然应用时这些参数可能就是一 //个整数类型或字符串类型的数组或指针以及相关变量(含指针)共同来实现，调用(不 //含自身递归)该函数之前应满足A,B，参数k表示除数长度，也表示商数的数位长 J r//k==2，rZ， ? if(A!=NULL) A.pfinger=A.pfinger+ k*2; T //首次调用时，设置好A中当前高端定位点指针A.pfingerT， //A最好为static对象(含指针) T if(k==N) //当数值较小时，常规除法更有效， { A.pfinger=A.pfinger-(N*2+F); //使A.pfinger指向A中当前低端定位点 CTC // A就是从A中当前低端定位点的数位开始向高位延伸到第1个非0数位共同构成 C //的大整数(如果没有非0数，则A表示0) C MinDivision(A,B.pfinger-F,N+F,C.pfinger ); C //在MinDivision中，第二个参数表示指向除数的指针，第三个参数表示 //除数长度，MinDivision函数的功能是计算C，并计算A′=A′-B′C， //此处A与A′对应，不允许给C.pfinger[N]赋值，否则就会出现0覆盖 C 10003 2006.7 11 说明书 A.pfinger=A.pfinger-N; TT return; } k/2B=Bh+B ; //将B分割为两半，并且B.pfinger=B.pfinger LRR // B.pfinger=B.pfinger+k/2， B.Length =B.Length =k/2 , LL R k/2C=Ch+C;//将C分割为两半，并且C.pfinger=C.pfinger LR R // C.pfinger=C.pfinger+k/2 C.Length =C.Length =k/2 , LL R BOOL IsFirstTime=TRUE; ReWork: SuperDivision_Core_1 (NULL, B, C ,k/2); //递归 L L ，A); // 设置好A，如设置A.pfinger=A.pfinger -k-F; 使 SetCurrentA(ATLLLT //A.pfinger指向A中当前低端定位点等 L A=A-SuperMultiply (B.pfinger -F,k/2, C.pfinger ,k/2); LLRL // SuperMultiply的功能是计算两个大整数的乘积，此处A与A′对应， L if(A<0) { //小概率事件 L FFF-F-12-3A= A，(Bh，Bh， Bh，Bh，…，B); LLk+1k+2k+3k+F C= C-1; LL } if(IsFirstTime){ IsFirstTime=FALSE; C.pfinger=C.pfinger; LR goto ReWork; } return ; } 通过对SuperDivision_Core_1函数的分析就会发现该函数把大整数除法转化为短除MinDivision，两次大整数乘法SuperMultiply，两次减法，以及一些计算量可忽略的辅助运算如指针赋值或移动等，由于本函数已限定被除数的长度为除数的两倍，因此下面以除数长度j来衡量时间复杂度，显然两次减法与除数长度j是线性相关的，由于限制了短除MinDivision的除数的长度为N，因此运算MinDivision所消耗的时间与被除数的长度2×j线性相关，并且当j很大时，前述的两次减法与短除所消耗的时间相对大整数乘法10003 2006.7 12 说明书 SuperMultiply所消耗的时间来讲可忽略不计，因此本文的时间复杂度取决于大整数乘法SuperMultiply的时间复杂度，例如SuperMultiply采用Karatsuba乘法时，本文中的大整 log3数除法时间复杂度:T(n) = O(2) 。本人根据上述SuperDivision_Core__1函数算法n 写出的代码采用了Karatsuba乘法，并进行了测试，测试方法是，随机产生两个长度为j 4个四字节(h=256)的大整数B、C及一个小于B的大整数Y，并利用Karatsuba乘法计算A=BC，接着计算A?A+Y，然后用SuperDivision_Core_1算法计算A/B商数的整数部分C′和余数Y′，然后比较C==C′和Y==Y′这两者是否成立，经过大量测试都验证这两者成立，在测试中还将计算A=BC时Karatsuba乘法所耗费的时间和计算A/B时SuperDivision_Core_1算法所耗费的时间进行了对比分析，发现在j?64个四字节的条件下SuperDivision_Core_1算法所消耗的时间约为Karatsuba乘法所消耗时间的两倍左右。当 调用其他大整数乘法如Toom–Cook算法、Schönhage–Strassen 算法、Fürer然，本算法也可 算法等。 在SuperDivision_Core_0算法和SuperDivision_Core_1算法中都调用了MinDivision短除函数来逐位计算当前最高位商数。接下来，讨论如何计算最高位商数C: 1 jk--22，1[A/((Bh，B) h)/ h] 12 iii1jk-1-2-3-2-2，1,[(Ah， Ah， Ah，…， Ah， A) /((Bh，B) h)/ h] 123i-1i12 ii1j+k-3i-1-2-3,[(Ah， Ah， Ah，…， Ah， A) /((Bh，B) h)] 123i-1i12 i1-1i-2i-3i-4j+k-3,[((Ah，Ah，Ah)，(Ah…， Ah， A))/((Bh，B) h)] 1234i-1i12 结合 i,j+k 或 i,j+k-1 可得 j-2k-i-1i-2i-3j+k-32，1[A/((Bh，B) h)/ h],[(Ah，Ah，Ah)/((Bh，B) h)] 1212312 i+2i+1ij+k,[(Ah，Ah，Ah)/((Bh，B) h)] (34) 12312 将i,j+k代入(34)得: j-2k-212，1[A/((Bh，B) h)/ h],[(Ah，Ah，A)/(Bh，B) ] (35) 1212312 结合结论3即(31)可得: 当i,j+k即A,B时， (39) J 21C,[(Ah，Ah，A)/(Bh，B)] 112312 21或C,[(Ah，Ah，A)/(Bh，B)]-1 112312 将i,j+k-1代入(34)得: j-2k-2，1[A/((Bh，B) h)/ h],[(Ah，A，A/h)/(Bh，B) ] 1212312 10003 2006.7 13 说明书 ,[(Ah，A)/(Bh，B)] 1212结合结论3即(31)可得: 当i,j+k-1即A?B时， (40) J C,[(Ah，A)/(Bh，B)] 11212 或C,[(Ah，A)/(Bh，B)]-1 11212 如果当A?B时，在A前添加一个0项，将0作为A的第一项，则此时也可使用(39)J 来计算C ，这样就将计算C的公式统一为(39)，无需考虑(40); 11 21 根据(39)要计算C首先得计算[(Ah，Ah，A)/(Bh，B)]，为充分利用CPU112312 322的带宽，通常h为CPU带宽的一半，例如在64比特CPU计算机中h=2，如果将(Ah，1 1Ah，A)做为一个整体来处理的话，就会超出CPU的带宽，因此必须设计一种方法来计算23 21h，B)];下面用近似C++语言的伪码的写出一种在CPU[(Ah，Ah，A)/(B12312 21′带宽为U比特计算机中计算C,[(Ah，Ah，A)/(Bh，B)]的方法: 112312 ′C,(Ah，A)/B; 1121 ′′if(C,,h) C,h-1; 11 ′Y=(Ah，A)- C*B; 1211 Y=<= A.pfinger) C { C,*(( unsigned CPUInteger *)A.pfinger)/B; 121 //其中unsigned CPUInteger *表示在计算机中CPU带宽无符号整数类型的数据， //如在64比特计算机用*(unsigned _int64*(A.pfinger))获取(A*h，A) 212 Y=*(( unsigned CPUInteger *)A.pfinger)- C*B; 211 Y=<<(U/2) ;// U 为CPU带宽值，如在64比特计算机中U==64 Y，= *( A.pfinger-1) ; // 即 Y，= A ; 23 X= B*C 21 if(X> Y) //这是由于C大于正确值 1 { 21 X= X-Y;//此时 X==C (Bh，B)- (Ah，Ah，A) 112123 C= C- X/(Bh，B);//这行和下面一行扣除C超出部分， 11121 if(X%(B*h，B)) C= C-1; 1211 } k-1A=A -B*C; //计算A=A-B*Ch; CC1 1 if(A <0) //即if(A<0) C { 10003 2006.7 15 说明书 k-1A = A，B ; //计算A=A，Bh ; CC C=C-1; 11 } *pCWorkFinger=C; 1 pCWorkFinger-,1;//每循环一次pCWorkFinger就在C上向低端滑动一个基数位 A.pfinger -,1; //每循环一次A就就在A上向低端滑动一个基数位 22 A.pfinger -,1; //每循环一次A就在A上向低端滑动一个基数位 CC } } 当将上述BigDivision单独作为一个大整数除法时已经比现有大整数除法更有效率， (指SuperDivision_Core_0和SuperDivision_Core_1)因此上面SuperDivision_Core函数 中的MinDivision函数最好使用BigDivision函数中的算法，即使用BigDivision函数中的算法来计算高位商数，当然不排除MinDivision函数使用其他常规大整数除法的算法。不过MinDivision函数与普通的大整数除法处理细节上稍有差别。参见下表， B B B B B B B … 1234567 ? 行 C C C C C C C … 1234567号 … … … … … … … R7 BC BC BC BC BC BC BC … 17273747576777R6 BC BC BC BC BC BC BC … 16263646566676R5 BC BC BC BC BC BC BC … 15253545556575R4 BC BC BC BC BC BC BC … 14243444546474 R3 BC BC BC BC BC BC BC … 13233343536373 R2 BC BC BC BC BC BC BC … 12223242526272 R1 BC BC BC BC BC BC BC … 11213141516171 A A A A A A A A A A A A A A … 1234567891011121314 这是一个

小学

小学生如何制作手抄报课件柳垭小学关于三违自查自纠报告小学英语获奖优质说课课件小学足球课教案全集小学语文新课程标准测试题

乘法过程表，仔细研究就会发现，普通大整数除法在计算商数中当前高位10003 2006.7 16 说明书 商数时，就是小学乘法的逆过程，都是每算出一个高位商数就从A中消掉与该高位商数相乘的项，如算出C后，就消掉R1这行:BCBC BCBC BC BC BC… ， 111 21 31 41 516171 因此接下来计算下一位的高位商数时，就不会受更高位商数的干扰，但在本文中分治法大整数除法的计算路径不是这样，而是在算出高位商数后，利用该高位商数与除数消除所对应行的前几项，就开始计算下一位的高位商数，导致低位商数的计算会受到高位商数的干扰，例如当N=2、F=1时，本算法在算出C后，就消掉R1这行中的:BC BC BC，就 111 21 31开始计算C，从上表中可以看出显然按这种路径计算C时，R1这行尚未消掉的项BC 2 241 BC BC BC…，可能向A这个位置产生进位，该进位值最大可达h-1,因此会干扰5161714 C的计算，F取值的大小决定了高位商数对低位商数计算的影响大小，根据(31)可知F?12 就可采用分治法，但当F=1或F=2时往往需要较多的试运算，当设置F=3时，需要试运的概率极小。但即时设置F=3或F=4仍然不可能完全消除高位商数对低位商数计算的影算 响，例如设置N=2、F=4时，本算法在算出C后，就消除R1这行中的:BC BC BC 111 21 31 BC BCBC，就开始计算C，从表中可以看出显然按这种路径计算C时，R1这行还41 51 612 2有未消掉的项BC …，这些未消掉的项与R1之上各行相加就可能引起连串的进位，并传递71 到A这个位置，甚至使A这个位置向A的进位突破h-1，并达到h，从而使A=1，这是现3321有大整数除法运算中不会出现的情况，因此MinDivision函数计算高位商数时，需要注意处理这种极端情况，不过可喜的是，在F?1的条件下可推出当前所求的高位商数等于h-1 。 具体实施方式 该方法可应用到计算机技术中，尤其是加密算法中的取模运算，可以以代码的形式出现在计算机、手机等各种可运行软件的电子设备中。 有了上面的准备工作，现在就可以写出一个计算大整数整除的商数(即商值的整数部分)和余数的实施例SuperDivision函数的伪码: SuperDivision(A, B, C，Y )//结束时， C保存整除的商数、Y保存模余 { if(FormatReady(A, B)==FALSE) return 0; // 若参数非法，则返回0; //FormatReady的功能主要是分配空间，将预留空间清0，并将A、B的数据复 //制到新空间上合适位置，并使A.pfinger、B.pfinger指向所对应的新空间， //并且A.pfinger、B.pfinger之后都至少有F个预留空间，如果B.Length不等 //于2的整数次幂，则应将从A、B复制到新空间上的数据都向高端移动相同个基数10003 2006.7 17 说明书 //位(腾空位置应清0)，相当于将A、B都乘以一个整数，以确保B.Length等于2 //的整数次幂，并对A作出修剪处理，以使 (A,B&&A.Length%B.Length==0&& J //B.pfinger[B.Length-1]!=0)成立，所述修剪可通过向A前加0或调用 //BigDivision函数对A的部分高端数据进行处理，算出部分高端商数 pAfinger,A.pfinger; C.pfinger= C.pfinger，A.Length-B.Length; A.pfinger= A.pfinger，A.Length-B.Length; while(A.pfinger,pAfinger) { A.pfinger= A.pfinger - B.Length; pfinger= C.pfinger-B.Length; C. SuperDivision_Core_1(A, B, C，B.Length);//或用SuperDivision_Core_0 } Y,A; //得到余数 Clear(A, B); //释放FormatReady(A, B)时，所分配的空间 return C.Length; } /////////////// 上述方法及实施例都要求A、B为整数，实际上可将上述方法及实施例推广到A、B含有小数及负数符号的C=A/B求商计算中，对于这样的情况，当A或B中含有小数时，只需将两者都乘以一个整数将A、B都转化为整数，就可使用上述方法进行计算;当A、B含有负数符号时，可以根据A、B的符号确定商数的符号，然后将A、B都转化为正数进行除法计算; V如果要使商数保留v位小数，则将A乘以h，然后运用上述方法计算C=A/B，则所得结果C中的后v位就是商数的小数部分，小数部分的前面就是商数的整数部分。我们甚至还可将该算法推广到开平方的过程中。 湖南茶陵 刘海云 于湛江 2011-10-26 10003 2006.7 18 填表注意事项 10003 2006.7 19