最快的开方算法.doc

当前位置:首页>资讯>技术文章>文章内容最快的开方算法作者:power来源:网络点击:632日期:2007-09-03最快的开平方算法(中值定理法)作者:李义2006关键词:最快开平方根算法中值定理开方整数平方数中值定理:设a、b、c为顺序排列间距为P的3个整数,A、B、C是它们的平方则有:b2=(a2+c2)/2-R,即:B=(A+C)/2-R其中:修正值R=P2特别地,如果间隔P=1、2、4、8、16、…2n(或Pn=2Pn-1)时则:修正值R=1、4、16、64、256、…22n(或Rn=4Rn-1)证明:已知:a=b+Pc=b-P有:a2=(b+P)2=b2+2Pb+P2c2=(b-P)2=b2-2Pb+P2则:a2+c2=2b2+2P2即:b2=(a2+c2)/2-P2特别地当:间隔P=2n=2*2n-1=2Pn-1时(n为自然数)则:修正值R=P2=22n=(2Pn-1)2=4(Pn-1)2=4Rn-1(证明完)根据以上定理,可以实现整数快速开平方根计算:先构建一个长度为N的数组1:数组长N=Ni+112345…间隔P=2Pi2481632…修正值R=4Ri4**********…以及一个对应2PN(这里N=4、2PN=32)的典型数和它的平方数组2:按N=4间隔排列的数d=di+2PN326496128160192224256…该数的平方D=d21024409692161638425600368645017665536…显然,N值越大则数组2越小、程序代码效率越高、用时(插值次数)越多。以2字节整数开方为例的计算流程如下:其中,被开方数D(范围0~65536),其平方根d(范围0~256)注:1、查表可以从任何位置开始,对计算速度影响不大。其中D=0、D=1、D=Di、D>65280判断可以省去。2、此算法完全没有乘法试算,其1/2、1/4除法运算可由二进制移位简单实现,且为完全补偿后的精确插值,所以递归速度非常快(这里4次)。3、最后运算已经包括了小数部分的精确4舍5入算法。4、此算法略加改动,即可实现更长字节整数或定长浮点数平方根精确解,其逆运算也可以实现乘方运算。一个C语言实例://sqrt_2中值定理法开平方程序(直接查表-插值)//输入D(两字节无符号整数)//输出d(一字节无符号整数)chara,b,c,p;intA,B,C,D,R,K;voidmain(){D=11111;//被开方数if(D>50176){A=0;a=0;C=50176;c=224;break;};//查表if(D>36864){A=50176;a=224;C=36864;c=192;break;};if(D>25600){A=36864;a=192;C=25600;c=160;break;};if(D>16384){A=25600;a=160;C=16384;c=128;break;};if(D>9216){A=16384;a=128;C=9216;c=96;break;};if(D>4096){A=9216;a=96;C=4096;c=64;break;};if(D>1024){A=4096;a=64;C=1024;c=32;break;};A=1024;a=32;C=0;c=0;break;p=16;R=256;//初始化数据do{b=c+p;B