Class Notes (809,484)
Canada (493,749)
CSC258H1 (46)


1 Page
Unlock Document

University of Toronto St. George
Computer Science
Steve Engels

 Multiplication cont.  Step #3 – iteration #4 o Booth’s algorithm  Check the last 2 digits of A: 111110  Devised as a way to take advantage of circuits where shifting is  Since digits are 10, subtract B (add -B) from the most cheaper than adding, or where space is at a premium significant digits of P:  Based on the premise that when multiplying by certain P 00000 11000 values (ex. 99) it can be easier to think of this operation -B +11110______ as a difference between two products P’ 11110 11000  Arithemtic shift P and A one bit to the right  Consider the shortcut method when multiplying a give demical value X by 9999: A  111111 P = 11111 01100  X*9999 = X*10000 – X*1  Step #3 – iteration #5 (final)  Now consider the equivalent problem in binary  Check the last 2 digits of A: 111111  X*001111 = X*010000 – X*1  Since digits are the same, do nothing to P  This idea is triggered on cases where two neighboring digits in  Arithemtic shift P and A one bit to the right an operand are different A  111111 P = 11111 10110  If digits at i and i–1 are 0 and 1, the multiplicand is  Step #4 A*B = 11011*00010 = 11111 10110 = P added to the result at position i  If idigits at i and i–1 are 1 and 0, the multiplicand is o Reflections on multiplcations subtracted from the result at position i  A popular version of this algorithim involves copying A into the  The result is always a value whose size is the sum of the sizes of lower bits of P, so that the testing and shifting only takes place in P the two multiplicands  In worst case this well be as efficient as an accumulator circit  Also good for maintaining the original value of A  Ex. 10111011*10101010  Multiplication isn’t as common an operation as addition or  In the average case its better than the worst case of
More Less

Related notes for CSC258H1

Log In


Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.