Take the 2-minute tour ×

Given two integers a and b, is there an efficient way to test whether there is another integer n such that a ≤ n2 < b?

I do not need to know n, only whether at least one such n exists or not, so I hope to avoid computing square roots of any numbers in the interval.

Although testing whether an individual integer is a perfect square is faster than computing the square root, the range may be large and I would also prefer to avoid performing this test for every number within the range.


  • intervalContainsSquare(2, 3) => false
  • intervalContainsSquare(5, 9) => false (note: 9 is outside this interval)
  • intervalContainsSquare(9, 9) => false (this interval is empty)
  • intervalContainsSquare(4, 9) => true (4 is inside this interval)
  • intervalContainsSquare(5, 16) => true (9 is inside this interval)
  • intervalContainsSquare(1, 10) => true (1, 4 and 9 are all inside this interval)
share|improve this question
Your third example is incorrect if a <= n^2 < b, because the interval includes the lower bound. Either change the definition to a < n^2 < b or modify the third example. –  duffymo Jun 29 '10 at 12:28
@duffymo: but n^2 < b part is violated, as 9 is not less than 9. –  Amadan Jun 29 '10 at 12:35
Fair enough, I agree. –  duffymo Jun 29 '10 at 12:35
@Amadan: a ≤ n² < b is equivalent to (a ≤ n²) ∧ (n² < b). The logical and operator returns false an soon as any of the operands is false. –  Andreas Rejbrand Jun 29 '10 at 12:45
add comment

9 Answers

up vote 25 down vote accepted

Computing whether or not a number is a square isn't really faster than computing its square root in hard cases, as far as I know. What is true is that you can do a precomputation to know that it isn't a square, which might save you time on average.

Likewise for this problem, you can do a precomputation to determine that sqrt(b)-sqrt(a) >= 1, which then means that a and b are far enough apart that there must be a square between them. With some algebra, this inequality is equivalent to the condition that (b-a-1)^2 >= 4*a, or if you want it in a more symmetric form, that (a-b)^2+1 >= 2*(a+b). So this precomputation can be done with no square roots, only with one integer product and some additions and subtractions.

If a and b are almost exactly the same, then you can still use the trick of looking at low order binary digits as a precomputation to know that there isn't a square between them. But they have to be so close together that this precomputation might not be worth it.

If these precomputations are inconclusive, then I can't think of anything other than everyone else's solution, a <= ceil(sqrt(a))^2 < b.

Since there was a question of doing the algebra right:

sqrt(b)-sqrt(a) >= 1
sqrt(b) >= 1+sqrt(a)
b >= 1+2*sqrt(a)+a
b-a-1 >= 2*sqrt(a)

Also: Generally when a is a large number, you would compute sqrt(a) with Newton's method, or with a lookup table followed by a few Newton's method steps. It is faster in principle to compute ceil(sqrt(a)) than sqrt(a), because the floating point arithmetic can be simplified to integer arithmetic, and because you don't need as many Newton's method steps to nail down high precision that you're just going to throw away. But in practice, a numerical library function can be much faster if it uses square roots implemented in microcode. If for whatever reason you don't have that microcode to help you, then it might be worth it to hand-code ceil(sqrt(a)). Maybe the most interesting case would be if a and b are unbounded integers (like, a thousand digits). But for ordinary-sized integers on an ordinary non-obsolete computer, you can't beat the FPU.

share|improve this answer
Yes that's the optimization I hoped would be possible. Thanks. –  finnw Jun 29 '10 at 13:39
I think you have a mistake in the algebra: it should be (b+a-1)^2>=4ab –  Eyal Schneider Jun 29 '10 at 13:50
Adam, you're misreading what I said. –  Greg Kuperberg Jun 29 '10 at 14:12
@Adam, Greg is describing quick test that can save computations. It states that if the difference is greater then 1 that implies there exists a perfect square root (and it does as then you for sure have at least one whole integer between the two squares). If the test fails (difference less then 1), then it is inconclusive - then you have to resort to more expensive methods. –  Unreason Jun 29 '10 at 15:03
@finnw, Eyal's formula is equivalent to Greg's. He squared the first line in Greg's derivation, rearranged terms, and squared again. –  brainjam Jun 29 '10 at 16:43
show 5 more comments

Get the square root of the lower number. If this is an integer then you are done. Otherwise round up and square the number. If this is less than b then it is true.

You only need to compute one square root this way.

In order to avoid a problem of when a is equal to b, you should check that first. As this case is always false.

share|improve this answer
+1 for avoiding two sqrt computations. –  Aryabhatta Jun 29 '10 at 12:59
add comment

If you will accept calculating two square roots, because of its monotonicity you have this inequality which is equivalent to your starting one:

sqrt(a) <= n < sqrt(b)

thus, if floor(sqrt(a)) != floor(sqrt(b)), floor(sqrt(b)) - 1 is guaranteed to be such an n.

share|improve this answer
Not exactly. Your condition on 6,9 returns true, which is incorrect. Note that b is not inclusive, so maybe you should check against b-1. –  Eyal Schneider Jun 29 '10 at 12:37
And there are cases when floor(sqrt(a)) = floor(sqrt(b))-1 (eg [5,10)) when there is such an n, so this answer is incomplete. –  Aryabhatta Jun 29 '10 at 12:39
@Moron: What I meant is: floor(sqrt(a)) != floor(sqrt(b-1)). It will return true for 5,10. –  Eyal Schneider Jun 29 '10 at 12:42
@Eyal: I wasn't refuting your comment :-). I saw your comment only after I posted mine. –  Aryabhatta Jun 29 '10 at 12:46
@Moron: I see. And by the way, extreme cases (b-1<=a) should also be handled. –  Eyal Schneider Jun 29 '10 at 12:49
show 1 more comment
  1. get the square root of the lower number and round it up
  2. get the square root of the higher number and round it down
  3. if 1 is lower or equal 2, there will be a perfect square
share|improve this answer
add comment

Find the integral part of sqrt(a) and sqrt(b), say sa and sb.

If sa2 = a, then output yes.

If sb2 = b and sa = sb-1, then output no.

If sa < sb output yes.

Else output no.

You can optimize the above to get rid of the computation of sqrt(b) (similar to JDunkerly's answer).

Or did you want to avoid computing square roots of a and b too?

You can avoid computing square roots completely by using a method similar to binary search.

You start with a guess for n, n = 1 and compute n2

Consider if a <= n < b, you can stop.

If n < a < b, you double your guess n. if a < b < n, you make it close to average of current + previous guess.

This will be O(logb) time.

share|improve this answer
Yes it would be better if I can avoid square roots completely –  finnw Jun 29 '10 at 12:40
@finnw: You can compute the integral part of a and b using binary search, in O(log a) and O(log b) time, if that works for you. This has only integer multiplications and you can avoid floating point and btw, the stackoverflow question you linked to, seems to provide a fast method for finding that too. –  Aryabhatta Jun 29 '10 at 12:41
add comment

In addition to JDunkerley's nice solution (+1), there could be a possible improvement that needs to be tested and uses integer square roots to calculate integer square roots

share|improve this answer
add comment

A Java implementation based on Greg Kuperberg's and JDunkerley's answers:

boolean intervalContainsSquare(int a, int b) {
    a = Math.max(0, a);
    if (a >= b) {
        return false;
    } else if ((a-b)*(a-b)+1 > 2*(a+b)) {
        return true;
    } else {
        int ra = (int) Math.ceil(Math.sqrt(a));
        return ra * ra < b;


Someone suggested there was an error in Greg's algebra, but here's why I am convinced it is correct:

Assume a ≤ b and there is not a perfect square within the interval.

Let be the largest square that is less than a.
(p+1)² must be the smallest square that is not less than b

also (p+1)² = p² + 2p + 1
=> (p+1)² - p² = 2p + 1

Since a > p² and b ≤ (p+1)², b - a < (p+1)² - p²
=> b - a < 2p + 1
=> b - a - 1 < 2p
=> (b - a - 1)² < 4p²
=> (b - a - 1)² / 4 < p² < a
=> (b - a - 1)² < 4a

So if 4a ≤ (b - a - 1)², this would contradict our assumption that there is no a ≤ n² < b and we can return true.

share|improve this answer
add comment

Why are you hoping to avoid square roots entirely? Even before you get to the most efficient way of solving this, you have seen methods that call for only 2 square roots. That's done in O(1) time, so it seems to me that any improvement you could hope to make would take more time to think about than it would EVER save you computing time. Am I wrong?

share|improve this answer
It is possible with only one square root. –  finnw Jun 29 '10 at 15:08
I acknowledged as much, finnw, my point was that to my understanding of computing time complexity, the difference between one and two square roots is really trivial. Computing every square root between A and B gets the problem solved in O(N) time. But computing two square roots is O(1), and computing one is O(1) too. It sounds like there's an attempt to do so with no square roots, which would be O(1), which we've already achieved, so who cares, except in the academic sense? I don't mean this as rhetorical or inflammatory, I want to know if I'm missing something. –  malenkylizards Jun 29 '10 at 15:43
add comment

One way is to use Newton's method to find the integer square root for b. Then you can check if that number falls in the range. I doubt that it is faster than simply calling the square root function, but it is certainly more interesting:

int main( int argc, char* argv[] )
    int a, b;
    double xk=0, xk1;
    int root;
    int iter=0;
    a = atoi( argv[1] );
    b = atoi( argv[2] );

    xk1 = b / 32 + 1;  // +1 to ensure > 0
    xk1 = b;
    while( fabs( xk1 - xk ) >= .5 ) {
        xk = xk1;
        xk1 = ( xk + b / xk ) / 2.;
        printf( "%d) xk = %f\n", ++iter, xk1 );

    root = (int)xk1;

    // If b is a perfect square, then this finds that root, so it also
    // needs to check if (n-1)^2 falls in the range.
    // And this does a lot more multiplications than it needs
    if ( root*root >= a && root*root < b ||
         (root-1)*(root-1) >= a && (root-1)*(root-1) < b )
        printf( "Contains perfect square\n" );
        printf( "Does not contain perfect square\n" );

    return 1;
share|improve this answer
I had the same idea, but no code and while on code, two notes. First, the stop condition should be > 0.5 according to wikipedia article. Secondly, initial guess for xk1 can speed up algorithm from 7-8 iterations to 3. Finally, I think newton approximation still holds if you use integers and integer operations for xk1 and xk. –  Unreason Jun 29 '10 at 14:49
Unreason, Thanks. I fixed the stopping condition and attempted a better starting point (probably could still use a better guess). –  Mark Wilkins Jun 29 '10 at 15:30
add comment

Your Answer


