Algorithm to find the largest square number smaller than n

Question

How can I find the largest square number (ie 4, 9, 16) smaller than a given int n efficiently? I have the following attempt:

int square = (int)Math.sqrt(number);
return square*square;

But it has the obvious inefficiency of getting a square root just so we can square it.

Answer 1

Up front: It should be noted that processors capable of doing sqrt as a machine instruction will be fast enough. No doubt, its (micro)program uses Newton-Raphson, and this algorithm is of quadratic convergence, doubling the number of accurate digits with each iteration.

So, ideas like this one aren't really worth pursuing, although they use nice properties of squares, etc. (See the next proposal)

// compute the root of the biggests square that is a power of two < n
public static int pcomp( int n ){
  long p2 = 1;
  int i = 0;
  while( p2 < n ){
    p2 <<= 2;
    i += 2;
  }
  p2 >>= 2;
  i -= 2;
  return (int)(p2 >>= i/2);
}

public static int squareLowerThan( int n ){
  int p = pcomp(n);
  int p2 = p*p;     // biggest power of two that is a square < n 
  int d = 1;        // increase using odd numbers until n is exceeded
  while( p2 + 2*p + d < n ){
    p2 += 2*p + d;
    d += 2;
  }
  return p2;
}

But I'm sure that Newton's algorithm is faster. Quadratic convergence, remember.

public static int sqrt( int n ){
  int x = n;
  while( true ){
    int y = (x + n/x)/2;
    if( y >= x ) return x;
    x = y;
  }
}

This returns the integer square root. return x*x to get the square below n.