Restoring Division - Prof. Mahesh PDF

Preview

Summary

Prof. Mahesh...

Description

Subject: Computer Organization

Arithmetic: Restoring Division

a) No Non-R n-R n-Rest est estori ori oring ng Di Divis vis visio io ion n Al Algo go gorit rit rithm: hm: In this algorithm, after subtraction If A is positive, we shift left and subtract M, that is, we perform 2A−M. If A is negative, we restore it by performing A+M, and then we shift it left and subtract M. This is equivalent to performing 2A+ M. The q0 bit is appropriately set to 0 or 1 after the correct operation has been performed. We can summarize this in the following algorithm for non-restoring division. Stag Stage e 11:: Do the following tw two o st steps eps n tim times: es: Step 1. If A is positive i.e., Sign of A is 0, shift A and Q left one bit position and subtract M from A (2A – M); otherwise, shift A and Q left and add M to A (2A+M). Step 2. Now, if the sign of A is 0 (+ve), set q0 to 1; otherwise, set q0 to 0. Stag Stage e 22:: If the sign of A is 1 (-ve), add M to A to store back the (+)ve remainder in A after n cycles else the content of A itself is remainder. The logic circuitry in Figure 3.33 used for restoring Division logic can also be used to perform this algorithm, except that the Restore operations are no longer needed. The Non-Restoring Division Algorithm explained in steps discussed in Stage 1 and Stage 2 above are shown using a flowchart in Figu Figure re 33.34 .34

Figur Figure e 33.34: .34: Non-Restoring Division Algorithm

Subject: Computer Organization

Exam Examp ple: St Stag ag age e 1 rrepe epe epeate ate ated d for n time timess Register MOperation n-bit positive Divisor 00011 As A is (+)ve Shift A and Q left & Subtract M (2A-M) As Sign of A is 1 set q0 to 0 As A is (-)ve Shift A and Q left & Add M (2A+M) As Sign of A is 1 set q0 to 0 As A is (-)ve Shift A and Q left & Add M (2A+M) As Sign of A is 0 set q0 to 0 As A is (+)ve Shift A and Q left & Subtract M (2A-M) As Sign of A is 1 set q0 to 0

Arithmetic: Restoring Division

Register A

Register Qn-bit dividend q3 q2 q1 q0

00000 00001 1 1 1 0 1 (2’s) 11110 11110 11100

1 0 0 0 0 0 0 _

00011 11111 11111 11110 00011 00001 00001 00010 11101 11111 11111

Cycle

Cycle 1 0 0 0 0 0 0 0 _ Cycle 2 0 0 0 0 0 0 0 _ Cycle 3 0 0 0 1 0 0 1 _ Cycle 4 0 0 1 0 Quotient

Stag Stage e 22:: As ssign ign of A is 11;; Ad Add d M to A As Sign of A is 1 (-)ve Add M to A; A= A+M

11111 00011 00010 Remainder

0 0 1 0

There are no simple algorithms for directly performing division on signed. In division, the operands can be preprocessed to change them into positive values. After using one of the algorithms just discussed, the signs of the quotient and the remainder are adjusted as necessary....