Thread: Checking for integer after square root

Here is a simple method:

Code:

/*root be the variable containing square root*/
Check for this condition:

if(root-(int)root==0)
  ...it is an integer value
else
   ...it is not

No, logicwonder's method is unsafe, because floating points are imprecise. grumpy got it right.

And what do you think about this solution:

Code:

#include <iostream>
#include <cmath>
using namespace std;

int main ( ) 
{
	double d = 256.2;
	double s = sqrt ( d );

	int x = ( int ) s ;

	if ( fmod ( s, ( int ) s ) == 0 )
	{
		cout << "Integer!";
	}
	return 0;
}

- Micko

It might work (not sure what exactly fmod does), but what for? Grumpy's version is fine, simple, and nearly guaranteed to work. To make it safe, the integer conversion line must be modified like so:

Code:

int root_i = (int)(x + 0.5);

Otherwise, x might be just below the actual integer value, and the resulting downrounding makes it incorrect.

Originally Posted by CornedBee

It might work (not sure what exactly fmod does), but what for? Grumpy's version is fine, simple, and nearly guaranteed to work. To make it safe, the integer conversion line must be modified like so:

Code:

int root_i = (int)(x + 0.5);

Otherwise, x might be just below the actual integer value, and the resulting downrounding makes it incorrect.

Ok, Grumpy's solution is fine.
I'm not sure why you need to do this:

Code:

int root_i = (int)(x + 0.5);

I didn't quite understand...
You have floor and ceil functions from cmath but don't know in which case ...+0.5 is needed...

Floating point numbers are imprecise, and square root algorithms only deliver approximations. It is well possible that, say, sqrt(1000000.0) doesn't return exactly 1000.0, but, say, 1000.0001 or perhaps 999.9999. The first is not a problem, because converting it to an integer will still yield 1000. However, integer conversion always rounds toward zero, no matter how small the difference is; thus, 999.9999 will yield 999 when converted to an integer. 999*999 is not 1000000, so the test will incorrectly fail. Adding 0.5 to the result ensures that the result will be correct either way. (The error will not go beyond 0.5 until the numbers become very large - probably too large for an integer anyway.)

A less elegant, yet highly precise solution would have you simply convert the resultant value to a string and analyze that.

Code:

bool is_sqrt_int(double your_value) {
  std::ostringstream ostr;
  ostr << square_root_of(your_value);
  return ostr.str().find(".") == std::string::npos;
}

[edit]
As far as calculating the square root is concerned, I prefer Newton's iteration:

Code:

result = 1

for i = 1 to N
  result = (result + (value / result)) / 2

where N is the number of iterations you'd like. (The more iterations, the more precise the value, but I find just a few to be enough. Experiment yourself.)
[/edit]

Except if the global locale was replaced by a German one, which would cause the stream to output 123.456 as "123,456".

Originally Posted by CornedBee

Except if the global locale was replaced by a German one, which would cause the stream to output 123.456 as "123,456".

Search the string for the current locale's integer and decimal separator. (You're splitting hairs, CornedBeef. In a real situation that might present a serious concern, but our friend is surely authoring a small program where he knows what his decimal character is.)

[edit]
Of course, you could always simply check the string for a non-numeric, non-sign character.

Code:

return ostr.str().find_first_not_of("-+0123456789") == std::string::npos;

[/edit]

Originally Posted by CornedBee

No, logicwonder's method is unsafe, because floating points are imprecise. grumpy got it right.

No, logicwonder's method is just as safe as grumpy's. Grumpy uses floating point numbers, too. (Both will work correctly; a double can hold unsigned integers exactly up to about 52 bits.)

Originally Posted by CornedBee

It is well possible that, say, sqrt(1000000.0) doesn't return exactly 1000.0, but, say, 1000.0001 or perhaps 999.9999.

If you're using a 32-bit or 64-bit IEEE representation, this will only happen if the square root implementation is broken. If you're paranoid about broken implementations, then rounding works, though.

[edit]If you increase your number to, say, 32 million, then you'll get problems. You end up getting false positives, not false negatives.