Fast computation of the Nth root (Q1263248)

A new class of iterative methods for computing a differentiable function is proposed, which is based on Padé approximation to Taylor's series of the function. It leads to a faster algorithm than Newton's method for \(x^{1/N}\) and a different interpretation of Newton's method. This algorithm uses 3rd degree approximation of continued fraction expansion to Taylor's series for \(x^{1/N}\), with adaptive expansion point for every iteration. Its major computational cost is \(O[(2 \log_ 2 N)(\log_ 4 M)]\) multiplications asymptotically, M is the number of precision bits desired, as opposed to existing bound of \(O[(2 \log_ 2 N)(\log_ 2 M)]\) for Newton's method.