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.

nearly identical to http://stackoverflow.com/questions/4930307/fastest-way-to-get-the-integer-part-of-sqrtn — hatchet - done with SOverflow, Feb 07 '15 at 18:08
@hatchet No, the point is I *dont* want the integer part of it. I want to go directly to the square number. — David says Reinstate Monica, Feb 07 '15 at 18:09
Need to s/smaller than n/not larger than n/g to make your code correct. — David Eisenstat, Feb 07 '15 at 18:12
find the integer square root (using an efficient integer square root algorithm, not Math's floating point sqrt), then square that, and you have what you are looking for. — hatchet - done with SOverflow, Feb 07 '15 at 18:12
@hatchet Did you even read my question? Thats exactly what I have **already** done. I'm asking for something different. — David says Reinstate Monica, Feb 07 '15 at 18:15
@Deduplicator It looks sketchy, but the int->double conversion is exact, and Math.sqrt is guaranteed to be correctly rounded, so one can do the error analysis to show that we never round correctly *up* to an integer (which is the only way the truncation can go wrong). — David Eisenstat, Feb 07 '15 at 18:15
@DavidGrinberg - There is a difference between integer square root in the question I linked to and the floating point square root used in your question. — hatchet - done with SOverflow, Feb 07 '15 at 18:18
Fibonacci search in a lookup table? (there are only 2^16 squares for a 32-bit int) Although sqrt isn't _that_ slow. — The Archetypal Paul, Feb 07 '15 at 18:32
what is the context? If you're trying to find a limit for a loop, you might be better off testing `i * i < n` as your loop termination, rather than `i < precalculated_square_root`. Otherwise, on modern hardware, floating square root is probably as fast as you will get. — rici, Feb 07 '15 at 19:57

laune · Accepted Answer · 2015-02-07T19:02:43.807

3

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.

edited Feb 07 '15 at 19:02

answered Feb 07 '15 at 18:24

laune

31,114
3
29
42

Would this be faster than a native implementation of square root? – Andy Turner Feb 07 '15 at 18:42
@AndyTurner Using double? With a processor having sqrt as an instruction or on some other crutch? Perhaps yes maybe no. :) - However, integer arithmetic is faster, all other things being equal. – laune Feb 07 '15 at 18:50
1

@laune: benchmarks or it's just an anecdote. integer arithmetic uses fewer gates, but it is not intrinsically faster if you've got enough chip real estate. In fact, on modern processors, a floating point divide may well be faster than an integer divide. – rici Feb 07 '15 at 19:55
@rici Still, the term "integer arithmetic" should not be understood in terms of raw CPU instruction timing: numerical algorithms in floating point tend to need more code, e.g., for deciding when to stop an iteration, or for the conversions to/from string. Also, certain optimizations can only be done in integer arithmetic, e.g., i/2 vs. f/2.0, or i++ vs. f+1.0. Shorter code, less cache lines... But when (as here) a single FP instruction does most of the job, all alternatives can be left aside. – laune Feb 08 '15 at 08:12

score 2 · Answer 2 · answered Feb 07 '15 at 18:10

2

A linear-time algorithm:

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

answered Feb 07 '15 at 18:10

Andy Turner

137,514
11
162
243

3

I would be very surprised if this is faster than finding the square root. – David says Reinstate Monica Feb 07 '15 at 18:11
Me too. But you said you don't want to use the square root. Not using square root feels like a micro-optimization. – Andy Turner Feb 07 '15 at 18:12
It absolutely is a micro-optimization. That is what Im asking for. This is not an optimization at all though – David says Reinstate Monica Feb 07 '15 at 18:16
What are you trying to optimize for? e.g. a lookup table of the results is pretty efficient in terms of time, but it's crappy for storage. – Andy Turner Feb 07 '15 at 18:19

score 2 · Answer 3 · edited Apr 13 '17 at 12:19

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

Algorithm to find the largest square number smaller than n

3 Answers3