Does a range of integers contain at least one perfect square?

Question

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.

Examples:

• 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)

Answer 1

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

If sa² = a, then output yes.

If sb² = 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 n²

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.

Answer 2

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.

Answer 3

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

Answer 4

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.

Answer 5

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)
(b-a-1)^2 >= 4*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.

Answer 6

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" );
    else
        printf( "Does not contain perfect square\n" );

    return 1;
}

Answer 7

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;
    }
}

Update

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 n² within the interval.

Let p² 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.

Answer 8

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

Answer 9

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?