CODEWITHSUNDEEP
c++math
gsdf
gsdf

Reputation: 285

Check if an integer has an integer cube root

I am writing a program which checks if a given number has a integer cube root. Here is my code:

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

int main(int argc, char const *argv[])
{
  double m;
  int c=0;
  int i;
  for(i=2;i<=1000000;i++)
  { 
    m = pow(i,(1./3.));
    if(m-(int)m == 0)
    {
      c++;
    }
  }
  cout<<c<<endl;
}

Here c stores the number of numbers which have a integer cube root. The problem with my code is that it always gives two as the answer while answer should be greater than two as there are many numbers like 8,64,27,...

I want to know why I get the result as two. I am not able to catch the bug!

Upvotes: 1

Views: 687

Answers (3)

n0dus
n0dus

Reputation: 155

If your number to check is small (e.g. <10,000,000) and you need the check for many numbers I would recommend to use an algorithm similar to the Sieve of Eratosthenes:

Create a boolean array for all numbers from 0 to your max number, then mark all numbers therein that are in fact cubes of a smaller integer number. You avoid using costly pow, root, even float functions at all.

#include <iostream>

void int_cubes(int num)
{
    bool cubes[num]={false};
    for(int m=2; ; ++m)
    {
        int i=m*m*m;
        if(i<num) cubes[i]=true;
        else break;
    }
    size_t c=0;
    for(size_t i=0; i<num; ++i)
    {
        if(cubes[i]) c++;
    }
    std::cout<<"Overall number: "<<c<<"\n";
}


int main(int argc, char **argv)
{
    int_cubes(atoi(argv[1]));
    
    return 0;
}

Further, this approach has the advantage that you can keep the array for later reference if you like.

Upvotes: 0

vsoftco
vsoftco

Reputation: 56567

You can also do (although I'd just cube the number from the very beginning) something like

#include <iostream>
#include <cmath>

int main(int argc, char const *argv[])
{
    int c = 0;
    for (int i = 2; i <= 1000000; i++)
    {
        int m = std::round(std::pow(i, 1. / 3));
        if (std::round(std::pow(m, 3)) == i) // use std::round to be super safe
            c++;
    }
    std::cout << c << std::endl;
}

PS: note that I used std::round(std::pow(m,3)) as it is possible (and horrible) for std::pow to give you an incorrect result, even if your base and argument are integers, see

std::pow with integer parameters, comparing to an integer type

Upvotes: 2

M.M
M.M

Reputation: 141628

What's happening is a rounding error. Since 1/3 is not exactly representable in IEEE754, you get an approximation which is slightly less than one third.

Then when you calculate, for example, pow(216, 1./3.) the result is 5.9999999999999991118 . So when you do m - (int)m , you get 0.9999999999999991118 which is not equal to zero and so your test fails.

The only two cases that your code found were the two smallest cubes (2 and 3) for which this error was so small that it still compared equal to zero.

To see the full precision of the result of your calculations, you can send << setprecision(20) to cout. (You may need #include <iomanip> for this).

To fix this, you need to do two things:

  • replace m - (int)m with m - round(m) or similar
  • Check for the number being very close to 0, instead of exactly 0.

See this question for discussion of the second part. This works for me for small cases:

abs(m - round(m)) < 0.000001

however you may need to think about the magnitude of this epsilon value for larger numbers. It's possible that this method actually won't work in general because maybe there is never an epsilon that's small enough to weed out false positives but big enough to catch all genuine cases.

Another improvement would be to use the standard cbrt function instead of this pow.

Upvotes: 6

Related Questions