Clemson University -- CPSC 231 -- Spring 2010
More Arithmetic
Multiplication (unsigned example on p. 128)
multiplying two 32-bit values gives up to a 64-bit product
we go from right to left across the multiplier digits in generating
partial products
we could use a double-length product register, and at each step we could
shift the multiplicand into the correct place for adding or not (just
like the normal paper and pencil approach)
e.g., 1111 4-bit multiplicand
x 0101 4-bit multiplier
---------
....1111
...0000. (. is a placeholder, equal to 0)
..1111..
.0000...
--------- need 8-bit adder
01001011
since one column is completely determined on the right at each step, we
could instead arrange to shift the partial sum to the right after each
add - this means we only need a 4-bit wide adder
carry accumulator MQ (multiplier/quotient) register
+---+-----------------+--------------+
==>| C : partial product : multiplier |
= +---+-----------------+--------------+
= + ^
= +-----------------+ test least significant bit
= | multiplicand | to see whether to add or not
= +-----------------+
= = MDR
=================
initially:
carry <- 0
accumulator <- 0
mq <- multiplier
mdr <- multiplicand
for( i = 1; i <= n; i++ ){
/* step i */
if( mq_bit[0] == 1 ){ (carry:accumulator) <- accumulator + mdr }
shift (carry:accumulator:mq) right one place
}
results:
high bits of product in accumulator
low bits of product in mq
e.g., 1111 4-bit multiplicand
x 0101 4-bit multiplier
--------
initially: C ACC MQ
0 0000 0101
MDR
1111
----------------------------------------------
step 1: 0 0000 0101
+ 1111 ^ add based on lsb=1
------
0 1111 0101
>> shift right
0 0111 1010
----------------------------------------------
step 2: 0 0111 1010
+ 0000 ^ no add based on lsb=0
------
0 0111 1010
>> shift right
0 0011 1101
----------------------------------------------
step 3: 0 0011 1101
+ 1111 ^ add based on lsb=1
------
1 0010 1101
>> shift right
0 1001 0110
----------------------------------------------
step 4: 0 1001 0110
+ 0000 ^ no add based on lsb=0
------
0 1001 0110
>> shift right
0 0100 1011
----------------------------------------------
SPARC has multiply step, mulscc, and uses a special Y register to hold
the multiplier/least significant part of product
(there are faster forms of multiplication hardware; a current processor
may only require 3-5 cycles for an integer multiply)
Division
instead of add-then-shift, division is implemented by shift-then-subtract
double-length dividend divided by single-length divisor yields single-length
quotient and single-length remainder
we work from left to right in generating the quotient
carry accumulator MQ (multiplier/quotient) register
+---+-----------------+--------------+
==>| 0 : double length dividend |
= +---+-----------------+--------------+
= - ^
= +-----------------+ set bit in quotient according
= | divisor | to whether subtraction of divisor
= +-----------------+ from C:ACC was successful or not
= = MDR
=================
initially:
carry <- 0
accumulator <- high bits of dividend (0s if dividend is single length)
mq <- low bits of dividend
mdr <- divisor
if( mdr == 0 ){ raise( DIVIDE_BY_ZERO__SIGNAL ); }
if( mdr <= accumulator ){ raise( QUOTIENT_OVERFLOW_SIGNAL ); }
for( i = 1; i <= n; i++ ){
/* step i */
shift (carry:accumulator:mq) left one place
(carry:accumulator) <- (carry:accumulator) - mdr /* subtract */
if( (carry:accumulator) is negative ){
mq_bit[0] <- 0
(carry:accumulator) <- (carry:accumulator) + mdr /* restore */
}else{
mq_bit[0] <- 1
}
}
results:
quotient in mq
remainder in accumulator
this is called restoring division, since the C:ACC must be restored to its
previous value if the result of a subtraction is negative
when the dividend is double-length, there is a special check (the value in
the MDR should be greater than the value in the ACC) to make sure that
the quotient won't overflow (e.g., consider 11111111 / 1)
when dividend is single-length, it is placed in the MQ and the ACC is set
to zero
e.g., 11001001 8-bit dividend
/ 1111 4-bit divisor
----------
initially: C ACC MQ
0 1100 1001
MDR
1111
(step 0: ( MDR != 0 ) and ( MDR > ACC ) so no exceptions)
-------------------------------------------------------------
step 1: 0 1100 1001
<< shift left
1 1001 001.
- 1111 subtract (== add 1 0001)
------
0 1010 0011
^ set to 1 since subtract successful
-------------------------------------------------------------
step 2: 0 1010 0011
<< shift left
1 0100 011.
- 1111 subtract (== add 1 0001)
------
0 0101 0111
^ set to 1 since subtract successful
-------------------------------------------------------------
step 3: 0 0101 0111
<< shift left
0 1010 111.
- 1111 subtract (== add 1 0001)
------
1 1011 1110
^ set to 0 since subtract unsuccessful
+ 1111 restoring add
------
0 1010 1110
-------------------------------------------------------------
step 4: 0 1010 1110
<< shift left
1 0101 110.
- 1111 subtract (== add 1 0001)
------
0 0110 1101
^ set to 1 since subtract successful
-------------------------------------------------------------
remainder | quotient
is in ACC | is in MQ
0110 | 1101
(there are faster forms of division, e.g., non-restoring)