69. x 的平方根

题目#

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

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

示例 1:

输入: 4
输出: 2

示例 2:

输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,
    由于返回类型是整数，小数部分将被舍去。

思路#

牛顿迭代法。

公式为 $x_{i+1}=\frac{x_i+\frac{n}{x_i}}{2}$ 。

终止条件为 $\mid x_{i} - x_{i-1} \mid \leq \epsilon$ ， $\epsilon$ 为所需精度。

代码#

func mySqrt(x int) int {
    if x <= 1 {
        return x
    }

    a := 1.0
    for {
        pre := a                   // x_{i-1}
        a = (a + float64(x)/a) / 2 // 迭代

        if math.Abs(a-pre) <= 0.1 {
            break
        }
    }

    return int(a)
}