Digital Arithmetic: Division Algorithms

Division is one of the basic arithmetic operations supported by every computer system. The operation can be performed and implemented in either hardware or software, or a combination of the two. Although division is not as frequent as addition and multiplication, nowadays most processors implement it in hardware to not compromise the overall computation performances. In this note, we explain the basic algorithms, suitable for hardware and software, to implement division in computer systems. Two classes of algorithms implement division or square root: digit-recurrence and multiplicative (e.g., Newton-Raphson) algorithms. The first class of algorithms are of digit-recurrence type, and are especially suitable for hardware implementation as they require modest resources and provide good performance on contemporary technology. The second class of algorithms, multiplicative type, requires significant hardware resources and is more suitable for software implementation on the existing multiply units. The purpose of this note is to provide an introductory survey using a presentation style suitable for reading also by the interested non-specialist Readers