Python 中使用二分法和牛顿法求整数平方根

本文将介绍如何使用 Python 中的二分法和牛顿法来求一个整数的平方根。

给定一个整数 c，其中 c >= 1，我们需要找到最大的整数 a，使得 a * a <= c。换句话说，我们需要判断 c 是否为一个整数的平方，如果是，则返回 True 和 a，否则返回 False 和 a。

例如，int_sqrt(16) 返回 (True, 4)，因为 4 * 4 = 16。而 int_sqrt(17) 返回 (False, 4)，因为 4 * 4 < 17 且 5 * 5 > 17。

我们将通过以下两种方法来实现 int_sqrt 函数：

（A）二分法

使用二分法的思路是：

初始化两个变量 a 和 b，分别代表搜索范围的起始值和结束值。初始值为 a = 0，b = c。
循环直到 a <= b。
在每次循环中，计算中间值 mid = (a + b) // 2。
如果 mid * mid == c，则找到了平方根，返回 True 和 mid。
如果 mid * mid < c，则将 a 设置为 mid + 1，因为平方根应该在 mid 的右侧。
否则，将 b 设置为 mid - 1，因为平方根应该在 mid 的左侧。
如果循环结束，则返回 False 和 a - 1，因为 a 表示在循环结束时找到的最大的平方小于 c 的整数。

以下是使用二分法实现 int_sqrt 函数的代码：

def int_sqrt(c):
    a = 0
    b = c
    iterations = 0

    while a <= b:
        iterations += 1
        mid = (a + b) // 2
        if mid * mid == c:
            return True, mid
        elif mid * mid < c:
            a = mid + 1
        else:
            b = mid - 1

    return False, a - 1, iterations

x1 = 12345678901234567890
x2 = 123456789012345678901234567890

c1 = x1 * x1
c2 = x1 * x1 + 1
c3 = x2 * x2
c4 = x2 * x2 + 1

print('使用二分法：')
print('c1:', int_sqrt(c1))
print('c2:', int_sqrt(c2))
print('c3:', int_sqrt(c3))
print('c4:', int_sqrt(c4))

（B）牛顿法

牛顿法使用迭代的方式来求解方程的根。具体而言，我们可以通过迭代公式 a_{n+1} = (a_n + c / a_n) // 2 来逼近 c 的平方根。

使用牛顿法的思路是：

初始化变量 a，初始值为 c // 2。
循环直到 new_a >= a。
在每次循环中，计算新的估计值 new_a = (a + c // a) // 2。
如果 new_a >= a，则说明已经找到了最大的平方小于 c 的整数，返回 False 和 a。
否则，更新 a 为 new_a，继续迭代。

以下是使用牛顿法实现 int_sqrt 函数的代码：

def int_sqrt(c):
    a = c // 2
    iterations = 0

    while True:
        iterations += 1
        new_a = (a + c // a) // 2
        if new_a >= a:
            return False, a, iterations
        a = new_a

    return False, a, iterations

x1 = 12345678901234567890
x2 = 123456789012345678901234567890

c1 = x1 * x1
c2 = x1 * x1 + 1
c3 = x2 * x2
c4 = x2 * x2 + 1

print('使用牛顿法：')
print('c1:', int_sqrt(c1))
print('c2:', int_sqrt(c2))
print('c3:', int_sqrt(c3))
print('c4:', int_sqrt(c4))

以上代码分别使用二分法和牛顿法实现了 int_sqrt 函数，并打印出了循环次数。您可以尝试使用不同的输入值来测试这两个算法的效率。

需要注意的是，牛顿法在某些情况下可能需要更多次迭代才能收敛。此外，由于浮点数的精度限制，牛顿法可能无法完全精确地找到平方根。但是，对于整数的平方根，我们可以通过使用整数运算来避免精度问题。