LOGARITHMIC DEPTH CIRCUITS FOR ALGEBRAIC FUNCTIONS.

This paper describes parallel circuits for computation of a large class of algebraic functions on polynomials, power series, and integers, for which, it has been a long standing open problem to compute in depth less than OMEGA (log n)**2. Furthermore this paper describes boolean circuits of depth O(log n(log log n)) which, given n-bit binary numbers, compute the product of n numbers and integer division. As corollaries, we get boolean circuits of the same depth for evaluating, within accuracy 2** minus **2, polynomials, power series, and elementary functions such as (fixed) powers, roots, exponentiations, logarithm, sine and cosine. All these circuits have constant indegree, polynomial size, and may be uniformly constructed by a deterministic Turing machine with space O(log n).

Duke Scholars

Author John H. Reif Computer Science