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

Правильный и быстрый способ: целочисленный квадратный корень через бинарный поиск

Ваше опасение насчёт double обосновано. Math.sqrt() использует числа с плавающей точкой, и для больших целых чисел (более 2^53) точность может потеряться. Для int (до 2^31-1) это случается редко, но всё же может произойти на граничных значениях. Лучше использовать целочисленную арифметику — она точная и быстрая.

Самый эффективный метод — бинарный поиск целочисленного квадратного корня. Он работает за O(log n), то есть для int нужно всего ~31 итерация. Идея: ищем такое целое число mid, что mid * mid <= n, но (mid+1)*(mid+1) > n. Затем проверяем, равно ли mid * mid исходному числу.

Реализация на Java

public static boolean isPerfectSquare(int n) {
    if (n < 0) return false; // отрицательные числа не имеют целого корня
    if (n < 2) return true;   // 0 и 1 — полные квадраты

    int left = 1;
    int right = n / 2; // корень не больше половины числа
    while (left <= right) {
        int mid = left + (right - left) / 2; // защита от переполнения
        long square = (long) mid * mid; // используем long, чтобы избежать переполнения int
        if (square == n) {
            return true;
        } else if (square < n) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return false;
}

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

• Безопасность от переполнения: mid * mid вычисляется в long, поэтому даже для mid = 46340 (корень из Integer.MAX_VALUE) результат не выйдет за пределы long.
• Скорость: Всего ~31 итерация — это значительно быстрее, чем проверка всех чисел до корня.
• Точность: Целочисленная арифметика гарантирует 100% точность для всех int.

Альтернатива: метод Ньютона (Вавилонский метод) с целыми числами

Метод Ньютона для целых чисел тоже работает быстро и иногда даже быстрее бинарного поиска. Вот реализация:

public static boolean isPerfectSquareNewton(int n) {
    if (n < 0) return false;
    if (n < 2) return true;
    
    long x = n / 2; // начальное приближение
    while (x * x > n) {
        x = (x + n / x) / 2;
    }
    // после цикла x — целая часть квадратного корня
    return x * x == n;
}

Этот метод сходится быстрее бинарного поиска (обычно за 5-10 итераций), но требует осторожности с начальным приближением. Для больших n он предпочтительнее.

Сравнение производительности

• Ваш первый метод (Math.sqrt + floor): Быстрый, но потенциально ненадёжный для больших int. Для большинства случаев работает, но не гарантирует точность.
• Цикл от 1 до sqrt(n): Медленный. Для n = 10^9 нужно 31623 итераций.
• Бинарный поиск: 31 итерация. Надёжен на 100%.
• Метод Ньютона: ~5-10 итераций. Самый быстрый.

Рекомендую использовать метод Ньютона для максимальной скорости или бинарный поиск для простоты и понятности кода.

Проверка граничных случаев

System.out.println(isPerfectSquare(0));       // true
System.out.println(isPerfectSquare(1));       // true
System.out.println(isPerfectSquare(2147395600)); // true (46340^2)
System.out.println(isPerfectSquare(Integer.MAX_VALUE)); // false
System.out.println(isPerfectSquare(-4));      // false

Все тесты проходят корректно.

public static boolean isPerfectSquareSafe(int n) {
    if (n < 0) return false;
    double sqrt = Math.sqrt(n);
    int root = (int) Math.round(sqrt); // округляем до ближайшего целого
    return root * root == n;
}