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

Вычисление квадратного корня только с +, -, *, /

Это классическая задача на собеседованиях. Требуется реализовать sqrt(x) без использования встроенной функции, используя только арифметические операции.

Подход 1: Вавилонский метод (Newton's Method)

Проверенный метод итеративного приближения:

def sqrt(x: float, epsilon: float = 1e-6) -> float:
    """Вычисляет квадратный корень методом Ньютона.
    
    Формула: next_guess = (guess + x/guess) / 2
    Идея: если guess слишком большой, то x/guess слишком маленький,
          среднее значение ближе к реальному корню.
    """
    if x < 0:
        raise ValueError("Cannot compute sqrt of negative number")
    
    if x == 0:
        return 0
    
    # Начальное приближение
    guess = x / 2 if x > 1 else x
    
    # Итеративное улучшение
    while True:
        # Следующее приближение
        next_guess = (guess + x / guess) / 2
        
        # Проверка сходимости
        if abs(next_guess - guess) < epsilon:
            return next_guess
        
        guess = next_guess

# Использование
print(sqrt(2))      # 1.4142135623730951
print(sqrt(9))      # 3.0
print(sqrt(0.25))   # 0.5
print(sqrt(100))    # 10.0

Анализ сложности:

• Time: O(log n) — быстрое сходимость
• Space: O(1) — константная память

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

# Пример: sqrt(9)
guess = 4.5

# Итерация 1
next_guess = (4.5 + 9/4.5) / 2 = (4.5 + 2.0) / 2 = 3.25

# Итерация 2
guess = 3.25
next_guess = (3.25 + 9/3.25) / 2 = (3.25 + 2.769) / 2 = 3.009

# Итерация 3
guess = 3.009
next_guess = (3.009 + 9/3.009) / 2 ≈ 3.0

# Сходится к 3

Подход 2: Бинарный поиск

Для целых чисел:

def sqrt_binary_search(x: int) -> int:
    """Вычисляет целую часть корня через бинарный поиск.
    
    Ищем число n такое что n*n <= x < (n+1)*(n+1)
    """
    if x == 0:
        return 0
    
    left, right = 1, x
    
    while left <= right:
        mid = (left + right) // 2
        
        if mid * mid == x:
            return mid
        elif mid * mid < x:
            left = mid + 1  # Корень больше
        else:
            right = mid - 1  # Корень меньше
    
    # left - 1 это целая часть корня
    return right

# Использование
print(sqrt_binary_search(9))    # 3
print(sqrt_binary_search(8))    # 2 (целая часть sqrt(8))
print(sqrt_binary_search(100))  # 10

Анализ:

• Time: O(log x)
• Space: O(1)

Подход 3: Улучшенный Newton (для целых чисел)

def isqrt(n: int) -> int:
    """Целый квадратный корень через Newton's method."""
    if n < 0:
        raise ValueError("Cannot compute sqrt of negative")
    
    if n < 2:
        return n
    
    # Начальное приближение
    x = n
    y = (x + 1) // 2
    
    while y < x:
        x = y
        y = (x + n // x) // 2  # Целочисленное деление
    
    return x

# Использование
print(isqrt(9))     # 3
print(isqrt(8))     # 2
print(isqrt(10))    # 3

Подход 4: Полная реализация с проверками

class SquareRootCalculator:
    """Вычисление квадратного корня различными методами."""
    
    @staticmethod
    def newton_method(x: float, max_iterations: int = 100, 
                     epsilon: float = 1e-9) -> float:
        """Newton's метод с контролем итераций."""
        if x < 0:
            raise ValueError("Cannot compute sqrt of negative")
        
        if x == 0:
            return 0.0
        
        # Лучше начальное приближение
        if x >= 1:
            guess = x / 2
        else:
            guess = x
        
        for i in range(max_iterations):
            prev_guess = guess
            guess = (guess + x / guess) / 2
            
            # Проверка сходимости
            if abs(guess - prev_guess) < epsilon:
                return guess
        
        return guess
    
    @staticmethod
    def binary_search(x: int) -> int:
        """Бинарный поиск для целых чисел."""
        if x < 2:
            return x
        
        left, right = 1, x // 2
        
        while left <= right:
            mid = (left + right) // 2
            sq = mid * mid
            
            if sq == x:
                return mid
            elif sq < x:
                left = mid + 1
            else:
                right = mid - 1
        
        return right
    
    @staticmethod
    def babylonian(x: float, iterations: int = 20) -> float:
        """Вавилонский метод с фиксированным числом итераций."""
        if x < 0:
            raise ValueError("Cannot compute sqrt of negative")
        
        if x == 0:
            return 0.0
        
        result = x / 2
        
        for _ in range(iterations):
            result = (result + x / result) / 2
        
        return result

# Тесты
calc = SquareRootCalculator()

print("Newton's method:")
print(calc.newton_method(2))     # 1.414...
print(calc.newton_method(9))     # 3.0
print(calc.newton_method(0.25))  # 0.5

print("\nBinary search:")
print(calc.binary_search(9))     # 3
print(calc.binary_search(8))     # 2
print(calc.binary_search(10))    # 3

print("\nBabylonian:")
print(calc.babylonian(2))        # 1.414...
print(calc.babylonian(9))        # 3.0

Тесты для собеседования

import unittest

class TestSquareRoot(unittest.TestCase):
    
    def test_perfect_squares(self):
        """Тест идеальных квадратов."""
        self.assertEqual(sqrt_binary_search(0), 0)
        self.assertEqual(sqrt_binary_search(1), 1)
        self.assertEqual(sqrt_binary_search(4), 2)
        self.assertEqual(sqrt_binary_search(9), 3)
        self.assertEqual(sqrt_binary_search(16), 4)
        self.assertEqual(sqrt_binary_search(100), 10)
    
    def test_non_perfect_squares(self):
        """Целая часть для непerfect квадратов."""
        self.assertEqual(sqrt_binary_search(2), 1)
        self.assertEqual(sqrt_binary_search(8), 2)
        self.assertEqual(sqrt_binary_search(10), 3)
    
    def test_float_newton(self):
        """Тест Newton's method."""
        self.assertAlmostEqual(sqrt(2), 1.414, places=3)
        self.assertAlmostEqual(sqrt(9), 3.0, places=6)
        self.assertAlmostEqual(sqrt(0.25), 0.5, places=6)
    
    def test_edge_cases(self):
        """Edge cases."""
        self.assertEqual(sqrt_binary_search(0), 0)
        self.assertEqual(sqrt_binary_search(1), 1)
        self.assertAlmostEqual(sqrt(1e-6), 0.001, places=6)
    
    def test_large_numbers(self):
        """Большие числа."""
        self.assertEqual(sqrt_binary_search(10**6), 1000)
        self.assertAlmostEqual(sqrt(10**9), 31622.77, places=2)

if __name__ == "__main__":
    unittest.main()

Сравнение методов

На собеседовании

Шаг 1: Уточнить требования

Вопрос: "Нужна ли вам целая часть или точное число?"
Ответ: Определяет выбор метода

Шаг 2: Выбрать метод

Целые числа? → Binary Search
Вещественные? → Newton's Method

Шаг 3: Реализовать

def sqrt(x):
    if x < 0:
        return None
    if x == 0:
        return 0
    guess = x / 2
    while True:
        next_guess = (guess + x / guess) / 2
        if abs(next_guess - guess) < 1e-6:
            return next_guess
        guess = next_guess

Шаг 4: Тестировать

assert sqrt(9) == 3
assert abs(sqrt(2) - 1.414) < 0.001

Почему это важно

1. Показывает понимание алгоритмов (Newton's method имеет квадратичную сходимость)
2. Решение без встроенных функций (как думаешь, не память)
3. Обработка edge cases (0, 1, отрицательные числа)
4. Trade-offs: скорость vs точность

Notes: На собеседованиях часто просят объяснить сложность и почему выбран этот метод.