Python使用牛顿迭代法和二分法计算任意大自然数的平方根近似值

在Python中，使用运算符“**”和内置模块math、cmath的函数sqrt()都可以直接计算平方根，其中运算符“**”和cmath.sqrt()可以计算负数的平方根，math.sqrt()的参数不能为负数。例如

Python中的整数可以非常非常非常大，但实数不能，而绝大部分整数的平方根是实数。也就是说，当整数大到一定程度以后，上面计算平方根的方法都不能用了。

那是不是就没法计算超大整数的平方根了呢？肯定不是，接下来我们就来看两个比较常用的方法。

1）牛顿迭代法

运行结果：

2）二分法查找

对于任意自然数n，其平方根一定在[1,n)区间内。可以使用线性搜索逐个测试区间内的自然数并检查其平方是否恰好为n，但这样的话当n变大时需要的时间非常多，收敛速度非常慢。下面的代码使用二分法查找快速缩小搜索范围并返回最接近于n的平方根的自然数。

运行结果：