开平方数的快速算法.pdf
《开平方数的快速算法.pdf》由会员分享,可在线阅读,更多相关《开平方数的快速算法.pdf(4页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、开平方数的快速算法.txt 我爸说过的最让我感动的一句话: “孩子,好好学习吧,爸以前玩麻将都玩儿 10 块的,现在为了供你念书,改玩儿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)2
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 224 256 该数的平方 D=d2 1024 4096 9216
3、 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 舍 5 入算法。4、此算法略加改动,即可实现更长字节整数或
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; if(D25600)A=36864;a=192;C=25600;c=160;break; if(D16384)A=25600;a=160;C
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 开平 快速 算法
限制150内