1：二分查找

? ? ? ??思路：要實現一個sqrt函數，可以使用二分法，首先確定一個范圍[begin, end]，這個范圍的中間數mid，看mid的平方是否等于x，如果相等，則返回mid，如果不等則縮小[begin,end]的范圍，為原來的一半。這里的初始范圍可以是[1, x]，也可以是更精確一些的[1, (x/2) + 1]。（因 (x/2) + 1 的平方等于 x+1+(x^2/4)，它一定大于x，所以，x的平方根一定在[1, (x/2) + 1]范圍內）

?

? ? ? ??題目中給出的函數原型是int mySqrt(int x)。參數和返回值都是整數。這里稍微擴展一下，將函數原型改為double mySqrt(int x)。解題思路還是一樣的，但是浮點數因精度的原因，無法判斷兩個浮點數是否完全相等，只能說兩者的差值絕對值小于某個精度，所以在二分查找時，需要一定的技巧，具體的代碼如下：

?

double mySqrt_binarysearch(int x) {if(x <= 0) return 0;double begin = 1;double end = x/2+1;double mid, lastmid;mid = begin + (end-begin)/2;do{if(mid < x/mid) begin = mid;else end = mid;lastmid = mid;mid = begin + (end-begin)/2;}while(ABS(lastmid-mid) > FLT_MIN);return mid; }

?

?

? ? ? ??上面的代碼中，逐步縮小[begin,end]的范圍，通過判斷上次的lastmid與本次的mid的差值絕對值是否在精度之內，來決定是否繼續尋找下去。

?

2：牛頓迭代法

? ? ? ??上面的實現方法只能說是中規中矩，但是實現sqrt有更牛逼的方法，就是牛頓迭代法。該方法就是由我們熟知的牛頓提出的。具體思想可以自行搜索。簡而言之，如下圖：

?

?

? ? ? ??x^2 = a的解，也就是函數f(x) = x^2 – a與x軸的交點。可以在x軸上先任選一點x0，則點（x0, f(x0)）在f(x)上的切線，與x軸的交點為x1，它們滿足切線的方程：f(x0)=(x0-x1)f’(x0)，可得x1更接近最終的結果，解方程得到：

x1 = (x0 + (a/x0))/2。以x1為新的x0，按照切線的方法依次迭代下去，最終求得符合精確度要求的結果值。它的實現代碼如下：

?

double mySqrt_newton(int x) {if(x <= 0) return 0;double res, lastres;res = x; //初始值，可以為任意非0的值do{lastres = res;res = (res + x/res)/2;}while(ABS(lastres-res) > FLT_MIN);return res; }

?

?

?????? 使用牛頓法解決sqrt的效率非常高，關于效率比較可參見本文最后一節。牛頓法的效率很大程度上取決于初始值的選取，這就引出了下一節。

?

3：神跡

?????? 下面這段代碼出自《雷神之錘》，至今尚未找到該代碼的真正作者，代碼如下：

?

float InvSqrt(float x) {float xhalf = 0.5f * x;int i = *(int*)&x; i = 0x5f375a86 - (i>>1); x = *(float*)&i;x = x*(1.5f-xhalf*x*x); x = x*(1.5f-xhalf*x*x); x = x*(1.5f-xhalf*x*x);return 1/x; }

?

?

?????? 它本質上還是使用的牛頓迭代法，真正牛逼的地方在于它初始值的選擇，0x5f375a86這個魔法數字的由來尚不可知，該算法的具體原理及其背景可以參見維基百科，不再贅述。

?????? 要注意的是，上面算法使用的是float和int類型，實驗可知他們不能替換為double和long。

?

4：效率

?????? 使用下面的代碼，測試上述三種方法，以及系統默認方法的效率：

?

int main(int argc, char **argv) {clock_t begin, end;int num = atoi(argv[1]);double res;int i;int loopcnts = 1000000;begin = clock();for(i = 0; i < loopcnts; i++)res = mySqrt_binarysearch(num);end = clock();printf("mySqrt_binarysearch(%d) = %f, spent time is %f\n", num, res, (double)(end-begin));begin = clock();for(i = 0; i < loopcnts; i++)res = mySqrt_newton(num);end = clock();printf("mySqrt_newton(%d) = %f, spent time is %f\n", num, res, (double)(end-begin));begin = clock();for(i = 0; i < loopcnts; i++)res = InvSqrt(num);end = clock();printf("InvSqrt(%d) = %f, spent time is %f\n", num, res, (double)(end-begin));begin = clock();for(i = 0; i < loopcnts; i++)res = sqrt(num);end = clock();printf("system sqrt(%d) = %f, spent time is %f\n", num, res, (double)(end-begin));}

?

?

?????? 測試結果如下：

?

mySqrt_binarysearch(65535) = 255.998047, spent time is 3437535.000000 mySqrt_newton(65535) = 255.998047, spent time is 659694.000000 InvSqrt(65535) = 255.998047, spent time is 65902.000000 system sqrt(65535) = 255.998047, spent time is 82605.000000

?

?

?????? 可見，二分法最慢，普通的牛頓迭代法次之，神跡代碼要比系統庫的還要快一些。

?

? ? ? ??Ps：謹以此文，給予那些不知天高地厚的程序員們，當頭棒喝！

?

參考：

https://zh.wikipedia.org/wiki/%E7%89%9B%E9%A1%BF%E6%B3%95

https://zh.wikipedia.org/wiki/%E5%B9%B3%E6%96%B9%E6%A0%B9%E5%80%92%E6%95%B0%E9%80%9F%E7%AE%97%E6%B3%95

http://kb.cnblogs.com/page/189867/

總結

以上是生活随笔為你收集整理的三种sqrt函数实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。