Checking if a number is a perfect square (without Math)

Question

I typed this up quickly as an intuitive solution for determining if a given number is a perfect square.

How could I improve this? I already know that it doesn't handle the case where the number is 1. I'm wondering if I could generalize the calculation so it rounds up. What can I look into to develop a mindset for tackling these sorts of problems?

int number = 1000000;
int half = (number + 2 - 1)/2;
int square = 0;
boolean isSquare = false;

for( int i = half; i > 0 ; i-- ){

    square = i*i;

    if( square > number )
        continue;

    if( square == number ){
        System.out.println( "This number is a perfect square" );
        isSquare = true;
        break;
    } 

}

if( !isSquare ){
    System.out.println( "This number is not a perfect square" );
}

Answer 1

You could make use of the fact that n² = the sum of the first n odd numbers (for integral n ≥ 0), rather than having to compute i * i every time through the loop.

Answer 2

You can narrow down your search range. If a number requires n bits to represent, its square root is between 1 << ((n-1) / 2) and 1 << ((n+1) / 2). You can determine number of bits with something like:

int numBits(long l) {
  for (int i = 62; i >= 0; i--) {
    if (l & (1 << i)) return i + 1;
  }
  return 0;
}

Answer 3

There are significant improvements that can be made by choosing a more optimal algorithm.

Better algorithms for finding the root of x² - n = 0 are :

• Halving intervals to search for the root. This is called the bisection method.

• Even faster would be Newton's method : follow the tangent line on your current approximated root, to find a closer approximation.

Note the pseudo code on the linked wiki pages.

Both are defined to use reals, but can easily be adapted to accept only integer results : once improvements stop or are less than the distance to the nearest integer, you either have found an exact integer result, or the root isn't an integer.

Answer 4

What you need is to use integer square root algorithm and verify that the root's square value is the original number (e.g. x == isqrt(x)^2).

You can find integer square root algorithm code here: http://medialab.freaknet.org/martin/src/sqrt/