1、最快的开平方算法(中值定理法 )作者:李义 2006 关键词:最快 开平方根 算法 中值定理 开方 整数平方数中值定理: 设 a、b、c 为顺序排列间距为 P 的 3 个整数,A 、B 、C 是它们的平方 则有:b2(a 2+c2)/2-R,即:B(A+C)/2-R 其中:修正值 RP2 特别地,如果间隔 P1、2 、 4、 8、 16、2 n (或 Pn=2Pn-1)时 则: 修正值 R1、4、16 、64 、256 、22n (或 Rn4Rn-1) 证明: 已知:ab+P c b-P 有:a 2(b+P)2 b2+2Pb+P2 c2 (b-P)2b2-2Pb+P2 则:a2+c22b2+2
2、P2 即:b2 (a2+c2)/2-P2 特别地 当: 间隔 P2 n2*2 n -12 Pn-1 时(n 为自然数) 则: 修正值 RP222n (2 Pn-1)24(P n-1)24Rn-1 (证明完) 根据以上定理,可以实现整数快速开平方根计算: 先构建一个长度为 N 的数组 1: 数组长 N=Ni+1 1 2 3 4 5 间隔 P=2Pi 2 4 8 16 32 修正值 R=4Ri 4 16 64 256 1024 以及一个对应 2PN(这里 N=4、2PN=32) 的典型数和它的平方数组 2: 按 N=4 间隔 排列的数 d=di+2PN 32 64 96 128 160 192 2
3、24 256 该数的平方 D=d2 1024 4096 9216 16384 25600 36864 50176 65536 显然,N 值越大则数组 2 越小、程序代码效率越高、用时(插值次数) 越多. 以 2 字节整数开方为例的计算流程如下: 其中, 被开方数 D(范围 065536),其平方根 d(范围 0256) 注:1、查表可以从任何位置开始, 对计算速度影响不大. 其中 D=0、D=1 、D=Di、 D65280 判断可以省去. 2、此算法完全没有乘法试算,其 1/2、1/4 除法运算可由二进制移位简单实现,且为完全补偿后的精确插值,所以递归速度非常快(这里 4 次). 3、最后运算
4、已经包括了小数部分的精确 4 舍 5 入算法. 4、此算法略加改动,即可实现更长字节整数或定长浮点数平方根精确解 ,其逆运算也可以实现乘方运算. 一个 C 语言实例: / sqrt_2 中值定理法开平方程序( 直接查表-插值) / 输入 D (两字节无符号整数) / 输出 d (一字节无符号整数) char a,b,c,p; int A,B,C,D,R,K; void main() D=11111; / 被开方数 if(D50176)A=0; a=0; C=50176;c=224;break; / 查表 if(D36864)A=50176;a=224;C=36864;c=192;break;
5、if(D25600)A=36864;a=192;C=25600;c=160;break; if(D16384)A=25600;a=160;C=16384;c=128;break; if(D9216) A=16384; a=128;C= 9216; c= 96; break; if(D4096) A= 9216; a= 96; C= 4096; c= 64; break; if(D1024) 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;
6、B=C;B=1; / 插值计算循环 if(A!=0)K=A;K=1; else K=0x8000; / 65536=1 的数 B+=K;B-=R; if(DB)C=B;c=b; elseA=B;a=b; p=1;R=2; while(p!=1); / 循环 4 次结束 K=A-C;K=2;A-=K; C+=K; / 小数部分四舍五入 if(Delse if(Delse b=a; /开方结束 进一步研究表明,由于循环内所有运算都是加、减、位移、比较等简单运算,所花费的时间很少,可以适当加大循环次数. 特别地,如果把间隔 P 加大到 128,对应修正值 R=13684,则循环次数 N=7,对应数组
7、 2 就简化到: 按 N=7 间隔排列的数 d=di+Pn 0 256 512 该数的平方 Di=d*d 0 65536 262144 这时, 对于两字节数被开方数 D 来讲,查表环节也可省去, 程序代码大幅减少,计算流程如下: C 语言程序的一个例子: unsigned char a,b,p=0x80; unsigned int K,A,B,C,R=0x4000,D=60000; sqt1() do b=a-p;B=C;B=1; if(A)K=A;K=1; else K=0x8000; B+=K;B-=R; if(DB)C=B; elseA=B;a=b; p=1;R=2; while(p!=
8、1); /循环 7 次结束 p=(A-C)2;A-=p; C+=p; b=a; if(D A)b-; if(D C)b-; /输出方根 b 程序里只用了一个特别的数 128(及其它的平方数 16384),就能够把两字节数 065535 范围内的任意整数的整数平方根精确(小数部分严格 4 舍 5 入) 求解. 程序思想还可以继续延伸到更长字节无符号整数的开方,只需要修改对应的初始值 p、R 就行了. 结论 : 本文首先提出并证明了整数平方数中值定理,进而提出一种基于此定理的的快速开方算法,并给出了具体的计算流程和 C 语言程序实例.由于全部运算不使用乘法运算或幂运算,只使用加、减、移位、逻辑等简单运算,只引入极少的初始变量, 在经过有限次循环后即可迅速逼近任意有限大整数的整数平方根的精确解(小数部分严格 4 舍 5 入),从而把整数开平方运算的迄今最快速度提高了一个数量级. 此算法对于由没有集成硬件乘法器的芯片组成的微处理(控制 )系统、同时要担负大量开方运算而时间特别紧张的应用 如大型游戏程序、图形处理系统中两坐标点的距离计算(方根)、交流电压有效值等控制计算( 均方根) 具有一针见血的效果,对于任何高级程序语言、游戏机乃至计算器、民用或工业控制系统中的开平方函数代码的优化具有显著积极的意义.
