Question

[30] <§3.4> Using a table similar to that shown in Figure 3.10, calculate 74 divided by 21 using the hardware described in Figure 3.11. You should show the contents of each register on each step. Assume A and B are unsigned 6-bit integers. This algorithm requires a slightly

different approach than that shown in Figure 3.9. You will want to think hard about this, do an experiment or two, or else go to the web to figure out how to make this work correctly. (Hint: one possible solution involves using the fact that Figure 3.11 implies the remainder register can be shifted either direction.)

Short answer

The required table is:

Iteration	Step	Quotient	Divisor	remainder
o	At the initial	0000	010101	000000 111100
After shifting the remainder left	0000	010101	000001 111000
1	1. remainder = remainder – divisor	0000	010101	110000 111000
2b. remainder < 0->divisor +, sll R, R0=0	0000	010101	000011 110000
2	1. remainder = remainder – divisor	0000	010101	110010 110000
2b. remainder < 0->divisor +, sll R, R0=0	0000	010101	000111 100000
3	1. remainder = remainder – divisor	0000	010101	110110 100000
2b. remainder < 0->divisor +, sll R, R0=0	0000	010101	001111 000000
4	1. remainder = remainder – divisor	0000	010101	111110 000000
2b. remainder < 0->divisor +, sll R, R0=0	0000	010101	011110 000000
5	1. remainder = remainder – divisor	0001	010101	001101 000000
2a. remainder >= 0->sll R, R0=0	0001	010101	011010 000001
6	1. remainder = remainder – divisor	0001	010101	001001 000001
2a. remainder >= 0->sll R, R0=0	0011	010101	010010 000011
Done	Shifting the left half of the remainder to the right.	0011	010101	001001 000011

Step-by-step solution

Define the concept.

Iteration number: 0

Details of the step	The values of divisor	The values of the remainder
At the initial	010101	000000 111100
After shifting the remainder left	010101	000001 111000

Iteration number: 1

Details of the step	The values of divisor	The values of the remainder
1.remainder = remainder – divisor	010101	110000 111000
2b. remainder < 0->divisor +, sll R, R0=0	010101	000011 110000

Iteration number: 2

Details of the step	The values of divisor	The values of the remainder
1.remainder = remainder – divisor	010101	110010 110000
2b. remainder < 0->divisor +, sll R, R0=0	010101	000111 100000

Iteration number: 3

Details of the step	The values of divisor	The values of the remainder
1.remainder = remainder – divisor	010101	110110 100000
2b. remainder < 0->divisor +, sll R, R0=0	010101	001111 000000

Iteration number: 4

Details of the step	The values of divisor	The values of the remainder
1.remainder = remainder – divisor	010101	111110 000000
2b. remainder < 0->divisor +, sll R, R0=0	010101	011110 000000

Iteration number: 5

Details of the step	The values of divisor	The values of the remainder
1.remainder = remainder – divisor	010101	001101 000000
2a. remainder >= 0->sll R, R0=0	010101	011010 000001

Iteration number: 6

Details of the step	The values of divisor	The values of the remainder
1.remainder = remainder – divisor	010101	001001 000001
2a. remainder >= 0->sll R, R0=0	010101	010010 000011

DONE:

Details of the step	The values of divisor	The values of the remainder
Shifting the left half of the remainder to the right.	010101	001001 000011

Determine the calculation.

As shown in the mentioned table 3.10.

This table shows the details of the division (74 is divided by 21 ) using the hardware. Where “A” and “B” are two unsigned 6-bit integers.

21 in binary 010101.

74 in binary 1001010.

Hence, the remainder at the initial stages 000000 111100

The required content of each register is shown on each step.

This table is implemented below:

Iteration	Step	Quotient	Divisor	remainder
o	At the initial	0000	010101	000000 111100
After shifting the remainder left	0000	010101	000001 111000
1	1. remainder = remainder – divisor	0000	010101	110000 111000
2b. remainder < 0->divisor +, sll R, R0=0	0000	010101	000011 110000
2	1. remainder = remainder – divisor	0000	010101	110010 110000
2b. remainder < 0->divisor +, sll R, R0=0	0000	010101	000111 100000
3	1. remainder = remainder – divisor	0000	010101	110110 100000
2b. remainder < 0->divisor +, sll R, R0=0	0000	010101	001111 000000
4	1. remainder = remainder – divisor	0000	010101	111110 000000
2b. remainder < 0->divisor +, sll R, R0=0	0000	010101	011110 000000
5	1. remainder = remainder – divisor	0001	010101	001101 000000
2a. remainder >= 0->sll R, R0=0	0001	010101	011010 000001
6	1. remainder = remainder – divisor	0001	010101	001001 000001
2a. remainder >= 0->sll R, R0=0	0011	010101	010010 000011
Done	Shifting the left half of the remainder to the right.	0011	010101	001001 000011