UNIVERSITY OF MASSACHUSETTS Dept of Electrical Computer Engineering Digital Computer Arithmetic ECE 666 Part 3 Sequential Algorithms for Multiplication and Division CE666 Koren Part 3 1 Israel Koren Spring 2008 Copyright 2008 Koren Sequential Multiplication X A multiplier and multiplicand X xn 1xn 2 x0 A an 1an 2 a1a0 xn 1 an 1 sign digits sign magnitude or complement methods Sequential algorithm n 1 steps Step j multiplier bit xj examined product j xjA added 0 to P previously accumulated partial product P 0 1 Multiplying by 2 shift by one position to the right alignment necessary since the weight of xj 1 is double that of xj CE666 Koren Part 3 2 Copyright 2008 Koren Sequential Multiplication Proof Repeated substitution 2 n 1 If both operands positive xn 1 an 1 0 The result is a product consisting of 2 n 1 bits for its magnitude CE666 Koren Part 3 3 Copyright 2008 Koren Number of product bits Maximum value of U when A and X are maximal Last term positive for n 3 therefore 2n 2 bits required to represent the value 2n 1 bits with the sign bit Signed magnitude numbers multiply two magnitudes and generate the sign separately positive if both operands have the same sign and negative otherwise CE666 Koren Part 3 4 Copyright 2008 Koren Negative operands For two s and one s complement distinguish between multiplication with a negative multiplicand A and multiplication with a negative multiplier X If only multiplicand is negative no need to change the previous algorithm only add some multiple of a negative number that is represented in either two s or one s complement CE666 Koren Part 3 5 Copyright 2008 Koren Multiplication Example A negative two s complement X positive 4 bits Product 7 bits including sign bit Registers are 4 bits long a double length register required for storing the final product Vertical line separates most from least significant half each stored in a single length register Bits in least significant half not used in the add operation CE666 Koren Part 3 6 Copyright 2008 Koren Least significant half of product Only 3 bit positions are utilized least significant bit position unused not necessarily final arrangement The 3 bits can be stored in 3 rightmost positions Sign bit of second register can be set in two ways 1 Always set sign bit to 0 irrespective of sign of the product since it is the least significant part of result 2 Set sign bit equal to sign bit of first register Another possible arrangement Use all four bit positions in second register for the four least significant bits of the product Use the rightmost two bit positions in the first register Insert two copies of sign bit into remaining bit positions CE666 Koren Part 3 7 Copyright 2008 Koren Negative Multiplier Two s Complement Each bit considered separately sign bit with negative weight treated differently than other bits Two s complement numbers If sign bit of multiplier is ignored X A is the desired product if xn 1 1 a correction is necessary The multiplicand A is subtracted from the most significant half of U CE666 Koren Part 3 8 Copyright 2008 Koren Negative Multiplier Example Multiplier and multiplicand negative numbers in two s complement In correction step subtraction of multiplicand is performed by adding its two s complement CE666 Koren Part 3 9 Copyright 2008 Koren Negative Multiplier One s Complement and 0 If xn 1 1 start with P A this takes care of the second correction term xn 1 ulp n 1 A At the end of the process subtract the first correction term xn 1 2 A CE666 Koren Part 3 10 Copyright 2008 Koren Negative Multiplier Example Product of 5 and 3 one s complement As in previous example subtraction of first correction term adding its one s complement Unlike previous example one s complement has to be expanded to double size using the sign digit a double length binary adder is needed CE666 Koren Part 3 11 Copyright 2008 Koren Sequential Division Division the most complex and time consuming of the four basic arithmetic operations In general result of division has two components Given a dividend X and a divisor D generate a quotient Q and a remainder R such that X Q D R with R D Assumption X D Q R positive If a double length product is available after a multiply and we wish to allow the use of this result in a subsequent divide then X may occupy a double length register while all other operands stored in single length registers CE666 Koren Part 3 12 Copyright 2008 Koren Overflow Divide by zero Q largestn number stored in a single length 1 register 2 for a register with n bits n 1 1 X 2 D otherwise an overflow indication must be produced by arithmetic unit Condition can be satisfied by preshifting either X or D or both Preshifting is simple when operands are floating point numbers 2 D 0 otherwise a divide by zero indication must be generated No corrective action can be taken when D 0 CE666 Koren Part 3 13 Copyright 2008 Koren Division Algorithm Fractions Assumption dividend divisor quotient remainder are fractions divide overflow condition is X D Obtain Q 0 q1 qm m n 1 sequence of subtractions and shifts Step i remainder is compared to divisor D if remainder larger quotient bit qi 1 otherwise 0 ith step ri 2ri 1 qiD i 1 2 m ri is the new remainder and ri 1 is the previous remainder r0 X qi determined by comparing 2ri 1 to D the most complicated operation in division process CE666 Koren Part 3 14 Copyright 2008 Koren Division Algorithm Proof The remainder in the last step is rm and repeated substitution of the basic expression yields m Substituting r0 X and dividing both sides by 2 results in m m hence rm2 X Q D as required True final remainder is R rm2 CE666 Koren Part 3 15 Copyright 2008 Koren Division Example 1 Fractions X 0 100000 2 1 2 D 0 110 2 3 4 Dividend occupies double length reg X D satisfied Generation of 2r0 overflow An extra bit position in the arithmetic unit needed Final result Q 0 101 2 5 8 m 3 no 3 R rm 2 r32 1 4 2 1 32 Quotient and final remainder satisfy X Q D R 5 8 3 4 1 32 16 32 1 2 Precise quotient is the infinite binary fraction 2 3 0 1010101 CE666 Koren Part 3 16 Copyright 2008 Koren Division Algorithm Integers Same procedure Previous equation rewritten XF DF QF RF fractions 2n 2 Dividing by 2 yields n 1 The condition X 2 D becomes XF DF X 01000002 32 D 0110 n 1 2 6 Overflow condition X 2 D is tested by comparing the most significant half of X 0100 to D 0110 The results of the division are Q 01012 5 and R 00102 2 In final step the true remainder R is generated n 1 no need to