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

There is a newton algorithm to find square root, what you need is m^2 instead of m, in the given link

https://math.stackexchange.com/questions/34235/algorithm-for-computing-square-root-of-a-perfect-square-integer

Even if you want to find square directly instead of finding m, I don't think it will be faster than this.

And working code here

public static int squareLessThanN(int N)
{
        int x=N;
        int y=(x+N/x)/2;
        while(y<x)
        {
               x=y;
               y=(x+N/x)/2;
        }
        return x*x;
 }

But it seems inbuilt square root seems to be faster anyway. Just measured the runtime for both.

class Square{
        public static void main(String[] args)
        {
                long startTime = System.currentTimeMillis();
                System.out.println(squareLessThanN(149899437943L));
                long endTime   = System.currentTimeMillis();
                long totalTime = endTime - startTime;
                System.out.println("Running time is "+totalTime);

                startTime = System.currentTimeMillis();
                System.out.println(normal(149899437943L));
                endTime   = System.currentTimeMillis();
                totalTime = endTime - startTime;
                System.out.println("Running time is "+totalTime);

        }
        public static long squareLessThanN(long N)
        {
                long x=N;
                long y=(x+N/x)/2;
                while(y<x)
                {
                        x=y;
                        y=(x+N/x)/2;
                }
                return x*x;
        }
        public static long normal(long N)
        {
                long square = (long)Math.sqrt(N);
                return square*square;
        }
}

And the output is

149899060224
Running time is 1
149899060224
Running time is 0

Answer 2

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.

Answer 3

A linear-time algorithm:

int largestSquare(int n) {
  int i = 0;
  while ((i+1)*(i+1) < n) {
    ++i;
  }
  return i*i;
}