作者：nash_
链接：/zmazon/article/details/8217866
sqrt()函数，是绝大部分语言支持的常用函数，它实现的是开方运算；开方运算最早是在我国魏晋时数学家刘徽所著的《九章算术》被提及。今天写了几个函数加上国外大神的几个神级程序带大家领略sqrt的神奇之处。
1、古人算法（暴力法）
原理：从0开始0.00001,000002...一个一个试，直到找到x的平方根，代码如下：
staticdoublebaoliSqrt(doublex){ finaldouble_JINGDU=1e-6; doublei; for(i=0;Math.abs(x-i*i)>_JINGDU;i+=_JINGDU) ; returni; } publicstaticvoidmain(String[]args){ doublex=3; doubleroot=baoliSqrt(x); System.out.println(root); }publicclassAPIsqrt{
测试结果：
1、7320509999476947
2、牛顿迭代法
计算机科班出身的童鞋可能首先会想到的是《数值分析》中的牛顿迭代法求平方根。原理是：随意选一个数比如说8，要求根号3，我们可以这么算：
(8 + 3/8) = 4.1875
(4.1875 + 3/4.1875) = 2.4519
(2.4519 + 3/2.4519) = 1.837
(1.837 + 3/1.837) = 1.735
做了4步基本算出了近似值了，这种迭代的方式就是传说中的牛顿迭代法了，代码如下：
staticdoublenewtonSqrt(doublex){ if(x<0){ System.out.println("负数没事开什么方"); return-1; } if(x==0) return0; double_avg=x; doublelast_avg=Double.MAX_VALUE; finaldouble_JINGDU=1e-6; while(Math.abs(_avg-last_avg)>_JINGDU){ last_avg=_avg; _avg=(_avg+x/_avg)/2; } return_avg; } publicstaticvoidmain(String[]args){ doublex=3; doubleroot=newtonSqrt(x); System.out.println(root); } }publicclassAPIsqrt{
测试结果：
17320508075688772
3、暴力-牛顿综合法
原理：还是以根号3为例，先用暴力法讲根号3逼近到1.7，然后再利用上述的牛顿迭代法。虽然没有用牛顿迭代好，但是也为我们提供一种思路。代码如下：
staticdoublebaoliAndNewTonSqrt(doublex){ if(x<0){ System.out.println("负数没事开什么方"); return-1; } if(x==0) return0; doublei=0; double_avg; doublelast_avg=Double.MAX_VALUE; for(i=0;i*i<x;i+=0.1); _avg=i; finaldouble_JINGDU=1e-6; while(Math.abs(_avg-last_avg)>_JINGDU){ last_avg=_avg; _avg=(_avg+x/_avg)/2; } return_avg; } publicstaticvoidmain(String[]args){ doublex=3; doubleroot=baoliAndNewTonSqrt(x); System.out.println(root); } }publicclassAPIsqrt{
测试结果：
1、7320508075689423
4、二分开方法
原理：还是以3举例：
(0+3)/2 = 1.5, 1.5^2 = 2.25, 2.25 < 3;
(1.5+3)/2 = 2.25, 2.25^2 = 5.0625, 5.0625 > 3;
(1.5+2.25)/2 = 1.875, 1.875^2 = 3.515625; 3.515625>3;
直到前后两次平均值只差小于自定义精度为止，代码如下：
staticdoubleerfenSqrt(doublex){ if(x<0){ System.out.println("负数没事开什么方"); return-1; } if(x==0) return0; finaldouble_JINGDU=1e-6; double_low=0; double_high=x; double_mid=Double.MAX_VALUE; doublelast_mid=Double.MIN_VALUE; while(Math.abs(_mid-last_mid)>_JINGDU){ last_mid=_mid; _mid=(_low+_high)/2; if(_mid*_mid>x) _high=_mid; if(_mid*_mid<x) _low=_mid; } return_mid; } publicstaticvoidmain(String[]args){ doublex=3; doubleroot=erfenSqrt(x); System.out.println(root); } }publicclassAPIsqrt{
测试结果：
1、732051134109497
5、计算 (int)(sqrt(x))算法
PS:此算法非博主所写
原理：空间换时间，细节请大家自行探究，代码如下：
finalstaticint[]table={0,16,22,27,32,35,39,42,45,48,50,53, 55,57,59,61,64,65,67,69,71,73,75,76,78,80,81,83,84, 86,87,89,90,91,93,94,96,97,98,99,101,102,103,104, 106,107,108,109,110,112,113,114,115,116,117,118,119, 120,121,122,123,124,125,126,128,128,129,130,131,132, 133,134,135,136,137,138,139,140,141,142,143,144,144, 145,146,147,148,149,150,150,151,152,153,154,155,155, 156,157,158,159,160,160,161,162,163,163,164,165,166, 167,167,168,169,170,170,171,172,173,173,174,175,176, 176,177,178,178,179,180,181,181,182,183,183,184,185, 185,186,187,187,188,189,189,190,191,192,192,193,193, 194,195,195,196,197,197,198,199,199,200,201,201,202, 203,203,204,204,205,206,206,207,208,208,209,209,210, 211,211,212,212,213,214,214,215,215,216,217,217,218, 218,219,219,220,221,221,222,222,223,224,224,225,225, 226,226,227,227,228,229,229,230,230,231,231,232,232, 233,234,234,235,235,236,236,237,237,238,238,239,240, 240,241,241,242,242,243,243,244,244,245,245,246,246, 247,247,248,248,249,249,250,250,251,251,252,252,253, 253,254,254,255}; /** *Afasterreplacementfor(int)(java.lang.Math.sqrt(x)).Completely *accurateforx<2147483648(i.e.2^31)... */ staticintsqrt(intx){ intxn; if(x>=0x10000){ if(x>=0x1000000){ if(x>=0x10000000){ if(x>=0x40000000){ xn=table[x>>24]<<8; }else{ xn=table[x>>22]<<7; } }else{ if(x>=0x4000000){ xn=table[x>>20]<<6; }else{ xn=table[x>>18]<<5; } } xn=(xn+1+(x/xn))>>1; xn=(xn+1+(x/xn))>>1; return((xn*xn)>x)?--xn:xn; }else{ if(x>=0x100000){ if(x>=0x400000){ xn=table[x>>16]<<4; }else{ xn=table[x>>14]<<3; } }else{ if(x>=0x40000){ xn=table[x>>12]<<2; }else{ xn=table[x>>10]<<1; } } xn=(xn+1+(x/xn))>>1; return((xn*xn)>x)?--xn:xn; } }else{ if(x>=0x100){ if(x>=0x1000){ if(x>=0x4000){ xn=(table[x>>8])+1; }else{ xn=(table[x>>6]>>1)+1; } }else{ if(x>=0x400){ xn=(table[x>>4]>>2)+1; }else{ xn=(table[x>>2]>>3)+1; } } return((xn*xn)>x)?--xn:xn; }else{ if(x>=0){ returntable[x]>>4; } } } return-1; } publicstaticvoidmain(String[]args){ System.out.println(sqrt(65)); } }publicclassAPIsqrt2{
测试结果：8
6、最快的sqrt算法
PS:此算法非博主所写
这个算法很有名，大家可能也见过，作者是开发游戏的，图形算法中经常用到sqrt，作者才写了一个神级算法，和他那神秘的0x5f3759df，代码如下
floatInvSqrt(floatx) { floatxhalf=0.5f*x; inti=*(int*)&x;//getbitsforfloatingVALUE i=0x5f375a86-(i>>1);//givesinitialguessy0 x=*(float*)&i;//convertbitsBACKtofloat x=x*(1.5f-xhalf*x*x);//Newtonstep,repeatingincreasesaccuracy returnx; } intmain() { printf("%lf",1/InvSqrt(3)); return0; }#include<math.h>
测试结果：
感兴趣的朋友可以参考/view/a0174fa20029bd64783e2cc0.html 是作者解释这个算法的14页论文《Fast Inverse Square Root》
7、一个与算法6相似的算法
PS:此算法非博主所写
代码如下：
floatSquareRootFloat(floatnumber){ longi; floatx,y; constfloatf=1.5F; x=number*0.5F; y=number; i=*(long*)&y; i=0x5f3759df-(i>>1); y=*(float*)&i; y=y*(f-(x*y*y)); y=y*(f-(x*y*y)); returnnumber*y; } intmain() { printf("%f",SquareRootFloat(3)); return0; }#include<math.h>
测试结果：
-END -
如果看到这里，说明你喜欢这篇文章，请转发、点赞。扫描下方二维码或者微信搜索「perfect_iscas」，添加好友后即可获得10套程序员全栈课程+1000套PPT和简历模板，向我私聊「进群」二字即可进入高质量交流群。
↓扫描二维码进群↓
喜欢文章，点个在看
