Check if BigInteger is not a perfect square
Compute the integer square root, then check that its square is your number. Here is my method of computing the square root using Heron's method:
private static final BigInteger TWO = BigInteger.valueOf(2);
/**
* Computes the integer square root of a number.
*
* @param n The number.
*
* @return The integer square root, i.e. the largest number whose square
* doesn't exceed n.
*/
public static BigInteger sqrt(BigInteger n)
{
if (n.signum() >= 0)
{
final int bitLength = n.bitLength();
BigInteger root = BigInteger.ONE.shiftLeft(bitLength / 2);
while (!isSqrt(n, root))
{
root = root.add(n.divide(root)).divide(TWO);
}
return root;
}
else
{
throw new ArithmeticException("square root of negative number");
}
}
private static boolean isSqrt(BigInteger n, BigInteger root)
{
final BigInteger lowerBound = root.pow(2);
final BigInteger upperBound = root.add(BigInteger.ONE).pow(2);
return lowerBound.compareTo(n) <= 0
&& n.compareTo(upperBound) < 0;
}
I found a sqrt method used here, and simplified the square test.
private static final BigInteger b100 = new BigInteger("100");
private static final boolean[] isSquareResidue;
static{
isSquareResidue = new boolean[100];
for(int i =0;i<100;i++){
isSquareResidue[(i*i)%100]=true;
}
}
public static boolean isSquare(final BigInteger r) {
final int y = (int) r.mod(b100).longValue();
boolean check = false;
if (isSquareResidue[y]) {
final BigInteger temp = sqrt(r);
if (r.compareTo(temp.pow(2)) == 0) {
check = true;
}
}
return check;
}
public static BigInteger sqrt(final BigInteger val) {
final BigInteger two = BigInteger.valueOf(2);
BigInteger a = BigInteger.ONE.shiftLeft(val.bitLength() / 2);
BigInteger b;
do {
b = val.divide(a);
a = (a.add(b)).divide(two);
} while (a.subtract(b).abs().compareTo(two) >= 0);
return a;
}