69. Sqrt(x)

给你一个非负整数 x ，计算并返回 x 的算术平方根。

由于返回类型是整数，结果只保留整数部分，小数部分将被舍去。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1：

输入：x = 4
输出：2
示例 2：

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842…, 由于返回类型是整数，小数部分将被舍去。

提示：

0 <= x <= 231 - 1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sqrtx
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

这题的解法用暴力解法是非常简单的。主要的麻烦在于如何解的更好，答案就是用牛顿迭代法。

下面这种方法可以很有效地求出根号 aa 的近似值：首先随便猜一个近似值 xx，然后不断令 xx 等于 xx 和 a/xa/x 的平均数，迭代个六七次后 xx 的值就已经相当精确了。

例如，我想求根号 22 等于多少。假如我猜测的结果为 44，虽然错的离谱，但你可以看到使用牛顿迭代法后这个值很快就趋近于根号 22 了：

( 4 + 2/ 4 ) / 2 = 2.25

( 2.25 + 2/ 2.25 ) / 2 = 1.56944..

( 1.56944..+ 2/1.56944..) / 2 = 1.42189..

( 1.42189..+ 2/1.42189..) / 2 = 1.41423..

….

这种算法的原理很简单，我们仅仅是不断用 (x, f(x))(x,f(x)) 的切线来逼近方程 x^2-a=0x
2
−a=0 的根。根号 aa 实际上就是 x^2-a=0x
2
−a=0 的一个正实根，这个函数的导数是 2x2x。也就是说，函数上任一点 (x,f(x))(x,f(x)) 处的切线斜率是 2x2x。那么，x-f(x)/(2x)x−f(x)/(2x) 就是一个比 xx 更接近的近似值。代入 f(x)=x^2-af(x)=x
2
−a 得到 x-(x^2-a)/(2x)x−(x
2
−a)/(2x)，也就是 (x+a/x)/2(x+a/x)/2。

同样的方法可以用在其它的近似值计算中。Quake III 的源码中有一段非常牛 B 的开方取倒函数。

知道方程实现就非常简单了。

作者：LOAFER
链接：https://leetcode-cn.com/problems/sqrtx/solution/niu-dun-die-dai-fa-by-loafer/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

代码

function mySqrt(x: number): number {
  let n = x;
  while (n * n > x) {
    n = Math.floor((n + x / n) / 2);
  }
  return n;
}

__END__