1、A=A1hi-1A2hi-2A3hi-3Ai-1h1Ai （5）其中iZ，A1H2， ArH （ 1ri,且r为整数）,h为进制基数，用AH表示A的前m项，即 AH=A1hi-1A2hi-2A3hi-3Am-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-1B2hj-2B3hj-3Bj-1h1Bj（9）其中jZ，B1H2， BrH （ 1rj,且r为整数）,h为进制基数用BH=（B1B2B3Bm-1Bm）hhj-m
2、表示B的前m项，即 BH=B1hj-1B2hj-2B3hj-3Bm-1hj-（m-1）Bmhj-m（10）其中mj设B=BHBEBE=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，
3、WrH （ 1rn,且r为整数）,0fW1，其中h为进制基数根据前面的陈述可知: A/BHA/B 即WC下面进行理论推导的第一大步骤,讨论i、j和k的关系:C=A/B=（A1hi-1A2hi-2A3hi-3Ai-1h1Ai）/Bhi/B=hi/（B1hj-1B2hj-2B3hj-3Bj-1h1Bj）hi/B1hj-1得到 Chi-j1/B1即 C1hk-1C2hk-2C3hk-3Ck-1h1CkfChi-j1/B1hk-1hi-j1 ki-j2 （13）C=A/B =（A1hj-1A2hj-2Aj-1hAj）hi-j/B （Aj1hi-（j1）Ai-1h1Ai）/B为便于表述设：AJ=A1hj
4、-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-jC1hk-1C2hk-2C3hk-3Ck-1h1CkfChi-jhkhi-jki-j 又结合（13）可得当AJB时，k=i-j1 （16）接下来，推导当AJB时，k与i-j的关系：A1hi-1/B=A1hi-1/（B1hj-1B2hj-2B3hj-3Bj-1h1Bj）A1hi-1/hjCA1hi-1-j将（12）代入得 C1hk-1C2hk-2C3hk-3Ck-1h1CkfCA1hi-1-
5、j hkhi-1-jki-j-1 （17）因为AJB，且AJ和B都是整数，因此可得AJ1B又由C=A/B得C= （A1hj-1A2hj-2A3hj-3Aj-1hAj）hi-j/B（Aj1hi-（j1）Ai-1h1Ai）/B（A1hj-1A2hj-2A3hj-3Aj-1hAj）hi-j/Bhi-j/B=（A1hj-1A2hj-2A3hj-3Aj-1hAj1）hi-j/B=（AJ1）hi-j/BBhi-j/B=hi-jC1hk-1C2hk-2C3hk-3Ck-1h1CkfChi-jki-j1 结合（17）可得 当AJB时，k=i-j下面进行理论推导的第二大步骤,讨论C中k和W中n的关系:设: P=
6、W-C则有 P=A/BH-A/（BHBE）=BEA/（BHBE）/BH=CBE/BH即有P/C=BE/BH=（Bm1hj-（m1）Bm2hj-（m2）Bm3hj-（m3）Bj-1hBj）/BHhj-m/BH=hj-m/（B1hj-1B2hj-2B3hj-3Bm-1hj-（m-1）Bmhj-m）hj-m/（B1hj-1）h1-mP/Ch1-m（W-C）/Ch1-mW/C1h1-m1h1-mW/C （19）则有1h1-mW/C=（W1hn-1W2hn-2W3hn-3Wn-1h1WnfW）/Chn-1/C=hn-1/（C1hk-1C2hk-2C3hk-3Ck-1h1CkfC）hn-1/hk1h1-m
7、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）W
8、mhn-m）/（C1hk-1C2hk-2C3hk-3Ck-1h1CkfC）=（W1hn-1W2hn-2Wm-1hn-（m-1）Wmhn-m）/（C1hk-1C2hk-2C3hk-3Cm-1hk-（m-1）Cmhk-mhk-m） （20）先将n=k代入（20）得 1h1-m（W1hk-1W2hk-2Wm-1hk-（m-1）Wmhk-m）/（C1hk-1C2hk-2C3hk-3Cm-1hk-（m-1）Cmhk-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
9、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-Wm）（C1hm-1C2hm-2C3hm-3Cm-1hCm）h1-m（C1-W1）hm-1（C2-W2）hm-2（Cm-1-Wm-1）h（Cm-Wm）h0（C1-W1）hm-2（C2-W2）hm-3（Cm-1-Wm-1）（Cm-Wm）/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-
10、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=W1W1=1，将W1=1代入（24）可得 （1-0）hm（W2-C1）hm-1
11、（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-1W
12、2hm-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=（ W1W2W3
13、Wnm-k-1）hhk-m1（ Wnm-kWnm-k+1Wn-1Wn）hA/BH/hk-m1=（ W1W2W3Wnm-k-1）h（28）当n=k时，从（28）显然可得，A/BH/hk-m1=（ W1W2W3Wm-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（C1C2C3
14、Cm-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+2Ck-1Ck）h上式中的（C1C2C3Cm-1）h就可利用结论3即（31）来计算，设WL= A/BH/hk-m1，CL=（C1C2C3Cm-1）h,计算CL方法如下：1 计算WL=A/BH/hk-m1=（A1A2A3Ai-1Ai）h/（B1B2B3Bm-1Bm）h/hk-m1，并计算AA-BHWLhk-m1 其中表示将右边的计算结果赋给左边用快速的大整数乘法计算WL
15、BE计算AA-WLBEhk-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则应从
16、高位算起，计算过程可分为以下几步:计算CL计算AA-（BLhk/2BR）CLhk/2计算CR计算AA-（BLhk/2BR）CR仔细分析就会发现，如果k/2I （I为大于2的正整数次幂的常数），适当修改和，就可在中再对CL分治，在中再对CR分治，这样计算余数Y就变成了一个递归函数的运算了。修改之后，得到的计算方法如下：1 判断当前要计算的商数C长度k是不是等于某整数N，若是，则采用预定算法计算C，并计算AA-B1N+FC ，然后退出；若不是，则执行下一步；其中所述A就是从A中当前低端定位点的数位开始向高位延伸到第1个非0数位共同构成的大整数（如果没有非0数，则A表示0），A中当前低端定位点的计算
17、方法请参后面的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；
18、其中所述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；在上述计算完成之后，
19、余数Y=A，这样就完成了求模余的计算，同时也完成了计算整除商数的过程。下面用近似于C+和JAVA的函数伪码表示上述运算流程如下：voidSuperDivision_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
20、.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中，第二个参数表示指向除数的指针，第三个参数表示/除数长度，MinD
21、ivision函数的功能是计算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_
22、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）;
23、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（AR0）/小概率事件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都是大整数对象，分别对应if（k=N） /当数值较小时，常规除法更有效，B=BL
