CODEWITHSUNDEEP
c++
Ankur Mishra
Ankur Mishra

Reputation: 61

Correct way to find nth root using pow() in c++

I have to find nth root of numbers that can be as large as 10^18, with n as large as 10^4.
I know using pow() we can find the nth roots using,

x = (long int)(1e-7 + pow(number, 1.0 / n))

But this is giving wrong answers on online programming judges, but on all the cases i have taken, it is giving correct results. Is there something wrong with this method for the given constraints
Note: nth root here means the largest integer whose nth power is less than or equal to the given number, i.e., largest 'x' for which x^n <= number.
Following the answers, i know this approach is wrong, then what is the way i should do it?

Upvotes: 0

Views: 16178

Answers (4)

Michel
Michel

Reputation: 339

You can try this to get the nth_root with unsigned in C :

// return a number that, when multiplied by itself nth times, makes N.
unsigned nth_root(const unsigned n, const unsigned nth) {
    unsigned a = n, c, d, r = nth ? n + (n > 1) : n == 1 ;
    for (; a < r; c = a + (nth - 1) * r, a = c / nth)
        for (r = a, a = n, d = nth - 1; d && (a /= r); --d);
    return r;
}

Yes it does not include <math.h>, example of output :

  24 == (int) pow(15625, 1.0/3)

  25 == nth_root(15625, 3)
   0 == nth_root(0, 0)
   1 == nth_root(1, 0)
   4 == nth_root(4096, 6)
  13 == nth_root(18446744073709551614, 17) // 64-bit 20 digits
  11 == nth_root(340282366920938463463374607431768211454, 37) // 128-bit 39 digits

The default guess is the variable a, set to n.

Upvotes: 0

thexiv
thexiv

Reputation: 25

I use this routine I wrote. It's the faster of the ones I've seen here. It also handles up to 64 bits. BTW, n1 is the input number. 

for (n3 = 0; ((mnk) < n1) ; n3+=0.015625, nmrk++) {
   mk += 0.0073125;
   dad += 0.00390625;
   mnk = pow(n1, 1.0/(mk+n3+dad));
   mnk = pow(mnk, (mk+n3+dad));
}

Although not always perfect, it does come the closest.

Upvotes: 0

Max Lybbert
Max Lybbert

Reputation: 20021

I think I finally understood your problem. All you want to do is raise a value, say X, to the reciprocal of a number, say n (i.e., find ⁿ√X̅), and round down. If you then raise that answer to the n-th power, it will never be larger than your original X. The problem is that the computer sometimes runs into rounding error.

#include <cmath>

long find_nth_root(double X, int n)
{
    long nth_root = std::trunc(std::pow(X, 1.0 / n));
    // because of rounding error, it's possible that nth_root + 1 is what we actually want; let's check
    if (std::pow(nth_root + 1, n) <= X) {
        return nth_root + 1;
    }
    return nth_root;
}

Of course, the original question was to find the largest integer, Y, that satisfies the equation X ≤ Yⁿ. That's easy enough to write:

long find_nth_root(double x, int d)
{
    long i = 0;
    for (; std::pow(i + 1, d) <= x; ++i) { }
    return i;
}

This will probably run faster than you'd expect. But you can do better with a binary search:

#include <cmath>

long find_nth_root(double x, int d)
{
    long low = 0, high = 1;
    while (std::pow(high, d) <= x) {
        low = high;
        high *= 2;
    }
    while (low != high - 1) {
        long step = (high - low) / 2;
        long candidate = low + step;

        double value = std::pow(candidate, d);
        if (value == x) {
            return candidate;
        }
        if (value < x) {
            low = candidate;
            continue;
        }
        high = candidate;
    }
    return low;
}

Upvotes: 0

user1196549
user1196549

Reputation:

You can just use 

x = (long int)pow(number, 1.0 / n)

Given the high value of n, most answers will be 1.

UPDATE:

Following the OP comment, this approach is indeed flawed, because in most cases 1/n does not have an exact floating-point representation and the floor of the 1/n-th power can be off by one.

And rounding is not better solution, it can make the root off by one in excess.

Another problem is that values up to 10^18 cannot be represented exactly using double precision, whereas 64 bits ints do.

My proposal:

1) truncate the 11 low order bits of number before the (implicit) cast to double, to avoid rounding up by the FP unit (unsure if this is useful).

2) use the pow function to get an inferior estimate of the n-th root, let r.

3) compute the n-th power of r+1 using integer arithmetic only (by repeated squaring).

4) the solution is r+1 rather than r in case that the n-th power fits.

There remains a possibility that the FP unit rounds up when computing 1/n, leading to a slightly too large result. I doubt that this "too large" can get as large as one unit in the final result, but this should be checked.

Upvotes: 5

Related Questions