UNIVERSITY OF MASSACHUSETTS Dept of Electrical Computer Engineering Digital Computer Arithmetic CE666 Koren Part 7a 1 ECE 666 Part 7a Fast Division I Israel Koren Spring 2008 Copyright 2008 Koren Fast Division SRT Algorithm 2 approaches First conventional uses add subtract shift number of operations linearly proportional to word size n Second uses multiplication number of operations logarithmic in n but each step more complex SRT first approach Most well known division algorithm named after Sweeney Robertson and Tocher Speed up nonrestoring division n add subtracts allows 0 as a quotient digit no add subtract CE666 Koren Part 7a 2 Copyright 2008 Koren Modified Nonrestoring Division Problem full comparison of 2ri 1 with either D or D required Solution restricting D to normalized fraction 1 2 D 1 Region of 2ri 1 for which qi 0 reduced to CE666 Koren Part 7a 3 Copyright 2008 Koren Modified Nonrestoring SRT Advantage Comparing partial remainder 2ri 1 to 1 2 or 1 2 not D or D Binary fraction in two s complement representation 1 2 if and only if it starts with 0 1 1 2 if and only if it starts with 1 0 Only 2 bits of 2ri 1 examined not full comparison between 2ri 1 and D In some cases e g dividend X 1 2 shifted partial remainder needs an integer bit in addition to sign bit 3 bits of 2ri 1 examined Selecting quotient digit CE666 Koren Part 7a 4 Copyright 2008 Koren SRT Division Algorithm Quotient digits so selected ri D final remainder D Process starts with normalized divisor normalizing partial remainder by shifting over leading 0 s 1 s if positive negative Example 2ri 1 0 001xxxx x 0 1 2ri 1 1 2 set qi 0 2ri 0 01xxxx and so on 2ri 1 1 110xxxx 2ri 1 1 2 set qi 0 2ri 1 10xxxx SRT is nonrestoring division with normalized divisor and remainder CE666 Koren Part 7a 5 Copyright 2008 Koren Extensio n to Negative Divisors Example Dividend 5 16 Divisor D 0 1100 2 X 0 0101 2 3 4 Before correction Q 0 1001 minimal SD repr of Q 0 0111 minimal number of add subtracts After correction Q 0 0111 ulp 0 01102 3 8 final remainder 4 1 2 2 1 32 CE666 Koren Part 7a 6 Copyright 2008 Koren Example X 0 00111111 2 63 256 D 0 1001 2 9 16 Q 0 01112 7 16 not a minimal representation in SD form Conclusion Number of add subtracts can be reduced further CE666 Koren Part 7a 7 Copyright 2008 Koren Properties of SRT Based on simulations and analysis 1 Average shift 2 67 n 2 67 operations for dividend of length n 24 2 67 9 operations on average for n 24 2 Actual number of operations depends on divisor D smallest when 17 28 D 3 4 average shift of 3 If D out of range 3 5 D 3 4 SRT can be modified to reduce number of add subtracts 2 ways to modify SRT CE666 Koren Part 7a 8 Copyright 2008 Koren Two Modifications of SRT Scheme 1 In some steps during division If D too small use a multiple of D like 2D If D too large use D 2 Subtracting 2D D 2 instead of D equivalent to performing subtraction one position earlier later Motivation for Scheme 1 Small D may generate a sequence of 1 s in quotient one bit at a time with subtract operation per each bit Subtracting 2D instead of D equivalent to subtracting D in previous step may generate negative partial remainder generating sequence of 0 s as quotient bits while normalizing partial remainder Scheme 2 Change comparison constant K 1 2 if D outside optimal range allowed because ratio D K matters partial remainder compared to K not D CE666 Koren Part 7a 9 Copyright 2008 Koren Example Scheme 1 Using 2D Same as previous example X 0 00111111 2 63 256 D 0 1001 2 9 16 Q 0 10012 7 16 minimal SD representation CE666 Koren Part 7a 10 Copyright 2008 Koren Scheme 1 Using D 2 Large D one 0 in sequence of 1 s in quotient may result in 2 consecutive add subtracts instead of one Adding D 2 instead of D for last 1 before the single 0 equivalent to performing addition one position later may generate negative partial remainder Allows properly handling single 0 Then continue normalizing partial remainder until end of sequence of 1 s CE666 Koren Part 7a 11 Copyright 2008 Koren Example X 0 01100 2 3 8 D 0 11101 2 29 32 Correct 5 bit quotient Q 0 01101 2 13 32 single Applying basic SRT algorithm Q 0 10111 0 not handled efficiently Using D 2 multiple Q 0 10011 2 13 32 single 0 handled properly CE666 Koren Part 7a 12 Copyright 2008 Koren Implementing Scheme 1 Two adders needed One to add or subtract D Second to add subtract 2D if D too small starts with 0 10 in its true form or add subtract D 2 if D too large starts with 0 11 Output of primary adder used unless output of alternate adder has larger normalizing shift Additional multiples of D possible 3D 2 or 3D 4 Provide higher overall average shift about 3 7 but more complex implementation CE666 Koren Part 7a 13 Copyright 2008 Koren Modifying SRT Scheme 2 For K 1 2 ratio D K in optimal range 3 5 D 3 4 is 6 5 D K D 1 2 3 2 or 6 5 K D 3 2 K If D not in optimal range for K 1 2 choose a different comparison constant K Region 1 2 D 1 can be divided into 5 not equally sized sub regions Each has a different comparison constant Ki CE666 Koren Part 7a 14 Copyright 2008 Koren Division into Sub regions 4 bits of divisor examined for selecting comparison constant It has only 4 bits compared to 4 most significant bits of remainder Determination of sub regions for divisor and comparison constants numerical search Reason Both are binary fractions with small number of bits to simplify division algorithm CE666 Koren Part 7a 15 Copyright 2008 Koren Example X 0 00111111 2 63 256 D 0 1001 2 9 16 Appropriate comparison constant K2 7 16 0 01112 If remainder negative compare to two s complement of K2 1 10012 Q 0 1001 0 01112 7 16 minimal SD form CE666 Koren Part 7a 16 Copyright 2008 Koren