Как проверить, что корень из числа — целое число: 5 методов в Java

Введение: задача, которая взрывает Stack Overflow

Представьте: вы пишете код, который обрабатывает тысячи чисел в секунду. Вам нужно отсеять те, квадратный корень которых — целое число (1, 4, 9, 16…). Казалось бы, что сложного? Взял Math.sqrt(), проверил остаток — и дело в шляпе. Но не всё так просто.

Вопрос «Fastest way to determine if an integer's square root is an integer» на Stack Overflow собрал уже больше 100 000 просмотров. Почему? Потому что Math.sqrt() — операция с плавающей точкой, а значит, она медленная и подвержена ошибкам округления. Для больших чисел (например, 2^50) double может просто «соврать».

В этой статье мы разберём 5 подходов на Java: от самого наивного до быстрых алгоритмов, которые используют битовые операции и целочисленную арифметику. Вы узнаете, какой метод реально быстрее, а какой — безопаснее. Поехали!

Постановка задачи

Нам нужно написать метод boolean isPerfectSquare(long n), который возвращает true, если n — полный квадрат (perfect square). Примеры:

• isPerfectSquare(25) → true (5*5)
• isPerfectSquare(26) → false
• isPerfectSquare(0) → true (0*0)
• isPerfectSquare(1) → true

Мы будем тестировать на long, так как int — частный случай, а long даёт больше пространства для ошибок.

Метод 1: Наивный — Math.sqrt + проверка остатка

Самый простой способ, который приходит в голову новичку:

public static boolean isPerfectSquareSqrt(long n) {
    if (n < 0) return false;
    double sqrt = Math.sqrt(n);
    long floorSqrt = (long) sqrt;
    return floorSqrt * floorSqrt == n;
}

Проблема №1: Точность. Для чисел больше ~2^53 (9 007 199 254 740 991) double перестаёт точно представлять целые числа. Пример: n = 999999999999999999L — Math.sqrt вернёт неверный результат.

Проблема №2: Скорость. Math.sqrt — инструкция процессора (FSQRT), но она всё равно медленнее простых арифметических операций.

Когда использовать: Только для int или небольших long (< 10^12), где скорость не критична.

Метод 2: Целочисленный квадратный корень через Newton-Raphson

Метод Ньютона (Newton-Raphson) — классический способ вычислить квадратный корень без чисел с плавающей точкой. Итеративно уточняем приближение:

public static boolean isPerfectSquareNewton(long n) {
    if (n < 0) return false;
    if (n < 2) return true;
    long x = n;
    long y = (x + 1) / 2;
    while (y < x) {
        x = y;
        y = (y + n / y) / 2;
    }
    return x * x == n;
}

Алгоритм сходится очень быстро — за O(log log n) итераций. Для чисел до Long.MAX_VALUE нужно всего 6-8 итераций.

Плюсы: Абсолютная точность для всех long (до 2^63-1). Не использует double.

Минусы: Деление — дорогая операция. Для очень маленьких чисел (n < 4) можно добавить проверку в начале.

Метод 3: Бинарный поиск корня

Ещё один классический алгоритм — ищем корень бинарным поиском на отрезке [0, n]. Для long максимальное значение корня — 3 037 000 499 (sqrt(Long.MAX_VALUE)).

public static boolean isPerfectSquareBinary(long n) {
    if (n < 0) return false;
    if (n < 2) return true;
    long low = 1;
    long high = 3037000499L; // sqrt(Long.MAX_VALUE)
    while (low <= high) {
        long mid = (low + high) >>> 1;
        long square = mid * mid;
        if (square == n) return true;
        else if (square < n) low = mid + 1;
        else high = mid - 1;
    }
    return false;
}

Важный нюанс: mid * mid может переполниться для больших mid. В Java long переполняется молча, поэтому нужно либо использовать BigInteger, либо проверять переполнение. В примере выше high = 3 037 000 499, квадрат этого числа ~9.22e18, что меньше Long.MAX_VALUE (9.22e18), так что переполнения нет. Но для безопасности можно написать:

long square;
if (mid > Long.MAX_VALUE / mid) {
    // переполнение — значит, square будет > n
    high = mid - 1;
    continue;
}
square = mid * mid;

Производительность: O(log n) — примерно 32 итерации для long. Каждая итерация — одно умножение и одно сравнение. Это медленнее, чем Newton (6-8 итераций), но проще для понимания.

Метод 4: Битовые трюки — отсечение заведомо неподходящих чисел

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

Факт: квадрат целого числа по модулю 16 может быть только 0, 1, 4, 9. То есть если n % 16 не входит в это множество — можно сразу вернуть false, не вычисляя корень.

public static boolean isPerfectSquareFilter(long n) {
    if (n < 0) return false;
    // Быстрый отсев по модулю 16
    long mod16 = n & 15; // n % 16
    if (mod16 != 0 && mod16 != 1 && mod16 != 4 && mod16 != 9) {
        return false;
    }
    // Дальше используем любой точный метод, например Newton
    return isPerfectSquareNewton(n);
}

Почему это ускоряет? Около 75% чисел отбрасываются на первом же шаге. Битовые операции (n & 15) выполняются за один такт процессора. Затем только 25% чисел проходят дальше, где уже используется Newton.

Можно расширить фильтр: по модулю 24 (остатки 0,1,4,9,12,16), по модулю 48 и так далее. Но с ростом модуля растёт и размер таблицы — нужно найти баланс.

Метод 5: Комбинация фильтра + Newton (рекомендуемый)

Лучший способ для production — объединить быстрый фильтр с точным алгоритмом:

public static boolean isPerfectSquare(long n) {