Browse Prior Art Database

MINIMAL CORRECTION LOGIC FOR PARTIAL REMAINDER OVERFLOW IN A NON-RESTORING DIVIDE ALGORITHM

IP.com Disclosure Number: IPCOM000005568D
Original Publication Date: 1985-Oct-01
Included in the Prior Art Database: 2001-Oct-16
Document File: 2 page(s) / 117K

Publishing Venue

Motorola

Related People

Doug MacGregor: AUTHOR [+3]

Abstract

The non-restoring divide algorithm is well known and has been used and understood for some time. Because this algorithm does not require that the partial remainder be recreated after an "over subtraction': it has fewer steps and as such can be implemented as a faster algorithm than the restoring divide operation which is common in microprocessors. A complete description of the algorithm is beyond the scope of this paper ISpanEl] but the basic concept is that when an "over subtraction" occurs, on the next iteration or iterations, it is possible to correct the partial remainder by keeping track of the results of the last operation and performing an add operation rather than a subtract. In this way the restore operation is not necessary. The non-restoring algorithm has the advantage of speed and the disadvantage that it requires increased control logic to select the type of operation to be performed.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 50% of the total text.

Page 1 of 2

0 M

MOTOROLA Technical Developments Volume 5 October 1985

MINIMAL CORRECTION LOGIC FOR PARTIAL REMAINDER OVERFLOW IN A NON-RESTORING DIVIDE ALGORITHM

by Doug MacGregor, Mitchell Taylor and James Kennedy

   The non-restoring divide algorithm is well known and has been used and understood for some time. Because this algorithm does not require that the partial remainder be recreated after an "over subtraction': it has fewer steps and as such can be implemented as a faster algorithm than the restoring divide operation which is common in microprocessors. A complete description of the algorithm is beyond the scope of this paper ISpanEl] but the basic concept is that when an "over subtraction" occurs, on the next iteration or iterations, it is possible to correct the partial remainder by keeping track of the results of the last operation and performing an add operation rather than a subtract. In this way the restore operation is not necessary. The non-restoring algorithm has the advantage of speed and the disadvantage that it requires increased control logic to select the type of operation to be performed.

   Most processors operate on N-bit operands using an N-bit or N/2-bit ALU (Arithmetic and Logic Unit). The divide operation is somewhat different in that regard because it has an 2N-bit dividend and an N-bit divisor, quo- tient, and remainder. In the MC68020, where N = 32, the operation is performed in two 32-bit ALUs in parallel. To start the operation, the 64 bits of dividend (which becomes the partial remainder) is stored in two pieces, the high portion in one 32-bit temporary (ALUH), and the low portion of the partial remainder is stored in another (ALUL). As the entire partial remainder is shifted left (including the portion stored in ALUL) the portion in ALUH is decremented by the divisor (as appropriate). Because the partial remainder is shifted left, it requires one less bit representation for each iteration. At the same time, the carry out of ALUH which can be used to indicate if the subtraction opera- tion resulted in an "over subtraction" is used to determine the next operation (add or subtract) for the high portion of the partial remainder and is shifted into ALUL to form the partial quotient which is being accumulated at a rate of one bit for each iteration and is also being shifted left at the same rate. In this way the number of bits of storage is constant (2N) throughout the operation. At the conclusion of the operation, the remainder is what is left over in ALUH and the quotient has been accumulated in ALUL.

   The non-restoring divide algorithm has one particular problem that normally requires a significant amount of hardware to correct. In order to prevent overflow of the partial remainder, the partial remainder requires N +l bits of representation. Because the size of the execution unit is a critical factor in the size of the design, th...