当前位置:首页 >> 建筑/土木 >>

开平方数的快速算法


整数平方数中值定理: 设 a、b、c 为顺序排列间距为 P 的 3 个整数,A、B、C 是它们的平方 则有:b^2=(a^2+c^2)/2-R,即:B=(A+C)/2-R 其中:修正值 R=P^2 特别地,如果间隔 P=1、2、 4、 8、 16、…2 n (或 Pn=2Pn-1)时 则: 修正值 R=1、4、16、64、256、…22n (或 Rn=4Rn-1)

r />证明: 已知:a=b+P c=b-P 有:a^2=(b+P)^2=b^2+2Pb+P^2 c2=(b-P)^2=b^2-2Pb+P^2 则:a^2+c^2=2b^2+2P^2 即:b^2=(a^2+c^2)/2-P^2 特别地 当:间隔 P=2 n=2*2 n -1=2 Pn-1 时(n 为自然数) 则:修正值 R=P^2=22n=(2 Pn-1)2=4(P n-1)2=4Rn-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 16384 25600 36864 50176 65536 … 显然,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 (一字节无符号整数)

char a,b,c,p; int A,B,C,D,R,K; void main() {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=C;B>>=1; // 插值计算循环 if(A!=0){K=A;K>>=1;} else K=0x8000; // 65536>>=1 的数 B+=K;B-=R; if(D>B){C=B;c=b;} else{A=B;a=b;} p>>=1;R>>=2; }while(p!=1); // 循环 4 次结束 K=A-C;K>>=2;A-=K; C+=K; // 小数部分四舍五入 if(D<C)b=c; else{ if(D<A)b=++c; else b=a;} } //开方结束

进一步研究表明,由于循环内所有运算都是加、减、位移、比较等简单运算,所花费的时间 很少,可以适当加大循环次数。

特别地,如果把间隔 P 加大到 128,对应修正值 R=13684,则循环次数 N=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(D>B)C=B; else{A=B;a=b;} p>>=1;R>>=2; }while(p!=1); //循环 7 次结束 p=(A-C)>>2;A-=p; C+=p; b=a; if(D<A)b--; if(D<C)b--; } //输出方根 b

程序里只用了一个特别的数 128(及其它的平方数 16384) ,就能够把两字节数 0~65535 范围 内的任意整数的整数平方根精确(小数部分严格 4 舍 5 入)求解。

程序思想还可以继续延伸到更长字节无符号整数的开方, 只需要修改对应的初始值 p、 就行 R 了。

结论 :

本文首先提出并证明了整数平方数中值定理,进而提出一种基于此定理的的快速开方算法, 并给出了具体的计算流程和 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 << MAX_BIT; for (i = MAX_BIT; i >= 0; i--) { r = root + m; if (r * r <= x) root = r; m >>= 1; } return root; }

unsigned long sqrt_5(unsigned long x) { register unsigned long xroot, m2, x2; xroot = 0; m2 = 1 << MAX_BIT * 2; do { x2 = xroot + m2; xroot >>= 1; if (x2 <= x) { x -= x2; xroot += m2; } } while (m2 >>= 2); if (xroot < x) return xroot + 1; return xroot; }


相关文章:
最快的开方算法
开平方算法 中值定理 开方 整数平方数中值定理: 设 a、b、c 为顺序排列间距为 P 的3个整数,A、B、C 是它们的平方 则有:b2=(a 2+c2)/2-R...
两位数平方的快速算法
开平方数的快速算法 4页 免费两​位​数​平​方​的​快​速​算​法 暂无评价|0人阅读|0次下载|举报文档 通​俗​易​懂​,​方...
快速平方算法
快速算法(适用于 100 以内的数,且个位是 1 或 9,求这个数的平方) 指定一个数为 x(x 为一个两位数,位数 1 或 9) 找到一个离 x 最近的整十数 y。 ...
快速平方根算法(1)
如果你在大学上数 学课没有打瞌睡的话,那么当你看到(1+M)^(-1/2)这样的...对整数开平方的算法如下。我并不打算在这讨论它(事实是我也没有仔细考究,因为...
任意两位数的平方速算法
http://hnjgdj.gov.cn 任意一个两位数平方的一种算法 为扩大学生的知识面,提高他们的计算速度,我们摸索出了一种求 任意一个两位数平方的一种算法 :将两位数...
开平方的计算
开平方的计算_数学_自然科学_专业资料。在中学阶段,...开平方 Extracting Square Root 写出被开方数,从小数...便于快速简洁的进行运算,并符合“算术公里的无矛盾性...
世界上最快的浮点开方算法
世界上最的浮点开方算法_计算机软件及应用_IT/计算机_专业资料。任何一个 3D...在牛顿近似值中的一般想法是我们我们猜测一个数 x 的平方根值 y, 我们可能...
两位数平方速算技巧
两位数平方速算技巧_数学_自然科学_专业资料。两位数平方速算技巧 本方法适合 11~99 所有平方的计算。 11X11=121 21X21=4141 31X31=961 41X41=1681 51X51=...
求数值近似开平方算法
求数值近似开平方算法 求数值近似开平方算法 近似 200721101008 陈林 摘要:本文...开平方数的快速算法 3页 免费 有限域中的开平方算法 5页 免费喜欢...
数字计算方法——手动开方
数字计算方法——手动开方_从业资格考试_资格考试/认证_教育专区。手动开平方 1.将被开方数的整数部分从个位起向左每隔两位划为一段,用撇号分开,分成 几段,...
更多相关标签:
开平方算法 | 开平方倒数算法 | 组合数快速算法 | 快速算数技巧心算法 | 数学快速口算法 | 三角函数 快速算法 | 数据结构快速排序算法 | 大数除法快速算法 |