69. Sqrt(x)

二分法的扩展，条件是一个数的平方大于x。可以用乘法或者除法进行比较，除法的时候要注意l=1，不然的话m有可能等于零出错。加上二分法最基本的两种写法，那么可以有四种写法。返回lower bound。

public int mySqrt(int x) {
    if (x < 2) return x;

    int l = 0, r = x / 2 + 1;

    while (l < r) {
        int m = (l + r) >>> 1;
        if (Math.pow(m, 2) == x) return m;
        if (Math.pow(m, 2) < x) {
            l = m + 1;
        } else {
            r = m;
        }
    }
    return l - 1;
}

public int mySqrt1(int x) {
    if (x < 2) return x;
    int l = 1, r = x / 2 + 1;

    while (l < r) {
        int m = (l + r) >>> 1;
        if (x / m == m) return m;
        if (x / m > m) {
            l = m + 1;
        } else {
            r = m;
        }
    }
    return l - 1;
}

public int mySqrt3(int x) {
    if (x < 2) return x;
    int l = 0, r = x / 2;

    while (l <= r) {
        int m = (l + r) >>> 1;
        if (Math.pow(m, 2) == x) return m;
        if (Math.pow(m, 2) < x) {
            l = m + 1;
        } else {
            r = m - 1;
        }
    }
    return l - 1;
}

public int mySqrt4(int x) {
    if (x < 2) return x;
    int l = 1, r = x / 2;

    while (l <= r) {
        int m = (l + r) >>> 1;
        if (x / m == m) return m;
        if (x / m > m) {
            l = m + 1;
        } else {
            r = m - 1;
        }
    }
    return l - 1;
}

牛顿开方法(Newton's method)：原理是取一条曲线f(x)点x0处的切线，得到和x轴相交后新点x1，再取f(x)点x1处的切线....以此类推，得到递推公式

取二阶可导曲线f(x) = x^2 - num, x = xn带入以上公式, 得到迭代公式x(n+1)=(1/2)*(xn+ num/xn)

# iteration
def sqrt(num):
    x = 1.0  # 取初始值x0 = 1.0
    while abs(x * x - num) > 1e-9: # 设定精度范围
        x = 0.5 * (x + num / x) # 迭代公式x(n+1) = 1/2 * (x(n) + num / x(n))
    return x

# recursion
def sqrt2(x, num):
    assert x > 0 # 初值点x不为负数
    if abs(x ** 2 - num) < 1e-9:
        return x
    x = 0.5 * (x + num / x)
    return sqrt2(x, num)

print sqrt(4)
print sqrt(16)
print sqrt(100)
print sqrt2(-1.0, 4) # error
print sqrt2(1.0, 4)
print sqrt2(2.0, 16)
print sqrt2(5.0, 100) # 选取不同的初值点x

下面是sqrt(100)的迭代过程, x=1.0

50.5
26.2400990099
15.02553012
10.840434673
10.032578511
10.0000528956
10.0000000001
10.0
10.0

越靠近答案计算次数越少，比如说100的话是10只用计算一次，但是有些点可能没有答案如极值点如0