Sign in to follow this  
RedRabbit

Perfect squares

Recommended Posts

Hey all, I have a program due in one of my classes in 2 days and I have a problem. I understand what a perfect square is and how to check for it mathematically but how can you check to see if the result of a square in C++ is an integer value? Thanks for the help :)

Share this post


Link to post
Share on other sites
int i = static_cast<int>(std::sqrt(x));
bool omg_you_should_really_learn_to_think_by_yourself_omg = (i*i == x);

Share this post


Link to post
Share on other sites
This one also works with numbers larger than 2^31
bool is_square(double x){
if(x<0)
return false;
double i = std::floor(std::sqrt(x)+.5);
return i*i==x;
}



Share this post


Link to post
Share on other sites
Surely the +0.5 isn't necessary in this case, since you're just checking for integerness instead of rounding? I know it's the standard reflex in a floored argument ;).

I think you can also do return ((sqrt(x)+epsilon)%1.0)<(2*epsilon) – epsilon being a suitable small constant to allow for floating-point arithmetic to 'miss' slightly.

Share this post


Link to post
Share on other sites
Quote:
Original post by Bob Janova
Surely the +0.5 isn't necessary in this case, since you're just checking for integerness instead of rounding? I know it's the standard reflex in a floored argument ;).

Well, it's a matter of robustness. It could be the case that on some system sqrt(49) is 6.999999999999999934, and then floor would convert that to 6. If you don't want to make assumptions on the type of errors that floating-point functions have, rounding is safer than flooring.

Here's an interesting alternative. Invoke this with any unsigned integer type. It might work with doubles too, but I haven't thought too much about it.
#include <climits>

template <typename U>
bool is_square(U x){
const int num_bits = CHAR_BIT*sizeof(U)/2;
U base=U(1)<<(num_bits-1);
U y=0;
for (int i=0; i<num_bits; ++i){
y+=base;
if(y*y>x)
y-=base;
base>>=1;
}
return y*y==x;
}



Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this