sqrt函数实现——二分法、牛顿迭代法

在leetcode练习时，碰到一道经典的面试题，如何实现sqrt()开平方函数。当然，很简单的是调用系统函数，但是难道不能自己实现这个函数的功能吗？于是一番思索和查阅资料，看到下面的方法。

二分法求解

二分法这个应该很熟悉，在二分查找算法中就有具体的体现。应用在此题上，也是合适不过的。
首先分析一下这道题：
实现sqrt函数功能，求一个数的开平方，即求$f(x) = x^2 - N$f(x)=x2−N这个函数$f(x) = 0$f(x)=0的非负解。

• 原理
  二分法的原理很简单，就是通过缩减区间来确定解的位置。通过图来说明：
  
• 实现步骤
  • 选择区间[a, b]，f(a)与f(b)异号。
  • 获得区间中值mid，以及f(mid)值。
  • 若f(a) * f(mid) < 0，即f(a)与f(mid)异号，取新区间[a, mid]。相反，取区间[mid, b]。
  • 重复上两步操作，直到达到类型精度停止。
• 代码实现

int BisectionSqrt(int x)
{
	double low = 0, high = x + 0.25, mid = (low + high) / 2;
	while (mid - low > DBL_EPSILON && high - mid > DBL_EPSILON)  // 精度
	{
		if ((mid * mid - x) * (low * low - x) < 0)
			high = mid;
		else low = mid;
		mid = (high + low) / 2;
	}
	return int(mid);
}

注：

初始上界为x + 0.25，而非x。（这一点我不是很懂，希望大佬指点）

牛顿迭代法

看概念：
又称为牛顿-拉弗森方法（英语：Newton-Raphson method），它是一种在实数域和复数域上近似求解方程的方法。方法使用函数$f(x)$f(x)的泰勒级数的前面几项来寻找方程 $f(y) = 0$f(y)=0的根。
可以看出满足上面的题目分析，可以求得根。

• 原理步骤
  选择一个接近函数$f(x)$f(x)零点的 $x_0$x0​，计算相应的$f(x_0)$f(x0​)和切线斜率 $f&#x27;(x_0)$f′(x0​)（这里$f&#x27;$f′表示函数 $f$f的导数）。然后我们计算穿过点 $f(x_0)$f(x0​)并且斜率为$f&#x27;(x_0)$f′(x0​)的直线和$x$x轴的交点的x坐标，也就是求如下方程的解：
  $0 = (x - x_0) * f&#x27;(x_0) + f(x_0)$0=(x−x0​)∗f′(x0​)+f(x0​)
  我们将新求得的点的$x$x坐标命名为 $x_1$x1​，通常$x_1$x1​会比 $x_0$x0​更接近方程 $f(x)=0$f(x)=0的解。因此我们现在可以利用$x_1$x1​开始下一轮迭代。迭代公式可化简为如下所示：
  $x_{n+1} = x_n - \frac{f(x_n)}{f&#x27;(x_n)}$xn+1​=xn​−f′(xn​)f(xn​)​
• 图示
  
  将上述的迭代式进行化简：
  因为要求的是开平方的解，所以$f&#x27;(x_n)$f′(xn​)为$2x_n$2xn​，同时将$f(x_n) =x_n^2 - N$f(xn​)=xn2​−N带入公式$x_{n+1} = x_n - \frac{f(x_n)}{f&#x27;(x_n)}$xn+1​=xn​−f′(xn​)f(xn​)​中，可以化简得到：$x_{n+1} = (x_n + N/x_n) / 2$xn+1​=(xn​+N/xn​)/2
• 代码实现

int NewtonSqrt(int x) {
	if (x == 0) return 0;
	double result = 1, pre = 0;
	while (result != pre)
	{
		pre = result;
		result = (result + x / result) / 2;
	}
	return int(result);
}

通过查阅的资料，以及在leetcode上的实际提交，发现牛顿迭代法的效率要比二分法高。
具体的效率差异请参考：https://blog.csdn.net/xusiwei1236/article/details/25657611