algorithm - Calculate Nth root with integer arithmetic

Question

There are a couple of ways to find integer square roots using only integer arithmetic. For example this one. It makes for interesting reading and also a very interesting theory, particularly for my generation where such techniques aren't so useful any more.

The main thing is that it can't use floating point arithmetic, so that rules out newtons method and it's derivations. The only other way I know of to find roots is binomial expansion, but that also requires floating point arithmetic.

What techniques/algorithms are there for computing integral nth roots using only integer arithmetic?

Edit: Thanks for all the answers so far. They all seem to be slightly more intelligent trial and improvement. Is there no better way?

Edit2: Ok, so it would seem there is no smart way to do this without trial/improvement and either newtons method or a binary search. Can anyone provide a comparison of the two in theory? I have run a number of benchmarks between the two and found them quite similar.

Answer 1

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.