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

Проблема с плавающей точкой и циклом

Ваш цикл работает за O(√n), что для максимального int (~2.1×10⁹) даёт ~46340 итераций — это ещё терпимо, но для long или многократных вызовов становится проблемой. Math.sqrt() быстр, но double имеет 52 бита мантиссы, что не гарантирует точность для чисел > 2⁵³. Для int (32 бита) он точен, если результат — целое число, но из-за округления может ошибиться на границе. Например, для n = 2_147_395_600 (46340²) Math.sqrt() вернёт 46340.0, а для n = 2_147_395_601 — уже может быть 46340.00000000001, что после (int) даст 46340, но проверка (int)sqrt * (int)sqrt == n не пройдёт. Поэтому нужен надёжный метод.

Лучшее решение: целочисленный бинарный поиск

Используйте бинарный поиск по диапазону [0, 46340] (так как 46340² = 2_147_395_600 < Integer.MAX_VALUE, а 46341² переполняет int). Для long нужно [0, 3_037_000_499]. Этот метод работает за O(log n) — всего ~16 итераций для int. Он абсолютно точен, так как использует только целочисленную арифметику.

public static boolean isPerfectSquare(int n) {
    if (n < 0) return false;
    int low = 0;
    int high = 46340; // floor(sqrt(Integer.MAX_VALUE))
    while (low <= high) {
        int mid = low + (high - low) / 2;
        long midSq = (long) mid * mid; // long, чтобы избежать переполнения
        if (midSq == n) {
            return true;
        } else if (midSq < n) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return false;
}

Почему это работает:

• Мы ищем целое число mid, квадрат которого равен n.
• Диапазон [0, 46340] гарантирует, что mid² не переполнит int, но мы всё равно используем long для умножения — на всякий случай.
• Бинарный поиск гарантирует логарифмическое время.

Ещё быстрее: метод Ньютона с целочисленной арифметикой

Метод Ньютона (или Вавилонский метод) для целых чисел сходится за ~log₂(n) итераций, но на практике быстрее бинарного поиска. Реализация:

public static boolean isPerfectSquare(int n) {
    if (n < 0) return false;
    if (n == 0 || n == 1) return true;
    long x = n; // используем long, чтобы избежать переполнения
    long y = (x + 1) / 2;
    while (y < x) {
        x = y;
        y = (x + n / x) / 2;
    }
    return x * x == n;
}

Объяснение:

• Начальное приближение: y = (n + 1) / 2 (грубая оценка).
• Итерация: y = (x + n / x) / 2 — это метод Ньютона для sqrt(n).
• Условие выхода: когда y >= x, мы нашли целый корень (или его floor).
• Проверка: x * x == n. Если true — идеальный квадрат.

Этот метод делает ~8-10 итераций для int, что быстрее бинарного поиска. Он точен, так как все операции целочисленные.

Рекомендация

Используйте метод Ньютона — он и быстр, и прост. Для максимальной надёжности добавьте проверку на отрицательные числа и ноль. Если нужно обрабатывать long, замените int на long и увеличьте начальное приближение (например, y = (n + 1) / 2).

public static boolean isPerfectSquare(int n) {
    if (n < 0) return false;
    // Быстрая проверка по модулю 16
    int mod16 = n & 15; // n % 16
    if (mod16 != 0 && mod16 != 1 && mod16 != 4 && mod16 != 9) {
        return false;
    }
    // Далее используем метод Ньютона или бинарный поиск
    long x = n;
    long y = (x + 1) / 2;
    while (y < x) {
        x = y;
        y = (x + n / x) / 2;
    }
    return x * x == n;
}