1. Обзор
Совершенный квадрат — это число, которое можно выразить как произведение двух одинаковых целых чисел.
В этой статье мы рассмотрим несколько способов определить, является ли целое число совершенным квадратом в Java. Также мы обсудим преимущества и недостатки каждого подхода, чтобы оценить их эффективность и определить, какой из них самый быстрый.
2. Проверка, является ли целое число совершенным квадратом
Как известно, в Java есть два типа данных для представления целых чисел. Первый — это int, который занимает 32 бита, а второй — long, занимающий 64 бита. В этой статье мы будем использовать long, чтобы охватить худший случай (наибольшее возможное целое число).
Поскольку long в Java занимает 64 бита, его диапазон составляет от -9,223,372,036,854,775,808 до 9,223,372,036,854,775,807. А так как мы имеем дело с совершенными квадратами, нас интересуют только положительные числа, потому что умножение любого целого числа само на себя всегда даёт положительный результат.
Кроме того, поскольку наибольшее число составляет примерно 2⁶³, это означает, что существует примерно 2³¹.⁵ целых чисел, квадраты которых меньше 2⁶³. Можно предположить, что использование таблицы поиска для этих чисел будет неэффективным.
2.1. Использование метода sqrt в Java
Самый простой и прямолинейный способ проверить, является ли число совершенным квадратом — использовать функцию sqrt. Она возвращает значение типа double, поэтому нужно привести результат к long и умножить на самого себя. Затем проверяем, равен ли результат исходному числу:
public static boolean isPerfectSquareByUsingSqrt(long n) {
if (n <= 0) {
return false;
}
double squareRoot = Math.sqrt(n);
long tst = (long)(squareRoot + 0.5);
return tst * tst == n;
}
Обратите внимание, что может понадобиться добавить 0.5 к результату из-за возможных ошибок округления при работе с типом double. Иногда целое число, преобразованное в double, может выглядеть как 3.00000001 или 2.99999999. Чтобы избежать этого, добавляем 0.5 перед приведением к long, чтобы получить точное значение.
Кроме того, если мы протестируем функцию sqrt на одном числе, время выполнения будет быстрым. Однако если нужно вызывать её много раз, и при этом пытаемся сократить количество операций, подобная микрооптимизация может оказаться полезной.
2.2. Использование бинарного поиска
Мы можем использовать бинарный поиск для нахождения квадратного корня числа без использования sqrt.
Поскольку диапазон чисел — от 1 до 2⁶³, корень будет находиться в пределах от 1 до 2³¹.⁵. Алгоритму бинарного поиска потребуется около 16 итераций для нахождения корня:
public boolean isPerfectSquareByUsingBinarySearch(long low, long high, long number) {
long check = (low + high) / 2L;
if (high < low) {
return false;
}
if (number == check * check) {
return true;
}
else if (number < check * check) {
high = check - 1L;
return isPerfectSquareByUsingBinarySearch(low, high, number);
}
else {
low = check + 1L;
return isPerfectSquareByUsingBinarySearch(low, high, number);
}
}
2.3. Улучшения бинарного поиска
Чтобы улучшить бинарный поиск, можно заметить, что определение количества цифр в числе даёт нам диапазон возможного квадратного корня.
Например, если число состоит из одной цифры, диапазон корня — от 1 до 4. Причина — максимальное однозначное число — 9, а его корень — 3. Если число состоит из двух цифр, диапазон — от 4 до 10 и так далее.
Поэтому мы можем построить таблицу диапазонов корня на основе количества цифр в исходном числе. Это сократит диапазон бинарного поиска, а значит — и количество итераций:
public class BinarySearchRange {
private long low;
private long high;
// стандартный конструктор и геттеры
}
private void initiateOptimizedBinarySearchLookupTable() {
lookupTable.add(new BinarySearchRange());
lookupTable.add(new BinarySearchRange(1L, 4L));
lookupTable.add(new BinarySearchRange(3L, 10L));
for (int i = 3; i < 20; i++) {
lookupTable.add(
new BinarySearchRange(
lookupTable.get(i - 2).low * 10,
lookupTable.get(i - 2).high * 10));
}
}
public boolean isPerfectSquareByUsingOptimizedBinarySearch(long number) {
int numberOfDigits = Long.toString(number).length();
return isPerfectSquareByUsingBinarySearch(
lookupTable.get(numberOfDigits).low,
lookupTable.get(numberOfDigits).high,
number);
}
2.4. Метод Ньютона с целочисленной арифметикой
Обычно метод Ньютона используется для вычисления квадратного корня любого числа, даже нецелого. Основная идея: предполагаем, что число X является корнем числа N, и начинаем цикл, постепенно приближаясь к правильному значению.
С некоторыми изменениями этот метод можно использовать для проверки совершенного квадрата:
public static boolean isPerfectSquareByUsingNewtonMethod(long n) {
long x1 = n;
long x2 = 1L;
while (x1 > x2) {
x1 = (x1 + x2) / 2L;
x2 = n / x1;
}
return x1 == x2 && n % x1 == 0L;
}
3. Оптимизация алгоритмов вычисления квадратного корня целого числа
Как мы уже обсудили, существует несколько алгоритмов для проверки, является ли число совершенным квадратом. Тем не менее, любой из этих алгоритмов можно оптимизировать с помощью некоторых приёмов.
Эти приёмы направлены на то, чтобы избежать выполнения основных вычислений, связанных с нахождением квадратного корня. Например, мы можем сразу исключить отрицательные числа.
Один из полезных фактов: совершенные квадраты в шестнадцатеричной системе могут оканчиваться только на 0, 1, 4 или 9. Поэтому мы можем сначала перевести число в шестнадцатеричную систему, а затем исключить те случаи, которые точно не могут быть совершенными квадратами:
public static boolean isPerfectSquareWithOptimization(long n) {
if (n < 0) {
return false;
}
switch((int)(n & 0xF)) {
case 0: case 1: case 4: case 9:
long tst = (long)Math.sqrt(n);
return tst * tst == n;
default:
return false;
}
}
4. Заключение
В этой статье мы рассмотрели несколько способов определения, является ли целое число совершенным квадратом. Как мы увидели, алгоритмы всегда можно улучшить с помощью определённых приёмов.
Эти приёмы позволяют исключить большое количество неподходящих случаев ещё до начала основных вычислений. Это возможно потому, что множество чисел легко определить как несовершенные квадраты.
Оригинал статьи: https://www.baeldung.com/java-find-if-square-root-is-integer