1. Обзор
Полный квадрат — это число, которое можно представить как произведение двух равных целых чисел.
В этой статье мы обнаружим несколько способов определить, является ли целое число идеальным квадратом в Java. Кроме того, мы обсудим преимущества и недостатки каждого метода, чтобы определить его эффективность и какой из них самый быстрый.
2. Проверка того, является ли целое число идеальным квадратом
Как мы знаем, Java предоставляет нам два типа данных для определения целого числа. Первый — это int , который представляет число в 32 битах, а другой — long , который представляет число в 64 битах. В этой статье мы будем использовать тип данных long для обработки наихудшего случая (наибольшего возможного целого числа).
Поскольку Java представляет длинное число в 64 битах, диапазон длинного числа составляет от -9 223 372 036 854 775 808 до 9 223 372 036 854 775 807 . А поскольку мы имеем дело с идеальными квадратами, нас интересует только набор положительных целых чисел, потому что умножение любого целого числа само на себя всегда дает положительное число.
Кроме того, поскольку наибольшее число равно примерно 2 ^63 , это означает, что существует около 2 ^31,5 целых чисел, квадрат которых меньше 2 ^63 . Кроме того, мы можем предположить, что наличие таблицы поиска этих чисел неэффективно.
2.1. Использование метода sqrt в Java
Самый простой и прямой способ проверить, является ли целое число полным квадратом, — использовать функцию sqrt . Как мы знаем, функция sqrt возвращает двойное значение. Итак, что нам нужно сделать, так это привести результат к типу int и умножить его сам на себя. Затем мы проверяем, равен ли результат целому числу, с которого мы начали:
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 число 3 , то ее значение может быть 3,00000001 или 2,99999999. Итак, чтобы избежать этого представления, мы добавляем 0,5 перед приведением к типу long , чтобы убедиться, что мы получаем действительное значение.
Кроме того, если мы протестируем функцию sqrt с одним числом, мы заметим, что время выполнения быстрое. С другой стороны, если нам нужно вызывать функцию sqrt много раз, и мы пытаемся уменьшить количество операций, выполняемых функцией sqrt , такая микрооптимизация действительно может иметь значение.
2.2. Использование бинарного поиска
Мы можем использовать бинарный поиск, чтобы найти квадратный корень числа без использования функции sqrt .
Так как диапазон числа от 1 до 2 ^63 , корень находится между 1 и 2 ^31,5 . Итак, алгоритму бинарного поиска требуется около 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;
// standard constructor and getters
}
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. После этого мы можем запустить цикл и продолжить вычисление корня, который, несомненно, будет двигаться к правильному квадратному корню из 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 по основанию 16» . Таким образом, мы можем преобразовать целое число в основание 16 перед началом вычислений. После этого исключаем случаи, когда число считается несовершенным квадратным корнем:
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. Вывод
В этой статье мы обсудили несколько способов определить, является ли целое число полным квадратом или нет. Как мы видели, мы всегда можем улучшить алгоритмы, используя некоторые приемы.
Эти приемы позволят исключить большое количество случаев до запуска основной работы алгоритма. Причина в том, что многие целые числа можно легко определить как несовершенные квадраты.
Как всегда, код, представленный в этой статье, доступен на GitHub .