Can I rely on this to judge a square number in C++?

Question

Can I rely on

sqrt((float)a)*sqrt((float)a)==a

or

(int)sqrt((float)a)*(int)sqrt((float)a)==a

to check whether a number is a perfect square? Why or why not?
int a is the number to be judged. I'm using Visual Studio 2005.

Edit: Thanks for all these rapid answers. I see that I can't rely on float type comparison. (If I wrote as above, will the last a be cast to float implicitly?) If I do it like

(int)sqrt((float)a)*(int)sqrt((float)a) - a < e  

How small should I take that e value?

Edit2: Hey, why don't we leave the comparison part aside, and decide whether the (int) is necessary? As I see, with it, the difference might be great for squares; but without it, the difference might be small for non-squares. Perhaps neither will do. :-(

Stewardson

Presumably a is an int, but could you confirm that? – Unwrap

What's with everyone being downvoted? – Fairtrade

phoenie, for all practical purposes anything less than 0.1 or so should work since you're basically comparing values that will be approximately equal to integers - any other integer input would result in an output approximately the integer difference of the squares away. – Ordure

e will be minimum of |f'(x)|-|(f(x)-f(x+h))/h| as h->0 – Larrigan

use natural logarithms - much more precise – Sob

the only problem with the function you typed above (the second one) is that you calc the float twice. Like my example (somewhere below), you only need to calculate it once – Blackmon

See also #296079 – Attitudinize

Answer 1

Actually, this is not a C++, but a math question.

1. With floating point numbers, you should never rely on equality. Where you would test a == b, just test against abs(a - b) < eps, where eps is a small number (e.g. 1E-6) that you would treat as a good enough approximation.
2. If the number you are testing is an integer, you might be interested in the Wikipedia article about Integer square root

EDIT:

As Krugar said, the article I linked does not answer anything. Sure, there is no direct answer to your question there, phoenie. I just thought that the underlying problem you have is floating point precision and maybe you wanted some math background to your problem.

For the impatient, there is a link in the article to a lengthy discussion about implementing isqrt. It boils down to the code karx11erx posted in his answer.

If you have integers which do not fit into an unsigned long, you can modify the algorithm yourself.

Plasticine

The article answers nothing. Yet this is being aired as the most voted question. Go figure. – Fairtrade

Shay Erlichmen has come with a nice algorithm. Check that. – Fairtrade

Actually you just reposted my solution to the perfect square question involving integer square roots which I posted below a few hours before your did. Looks like a case of blatant plagiarism to me. >:( – Cinque

I do not fight for reputation. I just want to answer questions. I removed the code to satisfy karx11erx. – Plasticine

Answer 2

If you don't want to rely on float precision then you can use the following code that uses integer math.

The Isqrt is taken from here and is O(log n)

// Finds the integer square root of a positive number
static int Isqrt(int num)
{
    if (0 == num) { return 0; }  // Avoid zero divide
    int n = (num / 2) + 1;       // Initial estimate, never low
    int n1 = (n + (num / n)) / 2;
    while (n1 < n)
    {
        n = n1;
        n1 = (n + (num / n)) / 2;
    } // end while
    return n;
} // end Isqrt()

static bool IsPerfectSquare(int num)
{
    return Isqrt(num) * Isqrt(num) == num;
}

Eade

although nice, the float version of the squareroot would probably be done on the math processor and be much faster vs this iterative approximation. – Blackmon

reinier, What's the good of as fast implementation that doesn't work right? – Cinque

Answer 3

Your question has already been answered, but here is a working solution.

Your 'perfect squares' are implicitly integer values, so you could easily solve floating point format related accuracy problems by using some integer square root function to determine the integer square root of the value you want to test. That function will return the biggest number r for a value v where r * r <= v. Once you have r, you simply need to test whether r * r == v.

unsigned short isqrt (unsigned long a)
{
    unsigned long rem = 0;
    unsigned long root = 0;

    for (int i = 16; i; i--) {
        root <<= 1;
        rem = ((rem << 2) + (a >> 30));
        a <<= 2;
        if (root < rem)
            rem -= ++root;
    }

    return (unsigned short) (root >> 1);
}

bool PerfectSquare (unsigned long a)
{
    unsigned short r = isqrt (a);

    return r * r == a;
}

Cinque

Oops. I just read your answer after my edit adding some code. I just copied blindly the isqrt code and did not even try to optimize it further. You get an upvote from me for spending the effort spent on these optimizations. – Plasticine

Well, I posted this solution hours before you - or anybody else here - did. I am not amused by your duplicating my solution and earning all the upvotes here. The decent way to handle this would have been to remove the code you edited in as an afterthought an point to my solution. – Cinque

Your solution? At least wigy includes a reference where he copied the code from. You don't. – Shigella

I copied the isqrt code from some source code of mine that is at least 10 years old. Integer square root functions are trivial and common knowledge. The point is that I was the first to propose their usage for the perfect square problem (and that was my own idea, it's pretty trivial anyway), and your comment is pointless. – Cinque

Well, since you admit computing square roots is common knowledge you could at least remove your accusations that wigy is commiting plagiarism and apologize. Thanks – Shigella

Wigy had the decency to remove his code, so what you are doing now is pure trolling. Apparently you lack what it takes to discern between using some code from the internet and creating a solution with it. I did the latter, and wigy posted an identical solution hours later. I am not even gonna ask you to apologize, because I have met so many people like you already that I know it's a waste of time, jsut that you stuff any further stupid and misguided comments where they belong instead of continuing to present yourself as an arrogant and thougtless troll. – Cinque

-1 For going against the spirit of the site. This is about answers, not ownership. Jeff and Joel have stated that the goal should be about making your answer the best. Sometimes that means combining other user's answers into an even better one. – Novellanovello

Geez, I hadn't been visiting this site for weeks at least ... time to delete the bookmark, I guess. Anyway, what do you believe does your necro posting comment add to the spirit of this site or the usefulness of this response? Pull the tree out of your eye before pointing at the splinter in mine, judgmental little man. – Cinque

Answer 4

Not to do the same calculation twice I would do it with a temporary number:

 int b = (int)sqrt((float)a);
 if((b*b) == a)
 {
     //perfect square
 }

edit: dav made a good point. instead of relying on the cast you'll need to round off the float first

so it should be:

 int b = (int) (sqrt((float)a) + 0.5f);
 if((b*b) == a)
 {
     //perfect square
 }

Blackmon

this is blatantly wrong. if a=35, then b=5. b*b - 25, which is !=35 – Clapp

@harshath.jr And thus 35 is not a perfect square. – Conjuncture

no it isn't. A perfect square, is an integer that can be written as the square of some other integer. So you example of a=35 is NOT a perfect square, which my routine will not identify as such! – Blackmon

You can very easily run into floating-point accuracy issues with this. For instance, if a=25, and the floating point sqrt result comes back as 4.99999999, which then gets cast to int, you'd wind up with b=4. – Ordure

@reinier: okay, I agree that your point is not blatantly wrong. but it is not entirely right (ref: @Dav) – Clapp

What's the 0.5f for? Can't it be 0.6f? – Stewardson

the 0.5f is to round it off. so if the float is 4.9999f then casting it to an int would give 4. If you first add the 0.5f then the float is rounded to the nearest int (so 4.49f will yield 4, where as 4.5f will yield 5) – Blackmon

In VS2005, (int)4.5f yields 4 too. – Stewardson

thats why we add the 0.5f. so: 4.5f + 0.5f = 5.0f = 5 – Blackmon

Answer 5

I didn't follow the formula, I apologize. But you can easily check if a floating point number is an integer by casting it to an integer type and compare the result against the floating point number. So,

bool isSquare(long val) {
    double root = sqrt(val);
    if (root == (long) root)
        return true;
    else return false;
}

Naturally this is only doable if you are working with values that you know will fit within the integer type range. But being that the case, you can solve the problem this way, saving you the inherent complexity of a mathematical formula.

Fairtrade

This may not work, as the compiler might cast the left root to long before comparing it. At least this can happen when comparing float values to integer constants. You may want to do "if (root == double (long (root)))" (using C++ function style type casts here). – Cinque

Answer 6

As reinier says, you need to add 0.5 to make sure it rounds to the nearest integer, so you get

int b = (int) (sqrt((float)a) + 0.5f);
if((b*b) == a) /* perfect square */

For this to work, b has to be (exactly) equal to the square root of a if a is a perfect square. However, I don't think you can guarantee this. Suppose that int is 64 bits and float is 32 bits (I think that's allowed). Then a can be of the order 2^60, so its square root is of order 2^30. However, a float only stores 24 bits in the significand, so the rounding error is of order 2^(30-24) = 2^6. This is larger to 1, so b may contain the wrong integer. For instance, I think that the above code does not identify a = (2^30+1)^2 as a perfect square.

Skillful

Any particular reason to use float and not double? – Rasorial

I just copied reinier. If I remember correctly, I wrote this reply as a comment on reinier's, but it was too long to put in a proper comment. – Skillful

Answer 7

I would do.

// sqrt always returns positive value. So casting to int is equivalent to floor()
int down =  static_cast<int>(sqrt(value));
int up   = down+1;                           // This is the ceil(sqrt(value))

// Because of rounding problems I would test the floor() and ceil()
// of the value returned from sqrt().
if (((down*down) == value) || ((up*up) == value))
{
     // We have a winner.
}

Prithee

Nice commenting. But a rounding function is easier to follow I think than 2 different tests. – Rasorial

Answer 8

The more obvious, if slower -- O(sqrt(n)) -- way:

bool is_perfect_square(int i) {
    int d = 1;
    for (int x = 0; x <= i; x += d, d += 2) {
        if (x == i) return true;
    }
    return false;   
}

Amplify

Answer 9

While others have noted that you should not test for equality with floats, I think you are missing out on chances to take advantage of the properties of perfect squares. First there is no point in re-squaring the calculated root. If a is a perfect square then sqrt(a) is an integer and you should check:

b = sqrt((float)a)
b - floor(b) < e

where e is set sufficiently small. There are also a number of integers that you can cross of as non-square before taking the square root. Checking Wikipedia you can see some necessary conditions for a to be square:

A square number can only end with digits 00,1,4,6,9, or 25 in base 10

Another simple check would be to see that a % 4 == 1 or 0 before taking the root since:

Squares of even numbers are even, since (2n)^2 = 4n^2.
Squares of odd numbers are odd, since (2n + 1)^2 = 4(n^2 + n) + 1.

These would essentially eliminate half of the integers before taking any roots.

Tamarah

Answer 10

The cleanest solution is to use an integer sqrt routine, then do:

bool isSquare( unsigned int a ) {

  unsigned int s = isqrt( a );
  return s * s == a;

}

This will work in the full int range and with perfect precision. A few cases:

a = 0, s = 0, s * s = 0 (add an exception if you don't want to treat 0 as square)  
a = 1, s = 1, s * s = 1  
a = 2, s = 1, s * s = 1  
a = 3, s = 1, s * s = 1  
a = 4, s = 2, s * s = 4  
a = 5, s = 2, s * s = 4

Won't fail either as you approach the maximum value for your int size. E.g. for 32-bit ints:

a = 0x40000000, s = 0x00008000, s * s = 0x40000000  
a = 0xFFFFFFFF, s = 0x0000FFFF, s * s = 0xFFFE0001

Using floats you run into a number of issues. You may find that sqrt( 4 ) = 1.999999..., and similar problems, although you can round-to-nearest instead of using floor().

Worse though, a float has only 24 significant bits which means you can't cast any int larger than 2^24-1 to a float without losing precision, which introduces false positives/negatives. Using doubles for testing 32-bit ints, you should be fine, though.

But remember to cast the result of the floating-point sqrt back to an int and compare the result to the original int. Comparisons between floats are never a good idea; even for square values of x in a limited range, there is no guarantee that sqrt( x ) * sqrt( x ) == x, or that sqrt( x * x) = x.

Glasser

Gah. That looked fine in the preview. THE PREVIEW TRICKED ME! This site bites. – Glasser

Answer 11

basics first:

if you (int) a number in a calculation it will remove ALL post-comma data. If I remember my C correctly, if you have an (int) in any calculation (+/-*) it will automatically presume int for all other numbers.

So in your case you want float on every number involved, otherwise you will loose data:

sqrt((float)a)*sqrt((float)a)==(float)a

is the way you want to go

Luckey

I think he's only interested in having the result be interpretable as an int. Otherwise any number would qualify – Blackmon

A recent question showed that even sin(x)==sin(x) doesn't hold true always. Don't trust floating point comparison. – Apoenzyme

true. floating point arithmetic is built for precision, not comparision. – Clapp

Depending on the expression parser, as soon as a floating point value is involved in an expression, all child expressions are cast to floating point. – Cinque

This solution may have false positives as well as false negatives. There is no reason why for example sqrt((float)2) * sqrt((float)2) should not be equal to 2.0. – Shigella

all true... didnt think of that – Luckey

Answer 12

Floating point math is inaccurate by nature.

So consider this code:

int a=35;
float conv = (float)a;
float sqrt_a = sqrt(conv);
if( sqrt_a*sqrt_a == conv )
    printf("perfect square");

this is what will happen:

a = 35
conv = 35.000000
sqrt_a = 5.916079
sqrt_a*sqrt_a = 34.999990734

this is amply clear that sqrt_a^2 is not equal to a.

Clapp

your example of a=35 is flawed. 35 is not a perfect square. – Blackmon

I never said it was...he's simply demonstrating how innacurate it is since 35 has a square roo that is fractional. – Hagiarchy

This version has many counterexamples. For example if a is larger than 2**24 then the result of sqrt_asqrt_a has no bits after the decimal points since floats have 24 bit precision. Hence whether the test sqrt_asqrt_a == conv returns true is more or less a coincidence. – Shigella