Logarithmic depth circuits for algebraic functions

Publisher Website
Google Scholar
Abstract
This paper describes circuits for computation of various algebraic functions on polynomials, power series, integers, and reals for which it has been a long standing open problem to compute in depth less then (log n)2. Let R[x] be the polynomials and power series over a commutative ring which supports a fast Fourier transform and let L[x] be the polynomials and power series over the rationals L. For polynomials of degree n-1, we give circuits of depth O(log n) for computing - the m-th power of a polynomial and the product of m polynomials in R[x], where m=nO(1) - the symmetric functions on R[x] - the remainder and quotient of division of polynomials in L[x] - interpolation of a polynomial in L[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=nO(1) - the composition of power series in R[x] - the reciprocal of a power series and the division of two power series in L[x] -the reversion of a power series in L[x] - various elementary functions applied to power series in L[x] such as (fixed) powers, roots, exponentation, logarithm, sin, cos, arctangent, and hyperbolic cosine. For integers represented by n bit binary numbers, we give boolean circuits (whose gates compute the boolean operations ∧, ∨, and ¬) of depth O(log n (loglog n) 2) for computing: - the m-th power of an integer and the product of m = nO(1) integers, - the remainder and quotient of the division of two integers. There are many immediate consequences of this result. For reals on a finite interval [a,b] represented as floating point numbers within relative accuracy o(2-n), we have boolean circuits of depth O (log n(loglog n) 2) for computing within relative accuracy o(2-n): - the m-th power of a real and the product of m = nO(1) reals - the reciprocal of a real and division of reals - various elementary functions on reals. Also, as a consequence of the above, for polynomials and power series in L[x] we have uniform boolean circuits of depth O(log n(loglog n)2) for all the above listed problems for polynomials and power series, and also: - evaluation of a polynomial or power series in L[x] at n points, within relative accuracy o(2-n). All our circuits may be uniformly constructed by a deterministic Turning machine with space O(log n) and have constant indegree.

This publication has 13 references indexed in Scilit: