Multiplication, division, and shift instructions in parallel random access machines

DOI10.1016/0304-3975(92)90362-JzbMath0780.68035OpenAlexW2086027629MaRDI QIDQ1193622

Michael C. Loui, Vijaya Ramachandran, Jerry L. Trahan

Publication date: 27 September 1992

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(92)90362-j

zbMATH Keywords

Turing machinepolynomial timepolynomial spaceparallel random access machine\(PSPACE\)\(PRAM\)enhanced instruction setssimulations of uniform circuits by \(RAM\)s

Mathematics Subject Classification ID

Computer system organization (68M99) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (2)

Multiple serial episodes matching ⋮ Window-accumulated subsequence matching problem is linear

Cites Work

• Unnamed Item
• Unnamed Item
• Unbounded fan-in circuits and associative functions
• Efficient parallel circuits and algorithms for division
• On saving space in parallel computation
• On uniform circuit complexity
• Division in idealized unit cost RAMs
• A characterization of the power of vector machines
• Time bounded random access machines
• Fast multiplication of large numbers
• Simulation of Parallel Random Access Machines by Circuits
• Constant Depth Reducibility
• A taxonomy of problems with fast parallel algorithms
• Logarithmic Depth Circuits for Algebraic Functions
• Log Depth Circuits for Division and Related Problems
• A universal interconnection pattern for parallel computers
• On Relating Time and Space to Size and Depth
• Implementation of simultaneous memory address access in models that forbid it
• An Algorithm for the Machine Calculation of Complex Fourier Series
• On the Computational Complexity of Algorithms
• Parallelism in random access machines

This page was built for publication: Multiplication, division, and shift instructions in parallel random access machines