Issues with the sqrt() function in C-CodePudding

So, I was writing code in C , which required an intermediate step to check whether a number was a perfect square. I wrote the following code.

int sqrt_of_t = (int)sqrt(t);
if (sqrt_of_t*sqrt_of_t != t)
{
    cout << "NO" << endl;
}

This code gives the correct results in my system, but it fails when passing it through an online judge in Codeforces. The case where it fails doesn't have any overflow associated with it or anything (really small test cases). So, can anyone explain where it went wrong and suggest some alternate method to check if a number is a perfect square or not, which will work on all systems and not show behaviors like this. Here t is an int too.

CodePudding user response：

sqrt() returns a floating point number which you cast to int, which truncates any fractional part. The problem is that floating point cannot represent all integers exactly, so you may end up with something like 19.99999999999999 which you expect to be 20 but is actually 19 when cast to an integer.

To fix it, use rounding instead:

long sqrt_of_t = lrint(sqrt(t));

CodePudding user response：

sqrt, on many systems returns an estimate.

sqrt(25) might return something like 4.99999999.

Hence, 4.99999999 * 4.99999999 is slightly less than 25.

My advice would be to do a binary search across the number space to see if the number is a perfect square. Avoid floating point whenever you need precise results.

bool isPerfectSquare(long t)
{
    if ((t == 0) || (t == 1)) {
        return true;
    }
    if (t < 0) {
       return false;
    }

    long low = 1; 
    long high = t/2;

    while (low < high)
    {
        int mid = (low high)/2;
        long sq = mid*mid;
        if (sq == t) {
            return true;
        }
        if (sq < t) {
           low = mid   1;
        }
        else {
           high = mid - 1;
        }
    }
}

CodePudding user response：

Here is Knuth's very interesting algorithm for computing integer square roots with only shift and add. It assumes 32-bit ints and rounds down for non-square inputs. I'm adding it for general interest. The binary search suggestion is good. Probably better.

unsigned isqrt1(unsigned x) {
  unsigned r = 0, r2 = 0; 
  for (int p = 15; p >= 0; --p) {
    unsigned tr2 = r2   (r << (p   1))   (1u << (p << 1));
    if (tr2 <= x) {
      r2 = tr2;
      r |= (1u << p);
    }
  }
  return r;
}