惨痛的教训——阿里一面

编程送分题，结果当时可能脑子进💩了，面试结束后，才知道自己有多么愚蠢。此贴仅以记录这一愚蠢时刻。
引以为戒。勿怠勿忘。
题目：求一整数的平方根，精确到0.001。

二分法

def sqrt_bi(num):
    if num < 0:
        raise ValueError("Please enter vaild number!")
    if num == 0:
        return 0
    min_num = 0
    max_num = num
    while True:
        if max_num * max_num == num or max_num - min_num < 1e-4:
            return round(max_num, 3)
        if min_num * min_num == num:
            return round(min_num, 3)
        mid = (max_num + min_num) / 2
        if mid * mid > num:
            max_num = mid
        else:
            min_num = mid

牛顿法

牛顿法用来求解方程$f(x)=0$的根。
原理：在初始值处做切线，该切线与x轴的交点作为下一个迭代值。切线方程为$y=f(x_0)+f’(x_0)(x-x_0)$，其与x轴交点为$x_1 = x_0-f(x_0)/f’(x_0)$。
对于方程$x^2-n=0$，更新式为$x^{new}=x^{old}-\frac{x^{old}-\frac{n}{x^{old}}}{2}$。

def sqrt_newton(num):
    if num < 0:
        raise ValueError('Please enter a valid number!')
    if num == 0 or num == 1:
        return num
    last, res = 0, 1
    while abs(last - res) > 1e-3:
        last = res
        res -= (res - num / res) / 2
    return round(res, 3)