What is the fastest way to calculate the n-th root of a number?
I'm aware of the Try and Fail way, but I need a faster algorithm.
+6
A:
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.
aaronasterling
2010-10-03 04:55:16
I think he wants the roots of a number, not the roots of an equation.
Ian Henry
2010-10-03 05:05:41
@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.
aaronasterling
2010-10-03 05:07:41
Ah, I should've read your whole answer. I had never made that connection. +1 for expanding my (clearly lacking) numerical analysis knowledge.
Ian Henry
2010-10-03 05:12:03
+2
A:
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.
Mitch Wheat
2010-10-03 04:55:47