如标题所示不用平方根库函数,求解一个数字的平方根
思路1:采用二分的方式(无处不在的二分),上界初始化为数字本身下界初始化为1,这样用二分判断中间數字的平方和目标数字比较,再修改上界和下界直到小于一定的阈值。
思路2:采用牛顿法(数值分析中提到)采用微分的方式,从初始点开始每次迭代,微分求解切线然后求解切线和x轴的交点,再以这个交点作为起点迭代进行。比如求解24那么写出函数:
我们目標就是求解这个函数的根,函数一阶导数是:
起始点可以选择x0 = 24通过求解,可以得到下一个迭代点的公式为:
这样迭代下去直到最后小於一定的阈值。
通过运行发现牛顿法的求解速度要比二分法快很多,例如求解30000牛顿法只要11次迭代,可以达到0.001精度但是二分法需要33次,所以数值分析普遍采用牛顿法进行求根