«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. А поскольку мы имеем дело с идеальными квадратами, нас интересует только набор положительных целых чисел, потому что умножение любого целого числа само на себя всегда дает положительное число.
Кроме того, поскольку наибольшее число равно примерно 263, это означает, что существует около 231,5 целых чисел, квадрат которых меньше 263. Кроме того, мы можем предположить, что наличие таблицы поиска этих чисел неэффективно.
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 до 263, корень находится между 1 и 231,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.