作者：nash_

sqrt()函數，是絕大部分語言支持的常用函數，它實現的是開方運算；開方運算最早是在我國魏晉時數學家劉徽所著的《九章算術》被提及。今天寫了幾個函數加上國外大神的幾個神級程序帶大家領略sqrt的神奇之處。

1、古人算法（暴力法）

原理：從0開始0.00001,000002...一個一個試，直到找到x的平方根，代碼如下：

publicclassAPIsqrt{

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);
}

測試結果：

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步基本算出了近似值了，這種迭代的方式就是傳說中的牛頓迭代法了，代碼如下：

publicclassAPIsqrt{

staticdoublenewtonSqrt(doublex){

if(x0){
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);
}
}

測試結果：

17320508075688772

3、暴力-牛頓綜合法

原理：還是以根號3為例，先用暴力法講根號3逼近到1.7，然后再利用上述的牛頓迭代法。雖然沒有用牛頓迭代好，但是也為我們提供一種思路。代碼如下：

publicclassAPIsqrt{

staticdoublebaoliAndNewTonSqrt(doublex){

if(x0){
System.out.println("負數沒事開什么方");
return-1;
}
if(x==0)
return0;

doublei=0;
double_avg;
doublelast_avg=Double.MAX_VALUE;
for(i=0;i*i0.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);
}
}

測試結果：

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;

直到前后兩次平均值只差小于自定義精度為止，代碼如下：

publicclassAPIsqrt{

staticdoubleerfenSqrt(doublex){

if(x0){
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*_midreturn_mid;

}

publicstaticvoidmain(String[]args){
doublex=3;
doubleroot=erfenSqrt(x);
System.out.println(root);
}
}

測試結果：

1、732051134109497

5、計算 (int)(sqrt(x))算法

PS:此算法非博主所寫

原理：空間換時間，細節請大家自行探究，代碼如下：

publicclassAPIsqrt2{
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
*accurateforx2147483648(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));

}
}

測試結果：8

6、最快的sqrt算法

PS:此算法非博主所寫

這個算法很有名，大家可能也見過，作者是開發游戲的，圖形算法中經常用到sqrt，作者才寫了一個神級算法，和他那神秘的0x5f3759df，代碼如下

#include
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;
}

測試結果：

感興趣的朋友可以參考http://wenku.baidu.com/view/a0174fa20029bd64783e2cc0.html 是作者解釋這個算法的14頁論文《Fast Inverse Square Root》

7、一個與算法6相似的算法

PS:此算法非博主所寫

代碼如下：

#include
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;
}

測試結果：