All Algebraic Functions Can Be Computed Fast

Abstract

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/th - degree 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 combina- torial analysis Reversion, reciprocation, and nth root of a polynomial are all special cases of algebraic functions