## 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

## Published In

## DOI

## ISSN

## Publication Date

## Volume

## Issue

## Start / End Page

## Related Subject Headings

- Computation Theory & Mathematics
- 4903 Numerical and computational mathematics
- 4901 Applied mathematics
- 4613 Theory of computation
- 0802 Computation Theory and Mathematics
- 0101 Pure Mathematics

### Citation

*SIAM Journal on Computing*,

*15*(1), 231–242. https://doi.org/10.1137/0215017

*SIAM Journal on Computing*15, no. 1 (January 1, 1986): 231–42. https://doi.org/10.1137/0215017.

*SIAM Journal on Computing*, vol. 15, no. 1, Jan. 1986, pp. 231–42.

*Scopus*, doi:10.1137/0215017.

## Published In

## DOI

## ISSN

## Publication Date

## Volume

## Issue

## Start / End Page

## Related Subject Headings

- Computation Theory & Mathematics
- 4903 Numerical and computational mathematics
- 4901 Applied mathematics
- 4613 Theory of computation
- 0802 Computation Theory and Mathematics
- 0101 Pure Mathematics