Find n-th root of all numbers within an interval

Question

I have a program which must print perfect square roots of all integer numbers within an interval. Now I want to do that for n-the root.

Here's what I've done, but I'm stuck at fmod.

#include <iostream>
#include <math.h>
using namespace std;

int nroot(int, int);

int main()
{

    int p, min, max,i;
    double q;

    cout << "enter min and max of the interval \n";
    cin >> min;
    cin >> max;
    cout << "\n Enter the n-th root \n";
    cin >> p;
    i = min;

    while (i <= max)
    {
        if (fmod((nroot(i, p)), 1.0) == 0)
        {
            cout << nroot(i, p);
        }
        i++;
    }
    return 0;
}

int nroot (int i, int p){

    float q;
    q = (pow(i, (1.0 / p)));

    return q;
}

I mean that I wanted to use fmod as a %10 to compare nroot() with. Like testing if a number is even. — Daniel, Nov 09 '13 at 20:06

Joe Z · Accepted Answer · 2013-11-09T19:30:24.527

You may want to tackle this in the opposite direction. Rather than taking the nth root of every value in the interval to see if the nth root is an integer, instead take the nth root of the bounds of the interval, and step in terms of the roots:

// Assume 'min' and 'max' set as above in your original program.
// Assume 'p' holds which root we're taking (ie. p = 3 means cube root)
int min_root = int( floor( pow( min, 1. / p ) ) );
int max_root = int( ceil ( pow( max, 1. / p ) ) );

for (int root = min_root; root <= max_root; root++)
{
    int raised = int( pow( root, p ) );
    if (raised >= min && raised <= max)
        cout << root << endl;
}

The additional test inside the for loop is to handle cases where min or max land directly on a root, or just to the side of a root.

You can remove the test and computation from the loop by recognizing that raised is only needed at the boundaries of the loop. This version, while slightly more complex looking, implements that observation:

// Assume 'min' and 'max' set as above in your original program.
// Assume 'p' holds which root we're taking (ie. p = 3 means cube root)
int min_root = int( floor( pow( min, 1. / p ) ) );
int max_root = int( ceil ( pow( max, 1. / p ) ) );

if ( int( pow( min_root, p ) ) < min )
    min_root++;

if ( int( pow( max_root, p ) ) > max )
    max_root--;

for (int root = min_root; root <= max_root; root++)
    cout << root << endl;

If you're really concerned about performance (which I suspect you are not in this case), you can replace int( pow( ..., p ) ) with code that computes the nth power entirely with integer arithmetic. That seems like overkill, though.

Great ideea. And it uses only integers. Thanks. – Daniel Nov 09 '13 at 20:13 — Daniel, Nov 09 '13 at 20:13

score 1 · Answer 2 · answered Nov 09 '13 at 19:17

1

Exact equality test for floating numbers might not work as you expect. It's better to compare with some small number:

float t = nroot(i, p);
if (fabs(t - rintf(t)) <= 0.00000001)
{
  cout << t << endl;
}

Even in this case you aren't guaranteed to get correct results for all values of min, max and p. All depends on this small number and precision you represent numbers. You might consider longer floating types like "double" and "long double".

answered Nov 09 '13 at 19:17

HEKTO

3,876
2
24
45

This is an excellent general point that cannot be made enough times. It seems to trip up everyone working with floating point arithmetic. In my own example above, I recast the problem to avoid floating point equality comparisons entirely, for similar reasons: Floating point equality comparisons stink. – Joe Z Nov 09 '13 at 20:40

Find n-th root of all numbers within an interval

2 Answers2

Linked