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.
3 Answers
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.
3 Comments
Ian Henry
I think he wants the roots of a number, not the roots of an equation.
aaronasterling
@Ian Henry, What's the difference? the real, positive root of a is the real, positive root of the equation a - x^n and vice versa. I did notice that Mitch Wheat posted an already derived version of newtons method that obscures this basic fact.
Ian Henry
Ah, I should've read your whole answer. I had never made that connection. +1 for expanding my (clearly lacking) numerical analysis knowledge.
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; } 
Comments
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.
Math.Pow(x, 1.0 / n);is pretty quick.