开平方数的快速算法

1、整数平方数中值定理：设a、b、c为顺序排列间距为P的3个整数，A、B、C是它们的平方则有：b2（a2c2）2R，即：B（AC）2R其中：修正值RP2特别地，如果间隔P1、2、 4、 8、 16、2 n (或Pn=2Pn-1）时则： 修正值R1、4、16、64、256、22n (或Rn4Rn-1）证明：已知：abPcbP有：a2(bP)2b22PbP2c2（bP）2b22PbP2则：a2c22b22P2即：b2（a2c2）2P2特别地当：间隔 P2 n2*2 n -12 Pn-1时（n为自然数）则：修正值 RP222n（2 Pn-1）24（P n-1）24Rn-1（证明完）根据以上定理，可以实现

2、整数快速开平方根计算：先构建一个长度为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 224 256 该数的平方 D=d2 1024 4096 9216 16384 25600 36864 50176 65536 显然，N值越大则数组2越小、程序代码效率越高、用时（插值次数）越多。以2字节整数开方为例的计算流程如下：其中，被开方数D（范围06

3、5536），其平方根d（范围0256）注：1、查表可以从任何位置开始，对计算速度影响不大。其中D=0、D=1、D=Di、 D65280判断可以省去。2、此算法完全没有乘法试算，其1/2、1/4除法运算可由二进制移位简单实现，且为完全补偿后的精确插值，所以递归速度非常快（这里4次）。3、最后运算已经包括了小数部分的精确4舍5入算法。4、此算法略加改动，即可实现更长字节整数或定长浮点数平方根精确解.一个C语言实例：/ sqrt_2 中值定理法开平方程序(直接查表-插值)/ 输入D (两字节无符号整数)/ 输出d (一字节无符号整数)char a,b,c,p;int A,B,C,D,R,K; voi

4、d 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; 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; brea

5、k; 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;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(DC)b=c; else if(D

6、=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!=1); /循环7次结束 p=(A-C)2;A-=p; C+=p; b=a; if(DA)b-; if(DC)b-; /输出方根b程序里只用了一个特别的数128（及其它的平方数16384），就能够把两字节数065535范围内的任意整数的整数平方根精确（小数部分严格4舍5入）求解。程序思想还可以继续延伸到更长字节无符号整数的开方，只需要修改对应的初始值p、R就行了。 结论 ：本文首先提出并证明了整数平方数中值定理，进而提出一种基于

7、此定理的的快速开方算法，并给出了具体的计算流程和C语言程序实例。由于全部运算不使用乘法运算或幂运算，只使用加、减、移位、逻辑等简单运算，只引入极少的初始变量，在经过有限次循环后即可迅速逼近任意有限大整数的整数平方根的精确解（小数部分严格4舍5入。 以下是大明轮王点评:说自己最快是要证明的:) 否定他只要举出一个更快的，更简单的。中国古代就有地道的开方术，原理是一位一位的尝试，写出来就是程序sqrt_1，很容易理解，但是用了乘法。通过二项式定理进行一系列优化，可以得到程序sqrt_5,只用了加减和移位，对结果四舍五入，供你参考比较! (程序是我摘录的，非原创) 如果需要软件实现的浮点库, 开源的Softfloat很好。 #define N_BITS 32#define MAX_BIT (N_BITS + 1) / 2 - 1) unsigned long sqrt_1(unsigned long x)register int i; register unsigned long m, r, root; root = 0; m = 1 = 0; i-) r = root + m; if (r * r = 1; return root; unsigned long sqrt_5(unsigned lon