Accession Number : AD0767702

Title :   On Computing Reciprocals of Power Series,

Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Kung,H. T.

Report Date : SEP 1973

Pagination or Media Count : 18

Abstract : Root-finding iterations are used to compute reciprocals of power series. The author shows that Sieveking's algorithm is just Newton iteration applied in the field of power series. Let (L sub n) denote the number of non-scalar multiplications needed to compute the first n+1 terms of the reciprocal. It is shown that n+1 < or = (L sub n) < or = 4n-log (base 2) n. It is conjectured that (L sub n) = 4n - lower order terms. (Modified author abstract)

Descriptors :   (*ITERATIONS, *POWER SERIES), ALGORITHMS, POLYNOMIALS

Subject Categories : Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE