Algorithm to find nth root of a number

Question

I am looking for an efficient algorithm to find nth root of a number. The answer must be an integer. I have found that newtons method and bisection method are popular methods. Are there any efficient and simple methods for integer output?

Answer 1

#include <math.h>
inline int root(int input, int n)
{
  return round(pow(input, 1./n));
}

This works for pretty much the whole integer range (as IEEE754 8-byte doubles can represent the whole 32-bit int range exactly, which are the representations and sizes that are used on pretty much every system). And I doubt any integer based algorithm is faster on non-ancient hardware. Including ARM. Embedded controllers (the microwave washing machine kind) might not have floating point hardware though. But that part of the question was underspecified.

Answer 2

I know this thread is probably dead, but I don't see any answers I like and that bugs me...

int root(int a, int n) {
    int v = 1, bit, tp, t;
    if (n == 0) return 0; //error: zeroth root is indeterminate!
    if (n == 1) return a;
    tp = iPow(v,n);
    while (tp < a) {    // first power of two such that v**n >= a
        v <<= 1;
        tp = iPow(v,n);
    }
    if (tp == a) return v;  // answer is a power of two
    v >>= 1;
    bit = v >> 1;
    tp = iPow(v, n);    // v is highest power of two such that v**n < a
    while (a > tp) {
        v += bit;       // add bit to value
        t = iPow(v, n);
        if (t > a) v -= bit;    // did we add too much?
        else tp = t;
        if ( (bit >>= 1) == 0) break;
    }
    return v;   // closest integer such that v**n <= a
}
// used by root function...
int iPow(int a, int e) {
    int r = 1;
    if (e == 0) return r;
    while (e != 0) {
        if ((e & 1) == 1) r *= a;
        e >>= 1;
        a *= a;
    }
    return r;
}

This method will also work with arbitrary precision fixed point math in case you want to compute something like sqrt(2) to 100 decimal places...