CODEWITHSUNDEEP
c#algorithmmathnth-root
Alon Gubkin
Alon Gubkin

Reputation: 57129

n-th Root Algorithm

What is the fastest way to calculate the n-th root of a number?

I'm aware of the Try and Fail method, but I need a faster algorithm.

Upvotes: 4

Views: 5443

Answers (3)

Doug
Doug

Reputation: 331

Not the fastest, but it works. Substitute your chosen type:

    private static decimal NthRoot(decimal baseValue, int N)
    {
        if (N == 1)
            return baseValue;
        decimal deltaX;
        decimal x = 0.1M;
        do
        {
            deltaX = (baseValue / Pow(x, N - 1) - x) / N;
            x = x + deltaX;
        } while (Math.Abs(deltaX) > 0);
        return x;
    }

    private static decimal Pow(decimal baseValue, int N)
    {
        for (int i = 0; i < N - 1; i++)
            baseValue *= baseValue;
        return baseValue;
    }

Upvotes: 4

aaronasterling
aaronasterling

Reputation: 71004

The canonical way to do this is Newton's Method. In case you don't know, the derivative of xn is nxn-1. This will come in handy. 1 is a good first guess. You want to apply it to the function a - xn

IIRC, it's superconvergent on functions of the form a - xn, but either way, it's quite fast. Also, IIRC, the warning in the wiki about it failing to converge would apply to more complex functions that have properties that the 'nice' functions you are interested in lack.

Upvotes: 10

Mitch Wheat
Mitch Wheat

Reputation: 300559

Are you referring to the nth root algorithm ? This is not a try-and-fail method, but an iterative algorithm which is repeated until the required precision is reached.

Upvotes: 2

Related Questions