求一个数的平方根函数sqrt(int num) ,在大多数语言中都提供实现。那么要求一个数的平方根，是怎么实现的呢？
实际上求平方根的算法方法主要有两种：二分法(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 mathfrom math import sqrtdef sqrt_binary(num):x=sqrt(num)y=num/2.0low=0.0up=num*1.0count=1while abs(y-x)>0.00000001:print count,ycount+=1if (y*y>num):up=yy=low+(y-low)/2else:low=yy=up-(up-y)/2return yprint(sqrt_binary(5))print(sqrt(5))
运行结果：
1 2.52 1.253 1.8754 2.18755 2.343756 2.2656257 2.22656258 2.246093759 2.23632812510 2.231445312511 2.2338867187512 2.2351074218813 2.2357177734414 2.2360229492215 2.2361755371116 2.2360992431617 2.2360610961918 2.2360801696819 2.2360706329320 2.2360658645621 2.2360682487522 2.2360670566623 2.236067652724 2.2360679507325 2.2360680997426 2.2360680252327 2.236067987982.236067969352.2360679775[Finished in 0.1s]
经过27次二分法迭代，得到的值和系统sqrt()差别在0.00000001，，精度在亿分之一，
0.001需要迭代8次
因此，在对精度要求不高的情况下，二分法也算比较高效的算法。
2：牛顿迭代
仔细思考一下就能发现，我们需要解决的问题可以简单化理解。
从函数意义上理解：我们是要求函数f(x) = x，使f(x) = num的近似解，即x – num = 0的近似解。
从几何意义上理解：我们是要求抛物线g(x) = x – num与x轴交点（g(x) = 0）最接近的点。
我们假设g(x0)=0，即x0是正解，那么我们要做的就是让近似解x不断逼近x0，这是函数导数的定义：
可以由此得到
从几何图形上看，因为导数是切线，通过不断迭代，导数与x轴的交点会不断逼近x0。
对于一般情况：
将m=2代入：
def sqrt_newton(num):x=sqrt(num)y=num/2.0count=1while abs(y-x)>0.00000001:print count,ycount+=1y=((y*1.0)+(1.0*num)/y)/2.0000return yprint(sqrt_newton(5))print(sqrt(5))运行结果：
1 2.52 2.253 2.236111111112.236067977922.2360679775
精确到亿分之一，牛顿法只迭代了3次，是二分法的十倍
3：利用牛顿法求开立方
def cube_newton(num):x=num/3.0y=0count=1while abs(x-y)>0.00000001:print count,xcount+=1y=xx=(2.0/3.0)*x+(num*1.0)/(x*x*3.0)return xprint(cube_newton(27))
微积分、概率、线代是高级算法的基础课。可是，这么多年，已经忘得差不多了…………………………
版权声明：本文为博主原创文章，未经博主允许不得转载。
空虚无聊的时候就读书，但一定得有自己的生活目标和计划。
