## 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 2^{63}, that means there are about 2^{31.5} integers whose square is less than 2^{63}. 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 2^{63}, the root is between 1 and 2^{31.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,
```

```
number);
}
```

### 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.

res – REST with Spring (eBook) (everywhere)