# LOGARITHMIC DEPTH CIRCUITS FOR ALGEBRAIC FUNCTIONS.

Published

Journal Article

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).

### Full Text

### Duke Authors

### Cited Authors

- Reif, JH

### Published Date

- January 1, 1986

### Published In

### Volume / Issue

- 15 / 1

### Start / End Page

- 231 - 242

### International Standard Serial Number (ISSN)

- 0097-5397

### Digital Object Identifier (DOI)

- 10.1137/0215017

### Citation Source

- Scopus