## nth Root Algorithm

Arithmetic, algebra, number theory, sequence and series, analysis, ...
Oliver1978
Posts: 165
Joined: Sat Nov 22, 2014 9:13 pm
Location: Erfurt, Germany

### nth Root Algorithm

I've found this n-th root algorithm in Richard P. Brent's book "Modern Computer Arithmetic". The power function was inserted by me to get the algorithm to work with bigints if necessary. D's internal ^^ operator for powers only works with purely numerical values.
Anyway, I've tried the algorithm an it returns 6 for nthRoot(243, 3) and 9 for nthRoot(729,3). Both results are of course wrong.

Code: Select all

T nthRoot(T)(T m, T n)
{
T power(T)(in T x, in T y)
{
T res = 1;
T b = x, e = y;
while (e > 0)
{
if (e & 1) res *= b;
b *= b;
e >>= 1;
}
return res;
}

if ((m < 1) || (n < 0)) return cast(T)0;
if ((m == 1) || (n == 0)) return cast(T)1;
if (n == 1) return m;

T u = m;
T s, t;

do
{
s = u;
t = (n - 1) * s + (m / power(s, (n - 1)));
u = t / n;
}
while (u < s);

return s;
}

Can anybody help me out?
49.157.5694.1125

DJohn
Posts: 43
Joined: Sat Oct 11, 2008 11:24 am

### Re: nth Root Algorithm

What's the problem? The floor of the cube root of 243 is 6, and the floor of the cube root of 729 is 9. Both results are correct.

Oliver1978
Posts: 165
Joined: Sat Nov 22, 2014 9:13 pm
Location: Erfurt, Germany

### Re: nth Root Algorithm

This is embarassing I've re-checked my numbers and found that I'd actually messed up base and exponent. Just because 3^5 ist 243, the cube root of 243 is not 5.

Thanks for pointing this out, DJohn!
49.157.5694.1125