Question

sqrt函数的原理和实现

Answer 1

最近放寒假了，在恶补数据结构和算法的知识，年少没听进数据结构老师的劝，到最后还是要兜兜转转回到算法。

求平方根自己在学数学的时候好像没有学过，我们学校的高数要求比较低，有一些比较重要的部分还是略过了没有学。如果按照我目前的数学基础来说的话，我能想到的就是 穷举x，让这个x²无限接近已知条件c 。凭借多年在试卷上的摸爬滚打，我知道这个肯定不行，所以直奔度娘（这是不好的习惯要自己注意），学到了旧知识新用： 牛顿迭代法 。

在我的理解下是，在给定函数曲线f(x)上，已知函数值y，做逼近该函数值y的切线f'(x)。f'(x) = y解出来的x值即为近似解

得出的公式是：Xn+1 = Xn - F(Xn)/F'(Xn)
具体证明可以看看度娘。

所以运用在平方根的求解上的话，F(x) = x² - c，F'(x) = 2x
x = x - [(x² - c) / 2x]

知道这个原理实现起来应该比较简单：

革命尚未成功，同志仍需努力！