Checking for integer after square root

This is a discussion on Checking for integer after square root within the C++ Programming forums, part of the General Programming Boards category; Hi, its seems like a simple problem but i can't seem to find any simple C/C++ tools to help me ...

  1. #1
    Registered User Boomba's Avatar
    Join Date
    Jun 2003
    Posts
    89

    Exclamation Checking for integer after square root

    Hi,
    its seems like a simple problem but i can't seem to find any simple C/C++ tools to help me with what i'm looking for...

    I have a long variable, I wanna take the square root of that long variable and then I want to check if the result of the square root is an integer (has no decimal values).

    any thoughts?

    thanks in advance
    Boomba,

  2. #2
    Registered User
    Join Date
    Jun 2005
    Posts
    6,251
    Code:
    int i = some_positive_value();
    double x = sqrt((double)i);
    int root_i = (int)x;
    if (root_i *root_i == i) square_root_is_integer();
    If you want to do away with working with floating point values (which also introduces some potential for rounding errors to mess things up), you need to use a loop;
    Code:
    /*  assume i is > 0 */
    int root_i = 0;
    while (root_i * root_i < i)  ++root_i;
    /*   root_i will be an integer that is not less than the square root of i */
    if (root_i * root_i == i) square_root_is_integer();

  3. #3
    Logic Programmer logicwonder's Avatar
    Join Date
    Nov 2005
    Location
    Kerala, India
    Posts
    52
    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
    L GIK wins!!!
    Salutes from logicwonder
    Enjoy programming

  4. #4
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    No, logicwonder's method is unsafe, because floating points are imprecise. grumpy got it right.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  5. #5
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    712
    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
    Gotta love the "please fix this for me, but I'm not going to tell you which functions we're allowed to use" posts.
    It's like teaching people to walk by first breaking their legs - muppet teachers! - Salem

  6. #6
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    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.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  7. #7
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    712
    Quote 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...
    Gotta love the "please fix this for me, but I'm not going to tell you which functions we're allowed to use" posts.
    It's like teaching people to walk by first breaking their legs - muppet teachers! - Salem

  8. #8
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    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.)
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  9. #9
    Magically delicious LuckY's Avatar
    Join Date
    Oct 2001
    Posts
    856
    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]
    Last edited by LuckY; 01-04-2006 at 02:52 PM.

  10. #10
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    Except if the global locale was replaced by a German one, which would cause the stream to output 123.456 as "123,456".
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  11. #11
    Magically delicious LuckY's Avatar
    Join Date
    Oct 2001
    Posts
    856
    Quote 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]
    Last edited by LuckY; 01-04-2006 at 02:58 PM.

  12. #12
    ^ Read Backwards^
    Join Date
    Sep 2005
    Location
    Earth
    Posts
    282
    I use this all the time:

    Code:
    bool is_int(double value)
    {
    	if ( (value / static_cast<int>(value)) == 1) return true;
    	else return false;
    
    }
    I have never come across any rounding errors with it, but I suppose it is possible. It is just simple and worked for everything I needed it with.

  13. #13
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    Quote 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.)

    Quote 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.
    Last edited by Rashakil Fol; 01-04-2006 at 05:36 PM.

  14. #14
    Registered User
    Join Date
    Jun 2005
    Posts
    6,251
    Quote Originally Posted by Rashakil Fol
    No, logicwonder's method is just as safe as grumpy's. Grumpy uses floating point numbers, too. (Both will work correctly;
    Actually, I provided two methods. One of them used floating point variables, and is just as safe (or unsafe) as logicwonder's method. The other method used purely integer arithmetic, and does not have the potential for errors due to lack of precision in floating point.
    Quote Originally Posted by Rashakil Fol
    a double can hold unsigned integers exactly up to about 52 bits.)
    That's not required to be true. It just happens to be true for some common floating point representations.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Profiler Valgrind
    By afflictedd2 in forum C++ Programming
    Replies: 4
    Last Post: 07-18-2008, 09:38 AM
  2. Forced moves trouble!!
    By Zishaan in forum Game Programming
    Replies: 0
    Last Post: 03-27-2007, 06:57 PM
  3. Bisection Method function value at root incorrect
    By mr_glass in forum C Programming
    Replies: 3
    Last Post: 11-10-2005, 08:10 AM
  4. Problems about gcc installation
    By kevin_cat in forum Linux Programming
    Replies: 4
    Last Post: 08-09-2005, 09:05 AM
  5. Templated Binary Tree... dear god...
    By Nakeerb in forum C++ Programming
    Replies: 15
    Last Post: 01-17-2003, 01:24 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21