时间复杂度取决于大整数乘法的大整数除法Word文档下载推荐.docx
《时间复杂度取决于大整数乘法的大整数除法Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《时间复杂度取决于大整数乘法的大整数除法Word文档下载推荐.docx（24页珍藏版）》请在冰点文库上搜索。
A=A1hi-1＋A2hi-2＋A3hi-3＋…＋Ai-1h1＋Ai（5）
其中i∈Z，A1∈H2，Ar∈H（1＜r≤i,且r为整数）,h为进制基数，
用AH表示A的前m项，即
AH=A1hi-1＋A2hi-2＋A3hi-3＋…＋Am-1hi-（m-1）＋Amhi-m（6）
设A=AH＋AE（7）
则有
AE=Am＋1hi-（m＋1）＋Am＋2hi-（m＋2）＋Am＋3hi-（m＋3）＋…＋Ai-1h＋Ai（8）
在（4）中B=（B1B2B3…Bj-1Bj）h可用多项式表示如下：
B=B1hj-1＋B2hj-2＋B3hj-3＋…＋Bj-1h1＋Bj（9）
其中j∈Z，B1∈H2，Br∈H（1＜r≤j,且r为整数）,h为进制基数
用BH=（B1B2B3…Bm-1Bm）h×
hj-m表示B的前m项，即
BH=B1hj-1＋B2hj-2＋B3hj-3＋…＋Bm-1hj-（m-1）＋Bmhj-m（10）
其中m＜j
设B=BH＋BE
BE=Bm＋1hj-（m＋1）＋Bm＋2hj-（m＋2）＋Bm＋3hj-（m＋3）＋…＋Bj-1h＋Bj（11）
在（4）中C=（C1C2C3…Ck-1Ck）h＋fC可用多项式表示如下：
C=C1hk-1＋C2hk-2＋C3hk-3＋…＋Ck-1h1＋Ck＋fC（12）
其中k∈Z，C1∈H2，Cr∈H（1＜r≤k,且r为整数）,0≤fC＜1，h为进制基数
设W=A/BH
则W=（W1W2W3…Wn-1Wn）h＋fW可用多项式表示为
W=W1hn-1＋W2hn-2＋W3hn-3＋…＋Wn-1h1＋Wn＋fW（12_H）
其中n∈Z，W1∈H2，Wr∈H（1＜r≤n,且r为整数）,0≤fW＜1，其中h为进制基数
根据前面的陈述可知:
A/BH≥A/B即W≥C
下面进行理论推导的第一大步骤,讨论i、j和k的关系:
C=A/B=（A1hi-1＋A2hi-2＋A3hi-3＋…＋Ai-1h1＋Ai）/B
＜hi/B=hi/（B1hj-1＋B2hj-2＋B3hj-3＋…＋Bj-1h1＋Bj）
≤hi/B1hj-1
得到C＜hi-j＋1/B1
即C1hk-1＋C2hk-2＋C3hk-3＋…＋Ck-1h1＋Ck＋fC＜hi-j＋1/B1
⇒hk-1＜hi-j＋1
⇒k＜i-j＋2（13）
C=A/B
=（A1hj-1＋A2hj-2＋…＋Aj-1h＋Aj）hi-j/B＋（Aj＋1hi-（j＋1）＋…＋Ai-1h1＋Ai）/B
为便于表述设：
AJ=A1hj-1＋A2hj-2＋A3hj-3＋…＋Aj-1h＋Aj（14）
⇒C=AJhi-j/B＋（Aj＋1hi-（j＋1）＋…＋Ai-1h1＋Ai）/B（15）
显然当AJ≥B时，
C=A/B≥hi-j＋（Aj＋1hi-（j＋1）＋…＋Ai-1h1＋Ai）/B≥hi-j
⇒C1hk-1＋C2hk-2＋C3hk-3＋…＋Ck-1h1＋Ck＋fC≥hi-j
⇒hk＞hi-j
⇒k＞i-j
又结合（13）可得
当AJ≥B时，k=i-j＋1（16）
接下来，推导当AJ＜B时，k与i-j的关系：
≥A1hi-1/B=A1hi-1/（B1hj-1＋B2hj-2＋B3hj-3＋…＋Bj-1h1＋Bj）
＞A1hi-1/hj
⇒C＞A1hi-1-j
将（12）代入得
C1hk-1＋C2hk-2＋C3hk-3＋…＋Ck-1h1＋Ck＋fC＞A1hi-1-j
⇒hk＞hi-1-j
⇒k＞i-j-1（17）
因为AJ＜B，且AJ和B都是整数，因此可得
AJ＋1≤B
又由C=A/B得
C=（A1hj-1＋A2hj-2＋A3hj-3＋…＋Aj-1h＋Aj）hi-j/B＋
（Aj＋1hi-（j＋1）＋…＋Ai-1h1＋Ai）/B
＜（A1hj-1＋A2hj-2＋A3hj-3＋…＋Aj-1h＋Aj）hi-j/B＋hi-j/B
=（A1hj-1＋A2hj-2＋A3hj-3＋…＋Aj-1h＋Aj＋1）hi-j/B
=（AJ＋1）hi-j/B
≤Bhi-j/B=hi-j
⇒C1hk-1＋C2hk-2＋C3hk-3＋…＋Ck-1h1＋Ck＋fC＜hi-j
⇒k＜i-j＋1结合（17）可得
当AJ＜B时，k=i-j
下面进行理论推导的第二大步骤,讨论C中k和W中n的关系:
设:
P=W-C
则有P=A/BH-A/（BH＋BE）=BEA/（BH＋BE）/BH=CBE/BH
即有
P/C=BE/BH
=（Bm＋1hj-（m＋1）＋Bm＋2hj-（m＋2）＋Bm＋3hj-（m＋3）＋…＋Bj-1h＋Bj）/BH
＜hj-m/BH
=hj-m/（B1hj-1＋B2hj-2＋B3hj-3＋…＋Bm-1hj-（m-1）＋Bmhj-m）
≤hj-m/（B1hj-1）≤h1-m
⇒P/C＜h1-m
⇒（W-C）/C＜h1-m
⇒W/C＜1＋h1-m
⇒1＋h1-m＞W/C（19）
则有
1＋h1-m＞W/C=（W1hn-1＋W2hn-2＋W3hn-3＋…＋Wn-1h1＋Wn＋fW）/C
≥hn-1/C=hn-1/（C1hk-1＋C2hk-2＋C3hk-3＋…＋Ck-1h1＋Ck＋fC）
＞hn-1/hk
⇒1＋h1-m＞hn-1-k由于m≥2，h≥2所以有
n-1-k≤0又由W≥C可推出n≥k,由这两者可得
n=k或n=k＋1
下面进行理论推导的第三大步骤,讨论C多项式和W多项式中前m项的关系:
因为0≤Cm+1hk-m-1＋Cm+2hk-m-2＋Cm+3hk-m-3＋…＋Ck-1h1＋Ck＋fC＜hk-m
所以可设Cm+1hk-m-1＋Cm+2hk-m-2＋Cm+3hk-m-3＋…＋Ck-1h1＋Ck＋fC＝βhk-m
并且0≤β＜1
由（19）得
1＋h1-m＞（W1hn-1＋W2hn-2＋W3hn-3＋…＋Wn-1h1＋Wn＋fW）/C
≥（W1hn-1＋W2hn-2＋W3hn-3＋…＋Wm-1hn-（m-1）＋Wmhn-m）/C
=（W1hn-1＋W2hn-2＋W3hn-3＋…＋Wm-1hn-（m-1）＋Wmhn-m）/（C1hk-1＋C2hk-2＋C3hk-3＋…＋Ck-1h1＋Ck＋fC）
=（W1hn-1＋W2hn-2＋…＋Wm-1hn-（m-1）＋Wmhn-m）/（C1hk-1＋C2hk-2＋C3hk-3＋…＋Cm-1hk-（m-1）＋Cmhk-m＋βhk-m）（20）
先将n=k代入（20）得
1＋h1-m＞（W1hk-1＋W2hk-2＋…＋Wm-1hk-（m-1）＋Wmhk-m）/（C1hk-1＋C2hk-2＋C3hk-3＋…＋Cm-1hk-（m-1）＋Cmhk-m＋βhk-m）
=（W1hm-1＋W2hm-2＋…＋Wm-1h＋Wm）/（C1hm-1＋C2hm-2＋…＋Cm-1h＋Cm＋β）
整理得
（C1-W1）hm-1＋（C2-W2）hm-2＋…＋（Cm-1-Wm-1）h＋（Cm-Wm）＋β＋（C1hm-1＋C2hm-2＋C3hm-3＋…＋Cm-1h＋Cm＋β）h1-m＞0（21）
由（21）得
0＜（C1-W1）hm-1＋（C2-W2）hm-2＋…＋（Cm-1-Wm-1）h＋（Cm-Wm）＋β＋（C1hm-1＋C2hm-2＋C3hm-3＋…＋Cm-1h＋Cm＋β）h1-m
＜（C1-W1）hm-1＋（C2-W2）hm-2＋…＋（Cm-1-Wm-1）h＋（Cm-Wm）＋β＋h
⇒
0＜（C1-W1）hm-2＋（C2-W2）hm-3＋…＋（Cm-1-Wm-1）＋（（Cm-Wm）＋β）/h＋1
＜（C1-W1）hm-2＋（C2-W2）hm-3＋…＋（Cm-1-Wm-1）＋1＋1
考虑到定义域可推出
0≤（C1-W1）hm-2＋（C2-W2）hm-3＋…＋（Cm-1-Wm-1）＋1
⇒（W1hm-2＋W2hm-3＋…＋Wm-1）-（C1hm-2＋C2hm-3＋…＋Cm-1）≤1
结合W≥C推出
当n=k时，则必有结论1（23）
W1hm-2＋W2hm-3＋…＋Wm-1=C1hm-2＋C2hm-3＋…＋Cm-1
或W1hm-2＋W2hm-3＋…＋Wm-1=C1hm-2＋C2hm-3＋…＋Cm-1＋1
即（C1C2C3…Cm-1）h=（W1W2W3…Wm-1）h
或者（C1C2C3…Cm-1）h=（W1W2W3…Wm-1）h-1
将n=k＋1代入（20）得
1＋h1-m＞（W1hm＋W2hm-1＋…＋Wm-1h2＋Wmh）/（C1hm-1＋C2hm-2＋C3hm-3＋…＋Cm-1h1＋Cm＋β）（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-1＋C2hm-2＋C3hm-3＋…＋Cm-1h1＋Cm＋β）h1-m＜h（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）h＜Cm＋β＋h
⇒（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＋β）/h＋1
⇒（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-1＋W2hm-2＋W3hm-3…＋Wm-1h＋Wm）-（C1hm-2＋C2hm-3…＋Cm-2h＋Cm-1）≤1
又因（hm-1＋W2hm-2＋W3hm-3…＋Wm-1h＋Wm）＞（C1hm-2＋C2hm-3…＋Cm-2h＋Cm-1），所以当n=k＋1时，则必有结论2（26）
（W1hm-1＋W2hm-2＋W3hm-3…＋Wm-1h＋Wm）-（C1hm-2＋C2hm-3…＋Cm-2h＋Cm-1）=1且W1=1
⇒（C1C2C3…Cm-1）=（W1W2W3…Wm-1Wm）-1（27）
下面进行理论推导的第四大步骤,讨论用分治法计算C多项式的整数部分:
由前面论述可知：
W整=[A/BH]
=[（W1W2W3…Wn-1Wn）h＋fW]
=（W1W2W3…Wn-1Wn）h
=（W1W2W3…Wn＋m-k-1）h×
hk-m＋1＋（Wn＋m-kWn＋m-k+1…Wn-1Wn）h
[A/BH/hk-m＋1]=（W1W2W3…Wn＋m-k-1）h（28）
当n=k时，从（28）显然可得，
[A/BH/hk-m＋1]=（W1W2W3…Wm-1）h
此时结合（23）可得
（C1C2C3…Cm-1）h=[A/BH/hk-m＋1]（29）
或者（C1C2C3…Cm-1）h=[A/BH/hk-m＋1]-1
当n=k＋1时，从（28）显然可得，
[A/BH/hk-m＋1]=（W1W2W3…Wm-1Wm）h
此时结合（27）可得
（C1C2C3…Cm-1）h=[A/BH/hk-m＋1]-1（30）
综合（29）、（30）就会发现不论n、k的关系如何，都可得
结论3
（C1C2C3…Cm-1）h=[A/BH/hk-m＋1]
或者（C1C2C3…Cm-1）h=[A/BH/hk-m＋1]-1（31）
有了结论3，就为分治计算定了基础。
C整=（C1C2C3…Ck-1Ck）h
=（C1C2C3…Cm-1）h×
hk-m＋1＋（CmCm+1Cm+2…Ck-1Ck）h
上式中的（C1C2C3…Cm-1）h就可利用结论3即（31）来计算，
设WL=[A/BH/hk-m＋1]，CL=（C1C2C3…Cm-1）h,
计算CL方法如下：
1计算WL=[A/BH/hk-m＋1]
=[（A1A2A3…Ai-1Ai）h/（B1B2B3…Bm-1Bm）h/hk-m＋1]，并计算
A←A-BHWLhk-m＋1其中←表示将右边的计算结果赋给左边
②用快速的大整数乘法计算WLBE
③计算A←A-WLBEhk-m＋1其中WLBE已在②完成
④判断A＜0是否成立，若成立则计算A←A＋Bhk-m＋1，并计算WL←WL-1
⑤完成赋值CL←WL
下面依据本文的计算理论构造特殊的分治递归的方法，使大整数除法的时间复杂度等于大整数除法中所采用的大整数乘法的时间复杂度。
首先请看针对特殊情况的分析，设j=k=2r，A=（BLhk/2＋BR）（CLhk/2＋CR）＋Y其中，r∈Z且r≥2，BL、BR、CL、CR、Y都是非负整数，BL＞0，Y＜（BLhk/2＋BR）
则Y=A-（BLhk/2＋BR）（CLhk/2＋CR）
=A-（BLhk/2＋BR）CLhk/2-（BLhk/2＋BR）CR
如果已知A、B=BLhk/2＋BR要求余数Y则应从高位算起，计算过程可分为以下几步:
①计算CL
②计算A←A-（BLhk/2＋BR）CLhk/2
③计算CR
④计算A←A-（BLhk/2＋BR）CR
仔细分析就会发现，如果k/2>
I（I为大于2的正整数次幂的常数），适当修改②和④，就可在①中再对CL分治，在③中再对CR分治，这样计算余数Y就变成了一个递归函数的运算了。
修改之后，得到的计算方法如下：
1判断当前要计算的商数C长度k是不是等于某整数N，若是，则采用预定算法计算C，并计算A′←A′-B1﹍N+FC，然后退出；
若不是，则执行下一步；
其中所述A′就是从A中当前低端定位点的数位开始向高位延伸到第1个非0数位共同构成的大整数（如果没有非0数，则A′表示0），A中当前低端定位点的计算方法请参后面的SuperDivision_Core_0、SuperDivision_Core_1这两个函数中的说明；
B1﹍N+F就是从B的高位顶点开始向低位延伸的N+F位数共同构成的大整数；
N应为2的非零整数次方,F＞=1,由于分治计算时高位商数在完成与除数的部分乘积减后，就开始计算低一位的商数，因此会暂时留下较多的剩余数据，当F=1时，需要试运算的概率较高，当F=2时，需要试运算的概率较小，当F=3时出现试运算的概率就很小，因此设置F=3比较好，当然也可设置F为更大的值，但太大会影响速度；
②将C空间等分为存放高位商数CL和存放低位商数CR两部分；
③递归计算CL；
④计算A′←A′-Bk/2+F+1﹍k+FCL；
其中所述Bk/2+F+1﹍k+F表示B中从高位第k/2+F+1位数开始向低位延伸到k+F位数所构成的大整数；
由于前面的运算已算到Bk/2+F这项，因此只能将Bk后的F位数添加在Bk后面构成一个具有k/2位数的大整数参与运算，以便使用大整数乘法达到加速目的，Bk/2+F+1﹍k+FCL就是一个k/2位大整数乘以k/2位大整数的运算，这样就可采用快速乘法来加速；
⑤判断A′是否小于0，若是，则计算A′←A′＋B1﹍k+F；
其中B1﹍k+F表示B中从高位第1位数开始向低位延伸到第k+F位数所构成的大整数；
⑥递归计算CR；
⑦计算A′←A′-Bk/2+F+1﹍k+FCR；
⑧判断A′是否小于0，若是，则计算A′←A′＋B1﹍k+F；
在上述计算完成之后，余数Y=A，这样就完成了求模余的计算，同时也完成了计算整除商数的过程。
下面用近似于C++和JAVA的函数伪码表示上述运算流程如下：
voidSuperDivision_Core_0（A,B,C,intk）//调用时A、B都是大整数对象，分别对应
{//被除数、除数、应在A、B后面预留F位空间，并将B中预留空间归0，计算完成之
//后，结束时，模余在A中，商数的整数部分在C中，当然应用时这些参数可能就是一
//个整数类型或字符串类型的数组或指针以及相关变量（含指针）共同来实现，调用（不
//含自身递归）该函数之前应满足AJ＜B，参数k表示除数长度，也表示商数的数位长
//k==2r，r∈Z，
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′-B′C，
//此处AC与A′对应，不允许给C.pfinger[N]赋值，否则就会出现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（AL<
0）{//小概率事件
AL=AL＋（BhF＋Bk+1hF-1＋Bk+2hF-2＋Bk+3hF-3＋…＋Bk+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＋（BhF＋Bk+1hF-1＋Bk+2hF-2＋Bk+3hF-3＋…＋Bk+F）;
CR=CR-1；
return;
容易看出函数SuperMultiply_0中两个递归后面的代码高度相似，并且很容易实现代码复用，将SuperMultiply_0修改后就得到下面的伪码函数
voidSuperDivision_Core_1（A,B,C,intk）//调用时A、B都是大整数对象，分别对应
if（k==N）//当数值较小时，常规除法更有效，
B=BL
升级会员 