Fast Parallel Arithmetic via Modular Representation
- 1 August 1991
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 20 (4) , 756-765
- https://doi.org/10.1137/0220048
Abstract
An almost uniform NC1 circuit family for integer division is presented. The circuit size is O(n6/log(n)). The circuit design is based on modular representation for integers below 2n. In particular, a very efficient technique is introduced for computing "a < b ?" when a and b are in modular representation. This leads to a uniform NC1 circuit of O(n2) size for comparison of integers in modular representation.Keywords
This publication has 7 references indexed in Scilit:
- Log Depth Circuits for Division and Related ProblemsSIAM Journal on Computing, 1986
- Logarithmic Depth Circuits for Algebraic FunctionsSIAM Journal on Computing, 1986
- Efficient Implementations of the Chinese Remainder Theorem for Sign Detection and Residue DecodingIEEE Transactions on Computers, 1985
- A taxonomy of problems with fast parallel algorithmsInformation and Control, 1985
- On uniform circuit complexityJournal of Computer and System Sciences, 1981
- On Relating Time and Space to Size and DepthSIAM Journal on Computing, 1977
- A Course in ArithmeticPublished by Springer Nature ,1973