Address 8: Binary Multiplication Division

Presentation Transcript

Address 8: Binary Multiplication & Division Today's points: Addition/Subtraction Multiplication Division Reminder: begin at an opportune time task 3

2's Complement – Signed Numbers 0000 two = 0 ten 0000 0001 two = 1 ten … 0111 1111 two = 2 31 - 1 1000 0000 two = - 2 31 1000 0000 0001 two = - (2 31 – 1) 1000 0000 0010 two = - (2 31 – 2) … 1111 1110 two = - 2 1111 two = - 1 Why is this portrayal ideal? Consider the total of 1 and - 2 … . we get - 1 Consider the entirety of 2 and - 1 … . we get +1 This arrangement can straightforwardly experience expansion with no changes! Each number speaks to the amount x 31 - 2 31 + x 30 2 30 + x 29 2 29 + … + x 1 2 1 + x 0 2 0

Alternative Representations The accompanying two (natural) portrayals were disposed of in light of the fact that they required extra transformation ventures before math could be performed on the numbers sign-and-greatness: the most huge piece speaks to +/ - and the rest of the bits express the extent one's supplement: - x is spoken to by upsetting every one of the bits of x Both portrayals above experience the ill effects of two zeroes

Addition and Subtraction Addition is like decimal number-crunching For subtraction, just include the negative number – thus, subtract A-B includes invalidating B's bits, including 1 and A

Overflows For an unsigned number, flood happens when the last convey (1) can't be obliged For a marked number, flood happens when the most huge piece is not the same as each piece to one side when the aggregate of two positive numbers is a negative outcome when the entirety of two negative numbers is a positive outcome The whole of a positive and negative number will never flood MIPS permits addu and subu directions that work with unsigned numbers and never hail a flood – to distinguish the flood, different guidelines should be executed

Multiplication Example Multiplicand 1000 ten Multiplier x 1001 ten - 1000 0000 1000 - Product 1001000 ten In each progression multiplicand is moved next piece of multiplier is analyzed (additionally a moving stride) if this bit is 1, moved multiplicand is added to the item

HW Algorithm 1 In each progression multiplicand is moved next piece of multiplier is inspected (likewise a moving stride) if this bit is 1, moved multiplicand is added to the item

HW Algorithm 2 32-bit ALU and multiplicand is untouched the total continues moving comfortable stride, number of bits in item + multiplier = 64, subsequently, they share a solitary 64-bit enlist

Notes The past calculation likewise works for marked numbers (negative numbers in 2's supplement frame) We can likewise change over negative numbers to positive, duplicate the sizes, and change over to negative if signs differ The result of two 32-bit numbers can be a 64-bit number - consequently, in MIPS, the item is spared in two 32-bit registers

MIPS Instructions mult $s2, $s3 processes the item and stores it in two "inside" registers that can be alluded to as hello there and lo mfhi $s0 moves the incentive in greetings into $s0 mflo $s1 moves the incentive in lo into $s1 Similarly for multu

Fast Algorithm The past calculation requires a clock to guarantee that the prior option has finished before moving This calculation can rapidly set up most data sources – it then needs to sit tight for the aftereffect of each add to proliferate down – quicker on the grounds that no clock is included - Note: high transistor cost

Division 1001 ten Quotient Divisor 1000 ten | 1001010 ten Dividend - 1000 10 101 1010 - 1000 10 ten Remainder At each progression, move divisor right and contrast it and current profit if divisor is bigger, move 0 as the following piece of the remainder if divisor is littler, subtract to get new profit and move 1 as the following piece of the remainder

Division 1001 ten Quotient Divisor 1000 ten | 1001010 ten Dividend 0001001010 0000001010 100000000000  0001000000 00001000000000001000 Quo: 0 000001 0000010 000001001 At each progression, move divisor right and contrast it and current profit if divisor is bigger, move 0 as the following piece of the remainder if divisor is littler, subtract to get new profit and move 1 as the following piece of the remainder

Divide Example Divide 7 ten (0000 0111 two ) by 2 ten (0010 two )

Divide Example Divide 7 ten (0000 0111 two ) by 2 ten (0010 two )

Hardware for Division A correlation requires a subtract; the indication of the outcome is analyzed; if the outcome is negative, the divisor must be included back

Efficient Division

Divisions including Negatives Simplest arrangement: change over to positive and modify sign later Note that various arrangements exist for the condition: Dividend = Quotient x Divisor + Remainder +7 div +2 Quo = Rem = - 7 div +2 Quo = Rem = +7 div - 2 Quo = Rem = - 7 div - 2 Quo = Rem =

Divisions including Negatives Simplest arrangement: change over to positive and conform sign later Note that numerous arrangements exist for the condition: Dividend = Quotient x Divisor + Remainder +7 div +2 Quo = +3 Rem = +1 - 7 div +2 Quo = - 3 Rem = - 1 +7 div - 2 Quo = - 3 Rem = +1 - 7 div - 2 Quo = +3 Rem = - 1 Convention: Dividend and leftover portion have a similar sign Quotient is negative if signs differ These standards satisfy the condition above

Title Bullet