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

说明书 时间复杂度取决于大整数乘法的大整数除法技术领域 本文主要提供一种特殊的分治递归运算的大整数除法（包括整除的商值及整除后取余数）。这种算法主要应用于计算机领域，尤其是加密技术中。论文背景 当前公开或使用的大整数除法即使采用Knuth的经典名著“The Art of Computer Programming”的第4.3.1节中的猜商值公式来计算，也需要多次试运算，所有这些大整数除法最大的缺点是时间复杂度:T(n) = O(n2)这与大整数乘法相比差远了。因此减少试运算的次数，降低时间复杂度对大整数除法具有特别重要的意义。本文依据全新的计算理论，构造了独特的大整数除法计算方法，文中实施例使试运算出现的概率远低于现有算法，即使出现也只需一次加法运算,不仅如此，更为重要的是本文采用特殊的分治递归的方法充分利用大整数乘法，使大整数除法的时间复杂度等于大整数除法中所采用的大整数乘法的时间复杂度，例如大整数除法中采用Karatsuba乘法加速时，本文中的大整数除法时间复杂度:T(n) = O(nlog23)，如果采用其他更快的大整数乘法，本算法会更快，这就使数值很长的大整数除法的计算速度大幅提高，例如当被除数的长度为4194304个四字节，除数长度为2097152个四字节时，本算法中采用Karatsuba乘法加速时的速度为现有大整数除法速度的30倍左右。论文内容本文在这部分将推出一种全新的大整数除法计算理论，并利用该理论构造分治的大整数除法，在分治中充分利用大整数乘法，以达到加速目的。请看下面的推理：设大整数运算过程中采用h（大于1的整数）进制，正整数集合：Z=x| x0并且 x=x 集合1：H= x| 0xh 并且x为整数集合2：H2=x| 1xh 并且x为整数任何有限长度的大整数除法都可转化为非负大整数的除法，因此除了最后一段外，下文只涉及非负大整数除法，非负大整数除法可表示如下：C=A/B (A0, B0, C0并且A和B都是整数) （1）当A=0时，显然C=0， （2）当AB时，显然C的整数部分为0， （3）当AB时，可通过将被除数和除数都乘以hm从而使A和B都转化为不小于hm的整数，并使结果C保持不变，其中m2且m Z，因此（1）式在排除（2）、（3）后，可转化为下式：C=A/B (AB，Bhm, m2, C0且A、B和m都是正整数) （4）在（4）中A=(A1A2A3Ai-1Ai)h可用多项式表示如下：A=A1hi-1 A2hi-2 A3hi-3 Ai-1h1 Ai （5）其中iZ，A1H2， ArH ( 1ri,且r为整数), h为进制基数，用AH表示A的前m项，即 AH=A1hi-1 A2hi-2 A3hi-3 Am-1hi-(m-1) Amhi-m （6）设A=AHAE （7）则有 AE=Am1hi-(m1)Am2hi-(m2)Am3hi-(m3)Ai-1hAi （8）在（4）中B=(B1B2B3Bj-1Bj)h可用多项式表示如下：B=B1hj-1 B2hj-2 B3hj-3 Bj-1h1 Bj （9）其中jZ，B1H2， BrH ( 1rj,且r为整数), h为进制基数用BH=(B1B2B3Bm-1Bm)hhj-m表示B的前m项，即 BH=B1hj-1B2hj-2 B3hj-3Bm-1hj-(m-1)Bmhj-m （10）其中mj设B=BHBE则有 BE=Bm1hj-(m1)Bm2hj-(m2)Bm3hj-(m3)Bj-1hBj （11）在（4）中C=(C1C2C3Ck-1Ck)hfC可用多项式表示如下：C=C1hk-1C2hk-2C3hk-3Ck-1h1CkfC （12）其中kZ，C1H2 ，CrH ( 1rk,且r为整数), 0fC1， h为进制基数设 W=A/BH则W=( W1W2W3Wn-1Wn)hfW可用多项式表示为 W=W1hn-1W2hn-2W3hn-3Wn-1h1WnfW （12_H） 其中nZ，W1H2， WrH ( 1rn,且r为整数), 0fW1，其中h为进制基数根据前面的陈述可知: A/BHA/B 即WC下面进行理论推导的第一大步骤,讨论i、j和k的关系:C=A/B=(A1hi-1A2hi-2A3hi-3Ai-1h1Ai)/B hi/B = hi/(B1hj-1B2hj-2B3hj-3Bj-1h1Bj)hi/B1hj-1得到 Chi-j1/B1 即 C1hk-1C2hk-2C3hk-3Ck-1h1CkfC hi-j1/B1 hk-1hi-j1 ki-j2 （13）C=A/B =(A1hj-1A2hj-2Aj-1hAj) hi-j/B (Aj1hi-(j1)Ai-1h1Ai)/B为便于表述设：AJ =A1hj-1A2hj-2A3hj-3Aj-1hAj （14） C=AJhi-j/B(Aj1hi-(j1)Ai-1h1Ai)/B (15)显然当AJB时，C=A/Bhi-j(Aj1hi-(j1)Ai-1h1Ai)/Bhi-j C1hk-1C2hk-2C3hk-3Ck-1h1CkfChi-j hkhi-j ki-j 又结合（13）可得当AJB时，k=i-j1 （16）接下来，推导当AJ B时，k与i-j的关系：C=A/B=(A1hi-1A2hi-2A3hi-3Ai-1h1Ai) /BA1hi-1/B= A1hi-1/(B1hj-1B2hj-2B3hj-3Bj-1h1Bj) A1hi-1/hj CA1hi-1-j将（12）代入得 C1hk-1C2hk-2C3hk-3Ck-1h1CkfC A1hi-1-j hk hi-1-j ki-j-1 （17）因为AJ B，且AJ和B都是整数，因此可得AJ1B 又由C=A/B得C= (A1hj-1A2hj-2A3hj-3Aj-1h Aj)hi-j/B(Aj1hi-(j1)Ai-1h1Ai)/B(A1hj-1A2hj-2A3hj-3Aj-1h Aj)hi-j/Bhi-j/B=(A1hj-1A2hj-2A3hj-3Aj-1h Aj1)hi-j/B =(AJ1)hi-j/B Bhi-j/B=hi-j C1hk-1C2hk-2C3hk-3Ck-1h1CkfC hi-j ki-j1 结合（17）可得 当AJ B时，k=i-j下面进行理论推导的第二大步骤,讨论C中k和W中n的关系:设: P=W-C则有 P= A/BH -A/(BHBE) =BEA/(BHBE)/BH=CBE/BH即有 P/C=BE/BH=(Bm1hj-(m1)Bm2hj-(m2)Bm3hj-(m3)Bj-1hBj)/BH hj-m/BH =hj-m/( B1hj-1B2hj-2B3hj-3Bm-1hj-(m-1)Bmhj-m)hj-m/(B1hj-1)h1-m P/Ch1-m （W-C）/Ch1-m W/C1h1-m 1h1-m W/C （19）则有 1h1-m W/C=(W1hn-1W2hn-2W3hn-3Wn-1h1WnfW)/Chn-1/C=hn-1/(C1hk-1C2hk-2C3hk-3Ck-1h1CkfC )hn-1/hk 1h1-m hn-1-k 由于m2，h2所以有 n-1-k0 又由WC可推出nk,由这两者可得 n=k 或 n=k1下面进行理论推导的第三大步骤,讨论C多项式和W多项式中前m项的关系:因为0Cm+1hk-m-1Cm+2hk-m-2Cm+3hk-m-3Ck-1h1CkfChk-m所以可设 Cm+1hk-m-1Cm+2hk-m-2Cm+3hk-m-3Ck-1h1CkfChk-m并且01由（19）得 1h1-m(W1hn-1W2hn-2W3hn-3Wn-1h1WnfW)/C (W1hn-1W2hn-2W3hn-3Wm-1hn-(m-1)Wmhn-m)/C=(W1hn-1W2hn-2W3hn-3Wm-1hn-(m-1)Wmhn-m)/ (C1hk-1C2hk-2C3hk-3Ck-1h1CkfC)=(W1hn-1W2hn-2Wm-1hn-(m-1)Wmhn-m)/(C1hk-1C2hk-2C3hk-3Cm-1hk-(m-1)Cm hk-mhk-m) （20）先将n=k代入（20）得 1h1-m(W1hk-1W2hk-2Wm-1hk-(m-1)Wmhk-m)/(C1hk-1C2hk-2C3hk-3Cm-1hk-(m-1)Cm hk-mhk-m) =(W1hm-1W2hm-2Wm-1hWm)/(C1hm-1C2hm-2Cm-1hCm) 整理得 (C1-W1)hm-1(C2-W2)hm-2(Cm-1-Wm-1)h(Cm-W m)(C1hm-1C2hm-2C3hm-3Cm-1hCm)h1-m0 （21） 由（21）得 0(C1-W1)hm-1(C2-W2)hm-2(Cm-1-Wm-1)h(Cm-W m)(C1hm-1C2hm-2C3hm-3Cm-1hCm)h1-m(C1-W1)hm-1(C2-W2)hm-2(Cm-1-Wm-1)h(Cm-W m)h0(C1-W1)hm-2(C2-W2)hm-3(Cm-1-Wm-1)(Cm-W m)/h1(C1-W1)hm-2(C2-W2)hm-3(Cm-1-Wm-1)11考虑到定义域可推出0(C1-W1)hm-2(C2-W2)hm-3(Cm-1-Wm-1)1 (W1hm-2W2hm-3Wm-1)-(C1hm-2C2hm-3Cm-1)1结合 WC 推出当n=k时，则必有结论1 （23） W1hm-2W2hm-3Wm-1=C1hm-2C2hm-3Cm-1或 W1hm-2W2hm-3Wm-1=C1hm-2C2hm-3Cm-11 即(C1C2C3Cm-1)h = ( W1W2W3Wm-1)h 或者 (C1C2C3Cm-1)h = ( W1W2W3Wm-1)h-1将n=k1代入（20）得 1h1-m(W1hmW2hm-1Wm-1h2Wmh)/(C1hm-1C2hm-2C3hm-3Cm-1h1Cm) （24） W1hm/hm=W1 W1=1， 将W1=1代入（24）可得 (1-0)hm(W2-C1)hm-1(W3-C2)hm-2(Wm-2-Cm-3)h3(Wm-1-Cm-2)h2(Wm-Cm-1)h-Cm-(C1hm-1C2hm-2C3hm-3Cm-1h1Cm)h1-mh （25） (1-0)hm(W2-C1)hm-1(W3-C2)hm-2(Wm-2-Cm-3)h3(Wm-1-Cm-2)h2(Wm-Cm-1)hCmh (1-0)hm-1(W2-C1)hm-2(W3-C2)hm-3(Wm-2-Cm-3)h2(Wm-1-Cm-2)h(Wm-Cm-1)(Cm)/h1 (1-0)hm-1(W2-C1)hm-2(W3-C2)hm-3(Wm-2-Cm-3)h2(Wm-1-Cm-2)h(Wm-Cm-1)1 (hm-1W2hm-2W3hm-3Wm-1hWm)-(C1hm-2C2hm-3Cm-2hCm-1)1又因(hm-1W2hm-2W3hm-3Wm-1hWm)(C1hm-2C2hm-3Cm-2hCm-1) ，所以当n= k1时，则必有结论2 （26） (W1hm-1W2hm-2W3hm-3Wm-1hWm)-(C1hm-2C2hm-3Cm-2hCm-1)=1 且 W1=1 (C1C2C3Cm-1) =(W1W2W3Wm-1Wm) -1 （27）下面进行理论推导的第四大步骤,讨论用分治法计算C多项式的整数部分:由前面论述可知：W整=A/BH = ( W1W2W3Wn-1Wn)hfW = ( W1W2W3Wn-1Wn)h= ( W1W2W3W nm-k-1)hhk-m1( Wnm-kW nm-k+1Wn-1Wn)h A/BH / hk-m1 = ( W1W2W3W nm-k-1)h （28）当n=k时，从（28）显然可得，A/BH / hk-m1 =( W1W2W3W m-1)h 此时结合（23）可得(C1C2C3Cm-1)h =A/BH / hk-m1 （29）或者 (C1C2C3Cm-1)h =A/BH / hk-m1-1当n=k1时，从（28）显然可得，A/BH / hk-m1 =(W1W2W3Wm-1Wm)h此时结合（27）可得(C1C2C3Cm-1)h =A/BH / hk-m1 -1 （30） 综合（29）、（30）就会发现不论n、k的关系如何，都可得结论3(C1C2C3Cm-1)h =A/BH / hk-m1或者 (C1C2C3Cm-1)h =A/BH / hk-m1-1 （31）有了结论3，就为分治计算定了基础。C整=(C1C2C3Ck-1Ck)h=(C1C2C3Cm-1)hhk-m1(CmCm+1Cm+2C k-1C k)h上式中的(C1C2C3Cm-1)h就可利用结论3即（31）来计算，设WL= A/BH /hk-m1，CL=(C1C2C3Cm-1)h ,计算CL方法如下： 计算WL=A/BH /hk-m1= (A1A2A3Ai-1Ai)h / (B1B2B3Bm-1Bm)h /hk-m1 ，并计算AA- BHWLhk-m1 其中表示将右边的计算结果赋给左边用快速的大整数乘法计算WLBE 计算AA- WLBE hk-m1 其中WLBE已在完成 判断A0是否成立，若成立则计算AABhk-m1，并计算WLWL-1 完成赋值CLWL下面依据本文的计算理论构造特殊的分治递归的方法，使大整数除法的时间复杂度等于大整数除法中所采用的大整数乘法的时间复杂度。首先请看针对特殊情况的分析，设j=k=2r，A=(BLhk/2BR)(CLhk/2CR)Y 其中，rZ且r2，BL、BR、CL、CR、Y都是非负整数，BL0，Y(BLhk/2BR)则 Y=A-(BLhk/2BR)(CLhk/2CR)=A-(BLhk/2BR)CLhk/2-(BLhk/2BR)CR如果已知A、B=BLhk/2BR 要求余数Y则应从高位算起，计算过程可分为以下几步:计算CL计算AA-(BLhk/2BR)CLhk/2计算CR计算AA-(BLhk/2BR)CR仔细分析就会发现，如果k/2I (I为大于2的正整数次幂的常数)，适当修改和，就可在中再对CL分治，在中再对CR分治，这样计算余数Y就变成了一个递归函数的运算了。修改之后，得到的计算方法如下： 判断当前要计算的商数C长度k是不是等于某整数N，若是，则采用预定算法计算C，并计算AA-B1N+FC ，然后退出；若不是，则执行下一步；其中所述A就是从A中当前低端定位点的数位开始向高位延伸到第1个非0数位共同构成的大整数（如果没有非0数，则A表示0），A中当前低端定位点的计算方法请参后面的SuperDivision_Core_0、SuperDivision_Core_1这两个函数中的说明；B1N+F就是从B的高位顶点开始向低位延伸的N+F位数共同构成的大整数；N应为2的非零整数次方,F=1,由于分治计算时高位商数在完成与除数的部分乘积减后，就开始计算低一位的商数，因此会暂时留下较多的剩余数据，当F=1时，需要试运算的概率较高，当F=2时，需要试运算的概率较小，当F=3时出现试运算的概率就很小，因此设置F=3比较好，当然也可设置F为更大的值，但太大会影响速度；将C空间等分为存放高位商数CL和存放低位商数CR两部分；递归计算CL ；计算AA-Bk/2+F+1k+FCL；其中所述Bk/2+F+1k+F表示B中从高位第k/2+F+1位数开始向低位延伸到k+F位数所构成的大整数；由于前面的运算已算到Bk/2+F这项，因此只能将Bk后的F位数添加在Bk后面构成一个具有k/2位数的大整数参与运算，以便使用大整数乘法达到加速目的，Bk/2+F+1k+FCL就是一个k/2位大整数乘以k/2位大整数的运算，这样就可采用快速乘法来加速；判断A是否小于0，若是，则计算AAB1k+F；其中B1k+F表示B中从高位第1位数开始向低位延伸到第k+F位数所构成的大整数；递归计算CR ；计算AA-Bk/2+F+1k+FCR；判断A是否小于0，若是，则计算AAB1k+F；在上述计算完成之后，余数Y=A，这样就完成了求模余的计算，同时也完成了计算整除商数的过程。下面用近似于C+和JAVA的函数伪码表示上述运算流程如下：void SuperDivision_Core_0(A, B, C,int k ) /调用时A、 B都是大整数对象，分别对应 /被除数、除数、应在A、B后面预留F位空间，并将B中预留空间归0，计算完成之/后，结束时，模余在A中，商数的整数部分在C中，当然应用时这些参数可能就是一/个整数类型或字符串类型的数组或指针以及相关变量（含指针）共同来实现，调用（不/含自身递归）该函数之前应满足AJB，参数k表示除数长度，也表示商数的数位长/k=2r，rZ， if(A!=NULL) AT.pfinger=A.pfinger+ k*2； /首次调用时，设置好A中当前高端定位点指针AT.pfinger， /AT最好为static对象（含指针）if(k=N) /当数值较小时，常规除法更有效， AC.pfinger=AT.pfinger-(N*2+F); /使AC.pfinger指向A中当前低端定位点/ AC就是从A中当前低端定位点的数位开始向高位延伸到第1个非0数位共同构成/的大整数（如果没有非0数，则AC表示0）MinDivision(AC,B.pfinger-F,N+F,C.pfinger );/在MinDivision中，第二个参数表示指向除数的指针，第三个参数表示/除数长度，MinDivision函数的功能是计算C，并计算A=A-BC，/此处AC与A对应，不允许给C.pfingerN赋值，否则就会出现0覆盖AT.pfinger=AT.pfinger-N;return；B=BLhk/2+BR ; /将B分割为两半，并且BR.pfinger=B.pfinger/ BL .pfinger=B.pfinger+k/2 ，BL .Length = BR .Length =k/2 ,C=CLhk/2+CR ; /将C分割为两半，并且CR.pfinger=C.pfinger/ CL.pfinger=C.pfinger+k/2 ，CL .Length =CR .Length =k/2 ,SuperDivision_Core_0(NULL , BL , CL ，k/2); /递归SetCurrentA(AT ，AL); / 设置AL，如设置AL.pfinger=AT.pfinger -k-F; 使/AL.pfinger指向A中当前低端定位点等AL=AL-SuperMultiply(BR.pfinger -F,k/2, CL.pfinger ,k/2); / SuperMultiply的功能是计算两个大整数的乘积，此处AL与A对应， if(AL0) /小概率事件AL= AL(BhFBk+1hF-1 Bk+2hF-2Bk+3hF-3Bk+F); CL= CL-1；SuperDivision_Core_0(NULL, BL, CR ，k/2); /递归SetCurrentA(AT ，AR ); /设置好AR，如设置AR .pfinger=AT.pfinger -k-F; 使/AR.pfinger指向A中当前低端定位点等AR=AR-SuperMultiply(BR.pfinger -F,k/2,CR.pfinger ,k/2); /此处AR与A对应，if(AR 0) /小概率事件AR=AR(BhFBk+1hF-1 Bk+2hF-2Bk+3hF-3Bk+F); CR= CR-1； return ; 容易看出函数SuperMultiply_0中两个递归后面的代码高度相似，并且很容易实现代码复用，将SuperMultiply_0修改后就得到下面的伪码函数void SuperDivision_Core_1(A, B, C,int k ) /调用时A、 B都是大整数对象，分别对应 /被除数、除数、应在A、B后面预留F位空间，并将B中预留空间归0，计算完成之/后，结束时，模余在A中，商数的整数部分在C中，当然应用时这些参数可能就是一/个整数类型或字符串类型的数组或指针以及相关变量（含指针）共同来实现，调用（不/含自身递归）该函数之前应满足AJB，参数k表示除数长度，也表示商数的数位长/k=2r，rZ， if(A!=NULL) AT.pfinger=A.pfinger+ k*2； /首次调用时，设置好A中当前高端定位点指针AT.pfinger， /AT最好为static对象（含指针）if(k=N) /当数值较小时，常规除法更有效， AC.pfinger=AT.pfinger-(N*2+F); /使AC.pfinger指向A中当前低端定位点/ AC就是从A中当前低端定位点的数位开始向高位延伸到第1个非0数位共同构成/的大整数（如果没有非0数，则AC表示0）MinDivision(AC,B.pfinger-F,N+F,C.pfinger );/在MinDivision中，第二个参数表示指向除数的指针，第三个参数表示/除数长度，MinDivision函数的功能是计算C，并计算A=A-BC，/此处AC与A对应，不允许给C.pfingerN赋值，否则就会出现0覆盖AT.pfinger=AT.pfinger-N;return；B=BLhk/2+BR ; /将B分割为两半，并且BR.pfinger=B.pfinger/ BL.pfinger=B.pfinger+k/2， BL .Length =BR .Length =k/2 ,C=CLhk/2+CR ; /将C分割为两半，并且CR.pfinger=C.pfinger/ CL.pfinger=C.pfinger+k/2 CL .Length =CR .Length =k/2 , BOOL IsFirstTime=TRUE;ReWork:SuperDivision_Core_1 (NULL, BL , CL ,k/2); /递归SetCurrentA(AT ，AL); / 设置好AL，如设置AL.pfinger=AT.pfinger -k-F; 使/AL.pfinger指向A中当前低端定位点等AL=AL-SuperMultiply (BR.pfinger -F,k/2, CL.pfinger ,k/2); / SuperMultiply的功能是计算两个大整数的乘积，此处AL与A对应， if(AL0) /小概率事件AL= AL(BhFBk+1hF-1 Bk+2hF-2Bk+3hF-3Bk+F); CL= CL-1； if(IsFirstTime) IsFirstTime=FALSE; CL.pfinger=CR.pfinger; goto ReWork; return ; 通过对SuperDivision_Core_1函数的分析就会发现该函数把大整数除法转化为短除MinDivision，两次大整数乘法SuperMultiply，两次减法，以及一些计算量可忽略的辅助运算如指针赋值或移动等，由于本函数已限定被除数的长度为除数的两倍，因此下面以除数长度j来衡量时间复杂度，显然两次减法与除数长度j是线性相关的，由于限制了短除MinDivision的除数的长度为N，因此运算MinDivision所消耗的时间与被除数的长度2j线性相关，并且当j很大时，前述的两次减法与短除所消耗的时间相对大整数乘法SuperMultiply所消耗的时间来讲可忽略不计，因此本文的时间复杂度取决于大整数乘法SuperMultiply的时间复杂度，例如SuperMultiply采用Karatsuba乘法时，本文中的大整数除法时间复杂度:T(n) = O(nlog23) 。本人根据上述SuperDivision_Core_1函数算法写出的代码采用了Karatsuba乘法，并进行了测试，测试方法是，随机产生两个长度为j个四字节（h=2564）的大整数B、C及一个小于B的大整数Y，并利用Karatsuba乘法计算A=BC，接着计算AA+Y，然后用SuperDivision_Core_1算法计算A/B商数的整数部分C和余数Y，然后比较C=C和Y=Y这两者是否成立，经过大量测试都验证这两者成立，在测试中还将计算A=BC时Karatsuba乘法所耗费的时间和计算A/B时SuperDivision_Core_1算法所耗费的时间进行了对比分析，发现在j64个四字节的条件下SuperDivision_Core_1算法所消耗的时间约为Karatsuba乘法所消耗时间的两倍左右。当然，本算法也可调用其他大整数乘法如ToomCook算法、SchnhageStrassen 算法、Frer算法等。在SuperDivision_Core_0算法和SuperDivision_Core_1算法中都调用了MinDivision短除函数来逐位计算当前最高位商数。接下来，讨论如何计算最高位商数C1： A/(B1hB2) hj-2)/ hk-21 (A1hi-1 A2hi-2 A3hi-3 Ai-1h1 Ai) /(B1hB2) hj-2)/ hk-21 (A1hi-1 A2hi-2 A3hi-3 Ai-1h1 Ai) /(B1hB2) hj+k-3) (A1hi-1A2hi-2A3hi-3)(A4hi-4 Ai-1h1 Ai)/(B1hB2) hj+k-3) 结合 ij+k 或 ij+k-1 可得A/(B1hB2) hj-2)/ hk-21(A1hi-1A2hi-2A3hi-3)/(B1hB2) hj+k-3)(A1hi+2A2hi+1A3hi)/(B1hB2) hj+k) （34） 将ij+k代入（34）得：A/(B1hB2) hj-2)/ hk-21(A1h2A2h1A3)/(B1hB2) （35）结合结论3即（31）可得：当ij+k即AJB时， （39） C1(A1h2A2h1A3)/(B1hB2) 或C1(A1h2A2h1A3)/(B1hB2)-1 将ij+k-1代入（34）得：A/(B1hB2) hj-2)/ hk-21(A1hA2A3/h)/(B1hB2) (A1hA2)/(B1hB2) 结合结论3即（31）可得：当ij+k-1即AJB时， （40）C1(A1hA2)/(B1hB2) 或C1(A1hA2)/(B1hB2)-1 如果当AJB时，在A前添加一个0项，将0作为A的第一项，则此时也可使用（39）来计算C1 ，这样就将计算C1的公式统一为（39），无需考虑（40）； 根据（39）要计算C1首先得计算(A1h2A2h1A3)/(B1hB2)，为充分利用CPU的带宽，通常h为CPU带宽的一半，例如在64比特CPU计算机中h=232，如果将(A1h2A2h1A3)做为一个整体来处理的话，就会超出CPU的带宽，因此必须设计一种方法来计算(A1h2A2h1A3)/(B1hB2)；下面用近似C+语言的伪码的写出一种在CPU带宽为U比特计算机中计算C1(A1h2A2h1A3)/(B1hB2)的方法：C1(A1hA2)/B1 ; if(C1h) C1h-1;Y=(A1hA2)- C1*B1 ; Y=U/2 ； / U 为CPU带宽值，如在64比特计算机中U=64Y= A3 ; X= B2*C1if(X Y) /这是由于C1大于正确值 X= X-Y；/其结果 X=C1* (B1hB2)- (A1h2A2h1A3) C1= C1- X/(B1hB2)；/这行和下面一行扣除超出部分，就得到正确的C1 if(X%(B1hB2) C1= C1-1；这样就完成了C1(A1h2A2h1A3)/(B1hB2)的计算，此时要么C1=C1要么C1=C1-1。在得到C1后，按照下述近似C+语言的伪码提供的方法来计算高位商数C1 ：C1=C1；A=A-B*C1hk-1 ; if(A0) A=ABhk-1 ; C1=C1-1； 在得到正确的高位商数C1后，再按照上述方法来计算C2，从高位到低位循环计算高位商数，这样就可实现一种常规大整数除法运算。下面用近似C+语言的伪码将这种方法写出来：BigDivision(A, B, C ) /调用时A, B,都是大整数对象，分别对应被除数、除 /数、应在A前面至少预留1位空间，如果会出现A.Length=1，则A后面至/少预留1位空间，如果会出现B.Length=1，则B后面也至少预留1位空间，/并将预留空间归0，计算完成之后，结束时模余在A中，商数的整数部分在C中，/当然应用时这些参数可能就是一个整数类型或字符串类型的数组或指针，i=A.Length; /得到A长度if(B.Length=0|i= A.pfinger) C1*( unsigned CPUInteger *)A2.pfinger)/B1 ; /其中unsigned CPUInteger *表示在计算机中CPU带宽无符号整数类型的数据，/如在64比特计算机用*(unsigned _int64*(A2.pfinger)获取(A1*hA2)Y=*( unsigned CPUInteger *)A2.pfinger)- C1*B1 ; Y= Y) /这是由于C1大于正确值 X= X-Y；/此时 X=C1 (B1hB2)- (A1h2A2h1A3) C1= C1- X/(B1hB2)；/这行和下面一行扣除C1超出部分， if(X%(B1*hB2) C1= C1-1；AC=AC -B*C1 ; /计算A=A-B*C1hk-1 ; if(AC 0) /即if(A0) AC = ACB ; /计算A=ABhk-1 ;C1=C1-1； *pCWorkFinger=C1 ；pCWorkFinger-1;/每循环一次pCWorkFinger就在C上向低端滑动一个基数位A2.pfinger -1; /每循环一次A2就就在A上向低端滑动一个基数位AC.pfinger -1; /每循环一次AC就在A上向低端滑动一个基数位 当将上述BigDivision单独作为一个大整数除法时已经比现有大整数除法更有效率，因此上面SuperDivision_Core函数（指SuperDivision_Core_0和SuperDivision_Core_1）中的MinDivision函数最好使用BigDivision函数中的算法，即使用BigDivision函数中的算法来计算高位商数，当然不排除MinDivision函数使用其他常规大整数除法的算法。不过MinDivision函数与普通的大整数除法处理细节上稍有差别。参见下表， 行号B1B2B3B4B5B6B7C1C2C3C4C5C6C7R7B1C7B2C7B3C7B4C7B5C7B6C7B7C7R6B1C6B2C6B3C6B4C6B5C6B6C6B7C6R5B1C5B2C5B3C5B4C5B5C5B6C5B7C5R4B1C4B2C4B3C4B4C4B5C4B6C4B7C4R3B1C3B2C3B3C3B4C3B5C3B6C3B7C3R2B1C2B2C2B3C2B4C2B5C2B6C2B7C2R1B1C1B2C1B3C1B4C1B5C1B6C1B7C1A1A2A3A4A5A6A7A8A9A10A11A12A13A14这是一个小学乘法过程表，仔细研究就会发现，普通大整数除法在计算商数中当前高位商数时，就是小学乘法的逆过程，都是每算出一个高位商数就从A中消掉与该高位商数相乘的项，如算出C1后，就消掉R1这行：B1C1 B2C1 B3C1 B4C1 B5C1 B6C1 B7C1 ， 因此接下来计算下一位的高位商数时，就不会受更高位商数的干扰，但在本文中分治法大整数除法的计算路径不是这样，而是在算出高位商数后，利用该高位商数与除数消除所对应行的前几项，就开始计算下一位的高位商数，导致低位商数的计算会受到高位商数的干扰，例如当N=2、F=1时，本算法在算出C1后，就消掉R1这行中的：B1C1 B2C1 B3C1，就开始计算C2 ，从上表中可以看出显然按这种路径计算C2时，R1这行尚未消掉的项B4C1 B5C1 B6C1 B7C1，可能向A4这个位置产生进位，该进位值最大可达h-1,因此会干扰C2的计算，F取值的大小决定了高位商数对低位商数计算的影响大小，根据（31）可知F1就可采用分治法，但当F=1或F=2时往往需要较多的试运算，当设置F=3时，需要