All Algebraic Functions Can Be Computed Fast
- 1 April 1978
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 25 (2) , 245-260
- https://doi.org/10.1145/322063.322068
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 functionsKeywords
This publication has 4 references indexed in Scilit:
- HENSEL MEETS NEWTON — ALGEBRAIC CONSTRUCTIONS IN AN ANALYTIC SETTINGPublished by Elsevier ,1976
- MULTIPLE-PRECISION ZERO-FINDING METHODS AND THE COMPLEXITY OF ELEMENTARY FUNCTION EVALUATIONPublished by Elsevier ,1976
- On computing reciprocals of power seriesNumerische Mathematik, 1974
- MACSYMA - the fifth yearACM SIGSAM Bulletin, 1974