求一個數(shù)的平方根函數(shù)sqrt(int num) ,在大多數(shù)語言中都提供實現(xiàn)。那么要求一個數(shù)的平方根，是怎么實現(xiàn)的呢？
實際上求平方根的算法方法主要有兩種：二分法(binary search)和牛頓迭代法(Newton iteration)

1：二分法

求根號5

a:折半： 5/2=2.5
b:平方校驗: 2.5*2.5=6.25>5，并且得到當前上限2.5
c:再次向下折半:2.5/2=1.25
d:平方校驗：1.25*1.25=1.5625<5,得到當前下限1.25
e:再次折半:2.5-(2.5-1.25)/2=1.875
f:平方校驗：1.875*1.875=3.515625<5,得到當前下限1.875

每次得到當前值和5進行比較，并且記下下下限和上限，依次迭代，逐漸逼近平方根：

import math 
from math import sqrt 
 
def sqrt_binary(num): 
  x=sqrt(num) 
  y=num/2.0 
  low=0.0 
  up=num*1.0 
  count=1 
  while abs(y-x)>0.00000001: 
    print count,y 
    count+=1     
    if (y*y>num): 
      up=y 
      y=low+(y-low)/2 
    else: 
      low=y 
      y=up-(up-y)/2 
  return y 
 
print(sqrt_binary(5)) 
print(sqrt(5)) 

運行結果：
1 2.5
2 1.25
3 1.875
4 2.1875
5 2.34375
6 2.265625
7 2.2265625
8 2.24609375
9 2.236328125
10 2.2314453125
11 2.23388671875
12 2.23510742188
13 2.23571777344
14 2.23602294922
15 2.23617553711
16 2.23609924316
17 2.23606109619
18 2.23608016968
19 2.23607063293
20 2.23606586456
21 2.23606824875
22 2.23606705666
23 2.2360676527
24 2.23606795073
25 2.23606809974
26 2.23606802523
27 2.23606798798
2.23606796935
2.2360679775
[Finished in 0.1s]

經過27次二分法迭代，得到的值和系統(tǒng)sqrt()差別在0.00000001，精度在億分之一，

0.001需要迭代8次

因此，在對精度要求不高的情況下，二分法也算比較高效的算法。

2：牛頓迭代

仔細思考一下就能發(fā)現(xiàn)，我們需要解決的問題可以簡單化理解。

從函數(shù)意義上理解：我們是要求函數(shù)f(x)=x²，使f(x)=num的近似解，即x²-num=0的近似解。

從幾何意義上理解：我們是要求拋物線g(x)=x²-num與x軸交點（g(x)=0）最接近的點。

我們假設g(x0)=0，即x0是正解，那么我們要做的就是讓近似解x不斷逼近x0，這是函數(shù)導數(shù)的定義：

可以由此得到

從幾何圖形上看，因為導數(shù)是切線，通過不斷迭代，導數(shù)與x軸的交點會不斷逼近x0。

對于一般情況：

將m=2代入：

def sqrt_newton(num): 
  x=sqrt(num) 
  y=num/2.0 
  count=1 
  while abs(y-x)>0.00000001: 
    print count,y 
    count+=1 
    y=((y*1.0)+(1.0*num)/y)/2.0000 
  return y 
 
print(sqrt_newton(5)) 
print(sqrt(5)) 

運行結果：
1 2.5
2 2.25
3 2.23611111111
2.23606797792
2.2360679775

精確到億分之一，牛頓法只迭代了3次，是二分法的十倍

3：利用牛頓法求開立方

def cube_newton(num): 
  x=num/3.0 
  y=0 
  count=1 
  while abs(x-y)>0.00000001: 
    print count,x 
    count+=1 
    y=x 
    x=(2.0/3.0)*x+(num*1.0)/(x*x*3.0) 
  return x 
 
print(cube_newton(27))  

微積分、概率、線代是高級算法的基礎課。可是，這么多年，已經忘得差不多了..............................

總結

以上就是本文關于Python編程實現(xiàn)二分法和牛頓迭代法求平方根代碼的全部內容，希望對大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站其他相關專題，如有不足之處，歡迎留言指出。

最新評論