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