Clemson University -- CPSC 231 -- Fall 2009 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 ------ 0 1010 0011 ^ set to 1 since subtract successful ------------------------------------------------------------- step 2: 0 1010 0011 << shift left 1 0100 011. - 1111 subtract ------ 0 0101 0111 ^ set to 1 since subtract successful ------------------------------------------------------------- step 3: 0 0101 0111 << shift left 0 1010 111. - 1111 subtract ------ 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 ------ 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)