Fast Parallel Arithmetic via Modular Representation

Authors:
  • GDGeorge I. Davida
    George I. Davida
  • BLBruce Litow
    Bruce Litow

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.

This publication has 7 references indexed in Scilit: