nth Root Algorithm

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

nth Root Algorithm

Post by Oliver1978 » Mon Aug 10, 2015 3:49 pm

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: 46
Joined: Sat Oct 11, 2008 11:24 am

Re: nth Root Algorithm

Post by DJohn » Mon Aug 10, 2015 6:32 pm

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.

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

Re: nth Root Algorithm

Post by Oliver1978 » Mon Aug 10, 2015 6:42 pm

This is embarassing :shock: 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. :oops:

Thanks for pointing this out, DJohn!
49.157.5694.1125

Post Reply