1

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!

Improve this question
8
  • 1
    why include <cstdio>? Commented Nov 26, 2014 at 4:18
  • 2
    Checking for equality is seldom a good idea when you work with floating point arithmetic. Instead, round the calculated root to nearest integer, then check if that is indeed a cube root. Of course this suggests a much more efficient alternative to your current design. Commented Nov 26, 2014 at 4:18
  • luu i write it every time when i write a code. cheers but what is wrong in my code? Commented Nov 26, 2014 at 4:20
  • 4
    @SurayansTiwari m - (int)m can be something like 0.00000000001 due to floating point error, even for what seem to be integer m's, and you're done. Commented Nov 26, 2014 at 4:22
  • better use multiplication rather than pow, and it's also faster because you only have to check less than 100 values Commented Nov 26, 2014 at 4:24

3 Answers 3

Reset to default
6

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

8 Comments

Re "IEEE754", there is no information that the OP's C++ implementation uses IEEE 754. I think, but I'm not sure, that C++ restricts the radix of floating point to be either 2 or 10, i.e. that 3 and multiples are not allowed, but to use that as an argument you would have to verify it via the Holy Standard.
@Alf I mean: what's happening to OP (not: what happens on all systems), it's a safe assumption he is using IEEE754
he could be sitting on an IBM mainframe.
@Cheersandhth.-Alf unless he's using some weird floating point types with base 3 (or a multiple of 3), he can never get the exact value or 1/3
@Cheersandhth.-Alf I didn't get you. IBM mainframes don't use radix 3n for floating points too
|
2

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

Improve this answer

Comments

0

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.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.