All Algebraic Functions Can Be Computed Fast
H. T. Kung, Joseph F. Traub · Journal of the ACM · 1978
The expansions of algebraic functions can be computed "fast" using the Newton Polygon Process and any "normal" iteration Let M(I) be the number of operations sufficient to multiply two/thdegree polynomials It is shown that the first N terms of an expansion of any algebraic function defined by an nth-degree polynomial can be computed in O(nM(N)) operations, while the classical method needs O(N ~) operations Among the numerous apphcatlons of algebraic functions are symbolic mathematics and combinatorial analysis Reversion, reciprocation, and nth root of a polynomial are all special cases of algebraic functions