摘自:越快越密网站中的《时间复杂度取决于大整数乘法的大整数除法》一个片断
下面用近似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<=0) return 0 //非法返回0
pCWorkFinger=C.pfinger+i- B.Length;
A2.pA2finger=A.pfinger+i-2;
AC.pfinger = A.pfinger+i-B.Length; //AC就是指当前A中处于工作状态的数据
while(AC.pfinger>= A.pfinger)
{
C1=*(( unsigned CPUInteger *)A2.pfinger)/B1 ;
//其中unsigned CPUInteger *表示在计算机中CPU带宽无符号整数类型的数据,
//如在64比特计算机用*(unsigned _int64*(A2.pfinger))获取(A1*h+A2)
Y=*(( unsigned CPUInteger *)A2.pfinger)- C1*B1 ;
Y=<<(U/2) ;// U 为CPU带宽值,如在64比特计算机中U==64
Y+= *( A2.pfinger-1) ; // 即 Y+= A3 ;
X= B2*C1
if(X> Y) //这是由于C1大于正确值
{
X= X-Y;//此时 X==C1 (B1h+B2)- (A1h2+A2h1+A3)
C1= C1- X/(B1h+B2);//这行和下面一行扣除C1超出部分,
if(X%(B1*h+B2)) C1= C1-1;
}
AC=AC -B*C1 ; //计算A=A-B*C1hk-1 ;
if(AC <0) //即if(A<0)
{
AC = AC+B ; //计算A=A+Bhk-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函数使用其他常规大整数除法的算法。
其他算法涉及繁琐的推理过程,导致文件达到342KB,因此这里实在放不下,如果你要了解另一个大整数除法就自己到越快越密网站去下载吧
[培训]内核驱动高级班,冲击BAT一流互联网大厂工作,每周日13:00-18:00直播授课