1. Overview
A perfect square is a number that can be expressed as the product of two equal integers.
In this article, we’ll discover multiple ways to determine if an integer is a perfect square in Java. Also, we’ll discuss the advantages and disadvantages of each technique to determine its efficiency and which is the fastest.
2. Checking if an Integer Is a Perfect Square
As we know, Java gives us two data types for defining an integer. The first one is int, which represents the number in 32 bits, and the other is long, which represents the number in 64 bits. In this article, we’ll use the long data type to handle the worst case (the largest possible integer).
Since Java represents the long number in 64 bits, the range of the long number is from -9,223,372,036,854,775,808 to 9*,223,372,036,854,775,807*. And, since we’re handling perfect squares, we’re only concerned with handling the set of positive integers because multiplying any integer by itself will always produce a positive number.
In addition, since the largest number is about 263, that means there are about 231.5 integers whose square is less than 263. Also, we can suppose that having a lookup table of those numbers is inefficient.
2.1. Using the sqrt Method in Java
The easiest and most straightforward way to check whether an integer is a perfect square is to use the sqrt function. As we know, the sqrt function returns a double value. So, what we need to do is to cast the result to int and multiply it by itself. Then, we check if the result is equal to the integer we started with:
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;
}
Note that we may need to add 0.5 to the result due to the precision errors we can encounter when dealing with double values. Sometimes, integers could be represented with a decimal point when assigned to a double variable.
For example, if we assign the number 3 to a double variable, then the value of it maybe 3.00000001 or 2.99999999. So, to avoid this representation, we add 0.5 before casting it to a long to make sure that we’re getting the actual value.
In addition, if we test the sqrt function with one number, we’ll notice that the execution time is fast. On the other hand, if we need to call the sqrt function many times, and we try to reduce the number of operations executed by the sqrt function, this kind of micro-optimization could actually make a difference.
2.2. Using Binary Search
We can use a binary search to find the square root of a number without using the sqrt function.
Since the range of the number is from 1 to 263, the root is between 1 and 231.5. So, the binary search algorithm needs about 16 iterations to get the square root:
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. Enhancements on Binary Search
To enhance the binary search, we can notice that if we determine the number of digits of the basic number, that gives us the range of the root.
For example, if the number consists of one digit only, then the range of the square root is between 1 and 4. The reason is that the maximum integer from one digit is 9 and its root is 3. In addition, if the number is composed of two digits, the range is between 4 and 10, and so on.
So, we can build a lookup table to specify the range of the square root based on the number of digits of the number we start with. That will reduce the range of the binary search. So, it’ll need fewer iterations to get the square root:
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,
2.4. Newton’s Method With Integer Arithmetic
In general, we can use Newton’s method to get the square root of any number, even non-integers. The basic idea of Newton’s method is to suppose a number X is the square root of a number N. After that, we can start a loop and keep calculating the root, which will surely move towards the correct square root of N.
However, with some modifications to Newton’s method, we can use it to check whether an integer is a perfect square:
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. Optimizing Integer Square Root Algorithms
As we discussed, there are multiple algorithms to check the square roots of an integer. Nevertheless, we can always optimize any algorithm by using some tricks.
Tricks should consider avoiding executing the main operations that will determine the square root. For example, we can exclude negative numbers directly.
One of the facts that we can use is “perfect squares can only end in 0, 1, 4, or 9 in base 16”. So, we can convert an integer to base 16 before starting the computations. After that, we exclude the cases that consider the number as a non-perfect square root:
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. Conclusion
In this article, we discussed multiple ways to determine whether an integer is a perfect square or not. As we’ve seen, we can always enhance the algorithms by using some tricks.
These tricks will exclude a large number of cases before starting the main operation of the algorithm. The reason is that a lot of integers can be determined as non-perfect squares easily.
As always, the code presented in this article is available over on GitHub.