Class Notes
(809,484)

Canada
(493,749)

University of Toronto St. George
(42,822)

Computer Science
(743)

CSC258H1
(46)

Steve Engels
(31)

Lecture

# mar04ce.docx

Unlock Document

University of Toronto St. George

Computer Science

CSC258H1

Steve Engels

Winter

Description

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