ansaurus

Question

Answer 1

+5 A:

sqrt(x), or in general, pow(x, 1./2) or pow(x, 1./3)

For example:

int n = 9;
int a = (int) sqrt((double) n);
if(a * a == n || (a+1) * (a+1) == n)  // in case of an off-by-one float error
    cout << "It's a square!\n";

Edit: or in general:

bool is_nth_power(int a, int n) {
  if(n <= 0)
    return false;
  if(a < 0 && n % 2 == 0)
    return false;
  a = abs(a);

  int b = pow(a, 1. / n);
  return pow((double) b, n) == a || pow((double) (b+1), n) == a;
}

Jesse Beder 2009-10-11 05:41:54

The problem with using `pow(x, 1./3)` is that 1/3 does not have an exact representation in floating point, so you're not "really" getting the cube root. C99 onwards has `cbrt`, which should do a better job of getting the cube root.

Chris Jester-Young 2009-10-11 05:45:17

I suppose. But `pow` generalizes easier, and it's easy enough to correct for floating point errors.

Jesse Beder 2009-10-11 05:48:47

Answer 2

+1 A:

No, but it's easy to write one:

bool is_perfect_square(int n) {
    if (n < 0)
        return false;
    int root(round(sqrt(n)));
    return n == root * root;
}

bool is_perfect_cube(int n) {
    int root(round(cbrt(n)));
    return n == root * root * root;
}

Chris Jester-Young 2009-10-11 05:43:38

Where do you see a possible division by zero ? sqrt(0) and cbrt(0) are defined.

Pierre Bourdon 2009-10-11 05:48:19

The original answer I had in my mind used return `n / root == root`, but I ended up using a different approach. Thanks for pointing out! Will edit answer.

Chris Jester-Young 2009-10-11 05:52:23

This won't always work, due to floating-point error: if `sqrt()` or `cbrt()` happens to return epsilon less than the actual root, the cast to an integer will truncate that, and the check will fail. To be completely bullet-proof against that, you also need to check if `n == (root + 1) * (root + 1)` for the square root case or if `n == (root + 1) * (root + 1) * (root + 1)` for the cube root case.

Adam Rosenfield 2009-10-11 17:52:25

Oh god, it hurts my head. I kept looking for the "root" function until I realized you were just initializing an integer... I strongly dislike your coding style.

Mark 2009-10-11 17:53:36

@Adam: Do you have a case where an "integral" result from `sqrt` or `cbrt` would end up to be "epsilon less than the root"? Remember we're not dealing with fractions here, so (assuming that the root isn't so big that it can't be represented exactly by a floating point number, in which case we've lost already), how will this be a problem? I'm happy to use `round()` though.

Chris Jester-Young 2009-10-11 18:53:30

@Mark: You can dislike it all you want, but it's the "more-standard" initialisation style in C++; I think it's called "constructor syntax" or something like that. i.e., if you are constructing an object that, say, takes more than one constructor parameter, you'd have to use that syntax anyway. I don't like to make a special exception for numeric types, so I use constructor syntax for them too.

Chris Jester-Young 2009-10-11 18:57:10

ansaurus

tags:

views:

answers:

Perfect square and perfect cube

related questions