CmpE 110

HomeWork Set 3 - MULTIPLICATION & DIVISION

Due: Oct. 20, 2003

SOLUTIONS

1.) Use Booth's Algorithm (Radix 2) to  show:  11 (5 bits)  * 5 (5 bits) = 55 (2 points)

A = 01011,  -A = 10101, B = 00101

                01011

            x  00101(0)

      1111110101   (1)0  -A  (Start of string of 1's)                               

      000001011-    (0)1 +A (end of string of 1's)

      11110101--    (1)0  -A (start of a string of 1's)

      0001011---     (0)1 +A (End of string of 1's)

      0000000----    (0)0 +0 (middle of string of 0's)

+     000000-----     (0)0 +0 (middle of string of 0's)

       0000110111₂    = 55₁₀  

2.) Use Booth's algorithm (Radix 4) to show:   25 (6 bits) * 5 (6 bits) = 125 (3 points)

A = 011001,  -A = 100111, B = 000101

                   011001

               x  000101 (0)

       000000011001  (01)0  -A +2A = A  (start and end of a string of 1s)      

       0000011001--   (01)0  -A +2A = A (start and end of a string of 1s)

  +   00000000----    (00)0  0 + 2*0 = 0  (middle of a string of 0's)

       000001111101₂     =   125₁₀ 

3.) Use Restoring Division to show:    43 (7 bits)  / 8 (7 bits) --> Q= 5, R = 3    (2 points)

R =       0101011,  B = 0001000  if A=A-B step is positive add a one to the end of Quotient, add a zero if its negative

R =       0000000 0101011       Init A in 2n Bit register R

B =       0001000 0000000        B_13-7 = B, Init B_6-0 = 0000000

B >> 1  0000100 0000000        Shift B right 1

-B         1111100 0000000       -B

R=R-B 1111100 0101011      Oops negative, Restore R    Quotient  = 0

R =       0000000 0101011

B =       0000100 0000000     

B >> 1   0000010 0000000     Shift B right 1

-B         1111110 0000000     -B

R=R-B  1111110 0101011      oops negative Restore R Quotient = 00

R =        0000000 0101011

B =        0000010 0000000   

B>>1     0000001 0000000

-B          1111111 0000000    -B

R=R-B   1111111 0101011    Oops negative, Restore R Quotient =000

R =        0000000 0101011

B =        0000001 0000000 

B>> 1    0000000 1000000  Shift B right 1

-B          1111111 1000000

R=R-B   1111111 1101011  Oops negative, Restore R Quotient = 0000

R =        0000000 0101011

B =        0000000 1000000

B>> 1    0000000 0100000    Shift B right 1

-B          1111111 1100000   -B

R= R-B 0000000 0001011   Positive, Quotient = 00001

B =       0000000 0100000

B >> 1   0000000 0010000   Shift B right 1

- B         1111111 1110000   -B

R=R-B   1111111 1111011 Negative Restore R Quotient = 000010

R =        0000000 0001011  

B =        0000000 0010000  

B>>1    0000000 0001000 Shift B right 1

-B         1111111 1111000  -B

R=R-B 0000000 0000011  positive, Quotient = 0000101

Since signs are the same, the result remains positive

Remainder =  0000000 0000011₂ = 3₁₀  Quotient = 0000101₂ = 5₁₀

4.) Use Non-Restoring Division to show:   72 ( 8 bits)  / 7 (8 bits) --> Q = 10, R = 2  (3 points)

A= 01001000 B = 00000111 00000000     If R is negative on R = R+-B Q = 0, next R=R+B, 

                                                              If R is positive on R= R+-B Q = 1, next R=R-B

R =     00000000 01001000  init R with A
B =     00000111 00000000   B

B >>1 00000011 10000000 Shift B right 1

-B =    11111100 10000000  -B

R=R-B 11111100 11001000  Answer negative so Quotient = 0

B >> 1  00000001 11000000  Shift B right 1

R=R+B 11111110 10001000 Answer negative so quotient = 00

B >> 1  00000000 11100000

R=R+B 11111111 01101000 Answer is negative so quotient = 000

B >> 1  00000000 01110000 

R=R+B 11111111 11011000 Answer is negative so quotient = 0000

B >> 1  00000000 00111000

R=R+B 00000000 00010000 Answer is positive so quotient = 0000 1

B >> 1  00000000 00011100 

-B         11111111 11100100 -B

R=R-B  11111111 11110100 Answer is negative so quotient = 0000 10

B >> 1   00000000 00001110

R =R+B 00000000 00000010 Answer is positive so quotient = 0000 101

B >> 1   00000000 00000111

-B          11111111 11111001 -B

R=R-B   11111111 11111011 Answer is negative so quotient = 0000 1010

Since this is last step Restore R since the last answer was negative = 00000000 00000010

Quotient    = 00001010₂ = 10₁₀       

Remainder = 00000010₂ = 2₁₀