Does a range of integers contain at least one perfect square?
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) 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 (ba-1)^2 >= 4*a, or if you want it in a more symmetric form, that (ab)^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.
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.
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 .
上一篇: 确定数字是否是斐波那契数
下一篇: 一系列整数是否包含至少一个完美正方形？