Calculate Nth root with integer arithmetic

One obvious way would be to use binary search together with exponentiation by squaring. This will allow you to find nthRoot(x, n) in O(log (x + n)): binary search in [0, x] for the largest integer k such that k^n <= x. For some k, if k^n <= x, reduce the search to [k + 1, x], otherwise reduce it to [0, k].

Do you require something smarter or faster?

One easy solution is to use the binary search.

Assume we are finding nth root of x.

Function GetRange(x,n):
    y=1
    While y^n < x:
        y*2
    return (y/2,y)

Function BinSearch(a,b,x,):
    if a == b+1:
        if x-a^n < b^n - x:
           return a
        else:
           return b
    c = (a+b)/2
    if n< c^n:
        return BinSearch(a,c,x,n)
    else:
        return BinSearch(c,b,x,n)

a,b = GetRange(x,n)
print BinSearch(a,b,x,n)

===Faster Version===

Function BinSearch(a,b,x,):
    w1 = x-a^n
    w2 = b^n - x
    if a <= b+1:
        if w1 < w2:
           return a
        else:
           return b
    c = (w2*a+w1*b)/(w1+w2)
    if n< c^n:
        return BinSearch(a,c,x,n)
    else:
        return BinSearch(c,b,x,n)

It seems to me that the Shifting nth root algorithm provides exactly what you want:

The shifting nth root algorithm is an algorithm for extracting the nth root of a positive real number which proceeds iteratively by shifting in n digits of the radicand, starting with the most significant, and produces one digit of the root on each iteration, in a manner similar to long division.

There are worked examples on the linked wikipedia page.

You can use Newton's method using only integer arithmetic, the step is the same as for floating point arithmetic, except you have to replace floating point operators with the corresponding integer operators in languages which have different operators for these.

Let's say you want to find the integer-k-th root of a > 0, which should be the largest integer r such that r^k <= a. You start with any positive integer (of course a good starting point helps).

int_type step(int_type k, int_type a, int_type x) {
    return ((k-1)*x + a/x^(k-1))/k;
}

int_type root(int_type k, int_type a) {
    int_type x = 1, y = step(k,a,x);
    do {
        x = y;
        y = step(k,a,x);
    }while(y < x);
    return x;
}

Except for the very first step, you have x == r <==> step(k,a,x) >= x.