Bits and relative order from residues, space efficiently

DOI10.1016/0020-0190(94)00021-2zbMath0807.68051OpenAlexW1963893271MaRDI QIDQ1327295

Paul F. Dietz, Ioan I. Macarie, Joel I. Seiferas

Publication date: 18 July 1994

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(94)00021-2

zbMATH Keywords

space complexitysign detectionparity detectionspace-efficiently computing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Congruences; primitive roots; residue systems (11A07)

Related Items (9)

Uniform constant-depth threshold circuits for division and iterated multiplication. ⋮ On the complexity of algebraic numbers, and the bit-complexity of straight-line programs1 ⋮ Binary coded unary regular languages ⋮ Factoring and Testing Primes in Small Space ⋮ Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\) ⋮ Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\) ⋮ Nondeterministic \(NC^1\) computation ⋮ On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits ⋮ UNARY CODED NP-COMPLETE LANGUAGES IN ASPACE(log log n)

Cites Work

• Multihead two-way probabilistic finite automata
• An efficient algorithm and parallel implementations for binary and residue number systems
• Efficient Implementations of the Chinese Remainder Theorem for Sign Detection and Residue Decoding
• Logarithmic Depth Circuits for Algebraic Functions
• Fast Parallel Arithmetic via Modular Representation
• On Relating Time and Space to Size and Depth
• A novel division algorithm for the residue number system
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Bits and relative order from residues, space efficiently