Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

To check if a natural number is a perfect square, programming in Python, I check if int(math.sqrt(n))==math.sqrt(n), id est if the decimal part of the square root is zero.

Here my question: are there cases such that this test could fail due to approximation error?

Here what I get thinking by myself. The test above will fail if $n$ has a square root of the form $$b_1 b_2...b_n,000...000a_1a_2...$$ with enough zeros such that the decimal part is smaller than the minimum representable number.

By hypothesis $$n=(b_1 b_2...b_n,000...000a_1a_2...)^2 = (b_1 b_2...b_n+0,000...000a_1a_2...)^2 =$$ $$= (b_1 b_2...b_n)^2+2(b_1 b_2...b_n \times 0,000...000a_1a_2...)+ (0,000...000a_1a_2...)^2$$

It follows that there's a positive integer $m$ such that $m=2(b_1 b_2...b_n \times 0,000...000a_1a_2...)+ (0,000...000a_1a_2...)^2$.

It is not clear to me if a positive integer $n$ with such $a_1a_2...$ and $b_1...b_n$ could exist. Any idea?

share|improve this question
2  
As Henning points out in his answer, you'll get into trouble with this approach long before only the fractional part by itself becomes unrepresentable. A better test would be to round the square root to the nearest integer, square it and check whether you recover the original number. (Of course the problem only occurs and the solution only works if you have at least 64-bit integers.) –  joriki Jan 1 '12 at 18:55

1 Answer 1

up vote 2 down vote accepted

The critical question is not whether the fractional part of the square root can be represented by itself, but if the square root including the fractional part can be represented without rounding to an integer. (Recall that the absolute distance between representable numbers increase when the numbers themselves get bigger).

Back-of-the-envelope estimate: An IEEE-754 double has 53 bits of precision, so trouble should arise when the square root is strictly between $n$ and $n(1+2^{-53})$ for some whole $n$. The first trouble would show at the high end of this interval, so let's assume the true square root is $n(1+2^{-53})$. Then the square is $n^2(1+2^{-52}+2^{-106})$, which can be an integer greater than $n^2$ if $n^2\ge {\approx}2^{52}$.

So we should expect trouble to start only when the prospective square is at the limit of what the floating-point format can represent exactly as an integer anyway.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.