Какой алгоритм позволяет вычислить квадратный корень, используя только базовые арифметические операции?

Для этой цели идеально подходит метод Ньютона (также известный как метод касательных). Это итерационный алгоритм, который позволяет быстро находить приближённое значение корня функции.

Для нахождения квадратного корня из числа n формула для каждой следующей итерации выглядит так:

x_next = 0.5 * (x_current + n / x_current)

Где x_current — текущее приближение, а x_next — следующее, более точное.

Как это работает:

1. Выбирается начальное приближение x (например, само число n).
2. На каждой итерации вычисляется новое приближение x_next по формуле.
3. Процесс повторяется до тех пор, пока разница между x_next и x_current не станет меньше заданной точности (эпсилон, ε).

Пример реализации на Python:

def sqrt_newton(n: float, epsilon: float = 1e-10) -> float:
    """Вычисляет квадратный корень из n методом Ньютона."""
    if n < 0:
        raise ValueError("Нельзя извлечь корень из отрицательного числа")
    if n == 0:
        return 0

    guess = n  # Начальное приближение
    while True:
        next_guess = 0.5 * (guess + n / guess)
        # Проверяем, достигнута ли нужная точность
        if abs(next_guess - guess) < epsilon:
            return next_guess
        guess = next_guess

# Тестирование
number = 25
result = sqrt_newton(number)
print(f"Квадратный корень из {number} равен {result}") # ~5.0

number = 2
result = sqrt_newton(number)
print(f"Квадратный корень из {number} равен {result}") # ~1.41421356237

Этот метод очень эффективен и быстро сходится, используя только операции сложения, умножения и деления.