Accession Number : AD0755451

Title :   Fast Evaluation and Interpolation,

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

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

Report Date : JAN 1973

Pagination or Media Count : 14

Abstract : A method for dividing a polynomial of degree (2n-1) by a precomputed nth degree polynomial in 0(n log n) arithmetic operations is given. This is used to prove that the evaluation of an nth degree polynomial at n+1 arbitrary points can be done in 0(n (log sup 2) n) arithmetic operations, and consequently, its dual problem, interpolation of an nth degree polynomial from n+1 arbitrary points can be performed in 0(n (log sup 2) n) arithmetic operations. The best previously known algorithms required 0(n (log sup 3) n) arithmetic operations. (Author)

Descriptors :   (*POLYNOMIALS, *INTERPOLATION), COMPLEX NUMBERS, ALGORITHMS, THEOREMS

Subject Categories : Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE