CODEWITHSUNDEEP
c++c++17
Vedanta Mohapatra
Vedanta Mohapatra

Reputation: 510

Issues with the sqrt() function in C++

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.

Upvotes: 4

Views: 1850

Answers (3)

Gene
Gene

Reputation: 46960

Here is Knuth's very interesting algorithm for computing integer square roots with only shift and add. It rounds down for non-square inputs.

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

This works by trying to set each bit to 1, high to low, maintaining the square of the prospective root computed so far. Each bit is "or"ed into the result if doing so produces a square no greater than the input value. It can be modified to detect the case where the prospect is an exact square.

bool is_exact_square(uint32_t x) {
  if (x == 0) return true;
  uint32_t r = 0, r2 = 0; 
  for (int p = 15; p >= 0; --p) {
    uint32_t tr2 = r2 + (r << (p + 1)) + (1u << (p << 1));
    if (tr2 == x) return true;
    if (tr2 < x) {
      r2 = tr2;
      r |= (1u << p);
    }
  }
  return false;
}

I'm adding the for general interest. The binary search suggestion is good. Maybe better unless you're working on a machine without fast multiply.

Upvotes: 4

selbie
selbie

Reputation: 104524

sqrt, on many systems returns an approximation.

For example, 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 long t)
{
    bool result = false;
    if ((t == 0) || (t == 1)) {
        return true;
    }
    if (t < 0) {
        return false;
    }

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

    while (low < high)
    {
        auto mid = (high + low) / 2;
        auto sq = mid * mid;
        if (sq == t) {
            result = true;
            break;
        }
        if (sq < t) {
            low = mid + 1;
        }
        else {
            high = mid - 1;
        }
    }
    return result;
}

Upvotes: 4

John Zwinck
John Zwinck

Reputation: 249153

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));

Upvotes: 5

Related Questions