Fast Parallel Arithmetic via Modular Representation
Authors:
- George I. DavidaGDGeorge I. Davida
- Bruce LitowBLBruce Litow
- 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
Abstract
An almost uniform $NC^1 $ circuit family for integer division is presented. The circuit size is $O(n^6 / \log (n))$. The circuit design is based on modular representation for integers below $2^n $. In particular, a very efficient technique is introduced for computing “$a < b$?” when a and b in modular representation. This leads to a uniform $NC^1 $ circuit of $O(n^2 )$ 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 Arithmetic1973