Skip to main content
Journal cover image

Probabilistic parallel prefix computation

Publication ,  Journal Article
Reif, JH
Published in: Computers and Mathematics with Applications
January 1, 1993

Given inputs x1,...,xn, which are independent identically distributed random variables over a domain D, and an associative operation \to;, the probabilistic prefix computation problem is to compute the product x1 \to; x2 \to; ... \to; xn and its n - 1 prefixes. Instances of this problem are finite state transductions on random inputs, the addition or subtraction of two random n-bit binary numbers, and the multiplication or division of a random n-bit binary number by a constant. The best known constant fan-in circuits for these arithmetic operations had logarithmic depth, linear size, and produce no errors. Furthermore, matching lower bounds for depth and size (up to constant factors between the upper and lower bounds) had previously been obtained for the case of constant fan-in circuits with no errors. We give arithmetic circuits for probabilistic prefix computation, which for these random arithmetic operations have constant fan-in, linear size, O(log log n) depth, but error probability less than n-α for any given α > 0. For any constant fan-in circuits computing these random arithmetic operations with error probability n-α, we prove the circuit depth must be bounded from below by Ω(log log n). Hence, we conclude our circuits have asymptotically optimal depth among circuits with error probability n-α. We also give error-free circuits for these random arithmetic operations with constant fan-in at all nodes but one, linear size, and O(log log n) expected delay for their parallel evaluation. © 1993.

Duke Scholars

Published In

Computers and Mathematics with Applications

DOI

ISSN

0898-1221

Publication Date

January 1, 1993

Volume

26

Issue

1

Start / End Page

101 / 110

Related Subject Headings

  • Numerical & Computational Mathematics
  • 49 Mathematical sciences
  • 46 Information and computing sciences
  • 35 Commerce, management, tourism and services
  • 15 Commerce, Management, Tourism and Services
  • 08 Information and Computing Sciences
  • 01 Mathematical Sciences
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Reif, J. H. (1993). Probabilistic parallel prefix computation. Computers and Mathematics with Applications, 26(1), 101–110. https://doi.org/10.1016/0898-1221(93)90089-E
Reif, J. H. “Probabilistic parallel prefix computation.” Computers and Mathematics with Applications 26, no. 1 (January 1, 1993): 101–10. https://doi.org/10.1016/0898-1221(93)90089-E.
Reif JH. Probabilistic parallel prefix computation. Computers and Mathematics with Applications. 1993 Jan 1;26(1):101–10.
Reif, J. H. “Probabilistic parallel prefix computation.” Computers and Mathematics with Applications, vol. 26, no. 1, Jan. 1993, pp. 101–10. Scopus, doi:10.1016/0898-1221(93)90089-E.
Reif JH. Probabilistic parallel prefix computation. Computers and Mathematics with Applications. 1993 Jan 1;26(1):101–110.
Journal cover image

Published In

Computers and Mathematics with Applications

DOI

ISSN

0898-1221

Publication Date

January 1, 1993

Volume

26

Issue

1

Start / End Page

101 / 110

Related Subject Headings

  • Numerical & Computational Mathematics
  • 49 Mathematical sciences
  • 46 Information and computing sciences
  • 35 Commerce, management, tourism and services
  • 15 Commerce, Management, Tourism and Services
  • 08 Information and Computing Sciences
  • 01 Mathematical Sciences