Logarithmic Depth Circuits for Algebraic Functions.
Abstract
This paper describes circuits for computation of various algebraic functions on polynomials, power series, integers, and reals. Let R(x) be the polynomials and power series over a commutative ring which supports a fast Fourier transform and let Zx be the polynomials and power series over the rationals Q. For polynomials of degree n-1, we give circuits of depth 0(log n) for computing - the m-th power of a polynomial and the product of m polynomials in R(x), where m=0(n) - the symmetric functions on R(x)- the remainder and quotient of division of polynomials in Q(x)- interpolation of a polynomial in Q(x). For power series with n given low order terms, we give circuits of depth o(log n) for computing the first n low order terms of - the m-th power of a power series in R(x) and the product of m power series in R(x) where m=0(n) - the composition of power series in R(x) - the reciprocal of a power series and the division of two power series in Q(x) - the reversion of a power series in Q(x) - various elementary functions applied to power series in Q(x) such as (fixed) powers, roots, exponentation, logarithm, sin, cos, arctangent, and hyperbolic cosine.
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 01, 1982
- Accession Number
- ADA122661
Entities
People
- John Reif
Organizations
- Harvard University