Integer Multiplication and Division COE 301 Computer Organization Prof. Muhamed Mudawar College of Computer Sciences and Engineering King Fahd University of Petroleum and Minerals Presentation Outline Unsigned Integer Multiplication Signed Integer Multiplication Faster Integer Multiplication Integer Division Integer Multiplication and Division in MIPS Integer Multiplication and Division COE 301 / ICS 233 Computer Organization KFUPM Muhamed Mudawar slide 2 Unsigned Integer Multiplication Paper and Pencil Example: Multiplicand Multiplier 11002 = 12 11012 = 13 1100 0000 1100 1100 Product Binary multiplication is easy 0 multiplicand = 0 1 multiplicand = multiplicand 100111002 = 156 n-bit multiplicand n-bit multiplier = (2n)-bit product

Accomplished via shifting and addition Consumes more time and more chip area than addition Integer Multiplication and Division COE 301 / ICS 233 Computer Organization KFUPM Muhamed Mudawar slide 3 Unsigned Sequential Multiplication Initialize Product = 0 Check each bit of the Multiplier If Multiplier bit = 1 then Product = Product + Multiplicand Rather than shifting the multiplicand to the left, Shift the Product to the Right Has the same net effect and produces the same result Minimizes the hardware resources One cycle per iteration (for each bit of the Multiplier) Addition and shifting can be done simultaneously Integer Multiplication and Division COE 301 / ICS 233 Computer Organization KFUPM Muhamed Mudawar slide 4 Unsigned Sequential Multiplier Initialize: HI = 0 Start Initialize: LO = Multiplier HI = 0, LO=Multiplier Final Product in HI and LO registers Repeat for each bit of Multiplier Multiplicand 32 bits =0 LO[0]? Carry, Sum = HI + Multiplicand 32 bits

32-bit ALU Carry =1 Sum HI, LO = Shift Right (Carry, Sum, LO) add 32 bits 32nd Repetition? shift right HI LO 64 bits Yes Control Done write LO[0] Integer Multiplication and Division COE 301 / ICS 233 Computer Organization KFUPM Muhamed Mudawar slide 5 No Sequential Multiplier Example Consider: 11002 11012 , Product = 100111002 4-bit multiplicand and multiplier are used in this example 4-bit adder produces a 4-bit Sum + Carry bit

Iteration 0 1 2 3 4 Initialize (HI = 0, LO = Multiplier) Multiplicand 1100 Product = HI, LO 0000 1101 + LO[0] = 1 => ADD Shift Right (Carry, Sum, LO) by 1 bit Carry 0 1100 1101 1100 0110 0110 1100 0011 0011 LO[0] = 0 => NO addition Shift Right (HI, LO) by 1 bit LO[0] = 1 => ADD Shift Right (Carry, Sum, LO) by 1 bit + Integer Multiplication and Division COE 301 / ICS 233 Computer Organization KFUPM

1111 0011 0111 1001 1100 + LO[0] = 1 => ADD Shift Right (Carry, Sum, LO) by 1 bit 0 1 1100 Muhamed Mudawar slide 6 0011 1001 1001 1100 Next . . . Unsigned Integer Multiplication Signed Integer Multiplication Faster Integer Multiplication Integer Division Integer Multiplication and Division in MIPS Integer Multiplication and Division COE 301 / ICS 233 Computer Organization KFUPM Muhamed Mudawar slide 7 Signed Integer Multiplication First attempt: Convert multiplier and multiplicand into positive numbers If negative then obtain the 2's complement and remember the sign Perform unsigned multiplication Compute the sign of the product If product sign < 0 then obtain the 2's complement of the product Drawback: additional steps to compute the 2's complement Better version:

Use the unsigned multiplication hardware When shifting right, extend the sign of the product If multiplier is negative, the last step should be a subtract Integer Multiplication and Division COE 301 / ICS 233 Computer Organization KFUPM Muhamed Mudawar slide 8 Signed Multiplication (Paper & Pencil) Case 1: Positive Multiplier Multiplicand Multiplier 11002 = -4 01012 = +5 11111100 Sign-extension 111100 Product 111011002 = -20 Case 2: Negative Multiplier Multiplicand Multiplier 11002 = -4 11012 = -3 11111100 Sign-extension 111100 00100 (2's complement of 1100) Product 000011002 = +12 Integer Multiplication and Division COE 301 / ICS 233 Computer Organization KFUPM

Muhamed Mudawar slide 9 Signed Sequential Multiplier ALU produces: 32-bit sum + sign bit Start Sign bit can be computed: HI = 0, LO = Multiplier No overflow: sign = sum[31] =1 If Overflow: sign = ~sum[31] 31 iterations: Sign, Sum = HI + Multiplicand Last iteration: Sign, Sum = HI Multiplicand Multiplicand 32 bits 32 bits 32-bit ALU sign sum =0 LO[0]? add, sub HI, LO = Shift Right (Sign, Sum, LO) 32 bits 32nd Repetition?

shift right HI LO 64 bits Yes Control write Done LO[0] Integer Multiplication and Division COE 301 / ICS 233 Computer Organization KFUPM Muhamed Mudawar slide 10 No Signed Multiplication Example Consider: 11002 (-4) 11012 (-3), Product = 000011002 Check for overflow: No overflow Extend sign bit Last iteration: add 2's complement of Multiplicand Iteration 0 1 2 3 4 Initialize (HI = 0, LO = Multiplier) Multiplicand 1100 Product = HI, LO 0000 1101 +

LO[0] = 1 => ADD Shift Right (Sign, Sum, LO) by 1 bit Sign 1 1100 1101 1100 1110 0110 1100 1111 0011 LO[0] = 0 => NO addition Shift Right (Sign, HI, LO) by 1 bit LO[0] = 1 => ADD + Shift Right (Sign, Sum, LO) by 1 bit 1100 LO[0] = 1 => SUB (ADD 2's compl) 0100 + 1 1101 1001 0 Shift Right (Sign, Sum, LO) by 1 bit Integer Multiplication and Division COE 301 / ICS 233 Computer Organization KFUPM 1011 0011

0001 1001 0000 1100 Muhamed Mudawar slide 11 Next . . . Unsigned Integer Multiplication Signed Integer Multiplication Faster Integer Multiplication Integer Division Integer Multiplication and Division in MIPS Integer Multiplication and Division COE 301 / ICS 233 Computer Organization KFUPM Muhamed Mudawar slide 12 Faster Multiplier Suppose we want to multiply two numbers A and B Example on 4-bit numbers: A = a3 a2 a1 a0 and B = b3 b2 b1 b0 Step 1: AND (multiply) each bit of A with each bit of B Requires n2 AND gates and produces n2 product bits Position of aibj = (i+j). For example, Position of a2b3 = 2+3 = 5 a3b0 a2b0 a1b0 a3b1 a2b1 a1b1 a0b1 a3b2 a2b2

a1b2 a0b2 a2b3 a1b3 a0b3 AB a3b3 Integer Multiplication and Division COE 301 / ICS 233 Computer Organization KFUPM Muhamed Mudawar slide 13 a0b0 Adding the Partial Products Step 2: Add the partial products The partial products are shifted and added to compute the product P The partial products can be added in parallel Different implementations are possible A3 A2 A1 A0 B3 B2 B1 B0

A3B0 A2B0 A1B0 A0B0 A3B1 A2B1 A1B1 A0B1 A3B2 A2B2 A1B2 A0B2 A3B3 A2B3 A1B3 A0B3 P6 P5 P4 P3

4-bit Multiplicand 4-bit Multiplier Partial Products are shifted and added 8-bit Product P7 Can be added in parallel Integer Multiplication and Division COE 301 / ICS 233 Computer Organization KFUPM Muhamed Mudawar slide 14 P2 P1 P0 4-bit 4-bit Binary Multiplier 16 AND gates, Three 4-bit adders, a half-adder, and an OR gate B3 B2 A3 A2 A1 A0 A3 A2 A1 A0 B1 A3 A2 A1 A0 0 carry P7

P6 A3 A2 A1 A0 0 4-bit Adder Half Adder B0 carry carry 4-bit Adder 4-bit Adder P5 P4 P3 P2 Integer Multiplication and Division COE 301 / ICS 233 Computer Organization KFUPM Muhamed Mudawar slide 15 P1 P0 Carry Save Adders A n-bit carry-save adder produces two n-bit outputs n-bit partial sum bits and n-bit carry bits All the n bits of a carry-save adder work in parallel The carry does not propagate as in a carry-propagate adder This is why a carry-save is faster than a carry-propagate adder Useful when adding multiple numbers (as in multipliers) a31 b31 cout

+ s31 ... a1 b1 a0 b0 + + s1 s0 a31 b31 c31 cin Carry-Propagate Adder Integer Multiplication and Division COE 301 / ICS 233 Computer Organization KFUPM + a1 b1 c1 ... c'31 s'31 a0 b0 c0 + + c'1 s'1 c'0 s'0

Carry-Save Adder Muhamed Mudawar slide 16 Carry-Save Adders in a Multiplier ADD the product bits vertically using Carry-Save adders Full Adder adds three vertical bits Half Adder adds two vertical bits Each adder produces a partial sum and a carry Use Carry-propagate adder for final addition a3b0 a2b0 a1b0 a3b1 a2b1 a1b1 a0b1 a3b2 a2b2 a1b2 a0b2 a2b3 a1b3 a0b3 AB a3b3

Integer Multiplication and Division COE 301 / ICS 233 Computer Organization KFUPM Muhamed Mudawar slide 17 a0b0 Carry-Save Adders in a Multiplier Step 1: Use carry save adders to add the partial products Reduce the partial products to just two numbers Step 2: Use carry-propagate adder to add last two numbers a3b1 a2b2 a3b0 a2b1 a1b3 FA a2b0 a1b1 a1 b2 FA a1b0 a0b1 a0b0 a0 b2 FA HA Carry Save a3b2 a2b3 a0 b3

FA HA FA FA FA FA HA P6 P5 P4 P3 HA Carry Save Adder a3b3 P7 Integer Multiplication and Division COE 301 / ICS 233 Computer Organization KFUPM Carry Propagate Adder P2 Muhamed Mudawar slide 18 P1 P0

Summary of a Fast Multiplier A fast n-bit n-bit multiplier requires: n2 AND gates to produce n2 product bits in parallel Many adders to perform additions in parallel Uses carry-save adders to reduce delays Higher cost (more chip area) than sequential multiplier Higher performance (faster) than sequential multiplier Integer Multiplication and Division COE 301 / ICS 233 Computer Organization KFUPM Muhamed Mudawar slide 19 Next . . . Unsigned Integer Multiplication Signed Integer Multiplication Faster Integer Multiplication Integer Division Integer Multiplication and Division in MIPS Integer Multiplication and Division COE 301 / ICS 233 Computer Organization KFUPM Muhamed Mudawar slide 20 Unsigned Division (Paper & Pencil) =10011 19 Quotient 2 Divisor 10112 110110012 = 217 -1011 10 101 1010 10100 Dividend -1011 = Quotient Divisor 1001 + Remainder 10011 217 = 19 11-1011 +8

Dividend Check how big a number can be subtracted, creating a bit of the quotient on each attempt Binary division is done via shifting and subtraction 10002 = 8 Remainder Integer Multiplication and Division COE 301 / ICS 233 Computer Organization KFUPM Muhamed Mudawar slide 21 Sequential Division Uses two registers: HI and LO Initialize: HI = Remainder = 0 and LO = Dividend Shift (HI, LO) LEFT by 1 bit (also Shift Quotient LEFT) Shift the remainder and dividend registers together LEFT Has the same net effect of shifting the divisor RIGHT Compute: Difference = Remainder Divisor If (Difference 0) then Remainder = Difference Set Least significant Bit of Quotient Observation to Reduce Hardware: LO register can be also used to store the computed Quotient Integer Multiplication and Division COE 301 / ICS 233 Computer Organization KFUPM Muhamed Mudawar slide 22 Sequential Division Hardware Initialize: Start HI = 0, LO = Dividend

Results: 1. HI = Remainder LO = Quotient Shift (HI, LO) Left Difference = HI Divisor 0 32 bits sub 32-bit ALU 32nd Repetition? sign Difference write 32 bits <0 2. HI = Remainder = Difference Set least significant bit of LO Divisor HI Difference? LO 32 bits Yes

Done Control shift left set lsb Integer Multiplication and Division COE 301 / ICS 233 Computer Organization KFUPM Muhamed Mudawar slide 23 No Unsigned Integer Division Example Example: 11102 / 01002 (4-bit dividend & divisor) Result Quotient = 00112 and Remainder = 00102 4-bit registers for Remainder and Divisor (4-bit ALU) Iteration 0 1 2 3 4 HI LO Divisor Difference Initialize 0000 1110 0100 Shift Left, Diff = HI - Divisor

0001 1100 0100 <0 0011 1000 0100 <0 Shift Left, Diff = HI - Divisor 0111 0000 0100 0011 HI = Diff, set lsb of LO 0011 0001 Shift Left, Diff = HI - Divisor 0110 0010 0100

0010 HI = Diff, set lsb of LO 0010 0011 Diff < 0 => Do Nothing Shift Left, Diff = HI - Divisor Diff < 0 => Do Nothing Integer Multiplication and Division COE 301 / ICS 233 Computer Organization KFUPM Muhamed Mudawar slide 24 Signed Integer Division Simplest way is to remember the signs Convert the dividend and divisor to positive Obtain the 2's complement if they are negative Do the unsigned division Compute the signs of the quotient and remainder Quotient sign = Dividend sign XOR Divisor sign Remainder sign = Dividend sign Negate the quotient and remainder if their sign is negative Obtain the 2's complement to convert them to negative Integer Multiplication and Division COE 301 / ICS 233 Computer Organization KFUPM Muhamed Mudawar slide 25 Signed Integer Division Examples 1. Positive Dividend and Positive Divisor Example: +17 / +3 Quotient = +5 Remainder = +2 2. Positive Dividend and Negative Divisor Example: +17 / 3 Quotient = 5

Remainder = +2 3. Negative Dividend and Positive Divisor Example: 17 / +3 Quotient = 5 Remainder = 2 4. Negative Dividend and Negative Divisor Example: 17 / 3 Quotient = +5 Remainder = 2 The following equation must always hold: Dividend = Quotient Divisor + Remainder Integer Multiplication and Division COE 301 / ICS 233 Computer Organization KFUPM Muhamed Mudawar slide 26 Next . . . Unsigned Integer Multiplication Signed Integer Multiplication Faster Integer Multiplication Integer Division Integer Multiplication and Division in MIPS Integer Multiplication and Division COE 301 / ICS 233 Computer Organization KFUPM Muhamed Mudawar slide 27 Integer Multiplication in MIPS Multiply instructions mult Rs, Rt multu Rs, Rt Signed multiplication Unsigned multiplication 32-bit multiplication produces a 64-bit Product

$0 $1 Separate pair of 32-bit registers .. HI = high-order 32-bit of product $31 LO = low-order 32-bit of product Multiply Divide MIPS also has a special mul instruction mul Rd, Rs, Rt Rd = Rs Rt HI Copy LO into destination register Rd Useful when the product is small (32 bits) and HI is not needed Integer Multiplication and Division COE 301 / ICS 233 Computer Organization KFUPM Muhamed Mudawar slide 28 LO Integer Division in MIPS Divide instructions div Rs, Rt divu Rs, Rt

Signed division Unsigned division Division produces quotient and remainder $0 $1 Separate pair of 32-bit registers .. HI = 32-bit remainder $31 LO = 32-bit quotient Multiply Divide If divisor is 0 then result is unpredictable Moving data from HI, LO to MIPS registers mfhi Rd (Rd = HI) mflo Rd (Rd = LO) Integer Multiplication and Division COE 301 / ICS 233 Computer Organization KFUPM Muhamed Mudawar slide 29 HI LO Integer Multiply and Divide Instructions Instruction mult multu Rs, Rt

Rs, Rt Meaning Format HI, LO = Rs s Rt Op = 0 Rs Rt 0 0 0x18 HI, LO = Rs u Rt Op = 0 Rs Rt 0 0 0x19 mul Rd, Rs, Rt Rd = Rs s Rt 0x1c

Rs Rt Rd 0 2 div Rs, Rt HI, LO = Rs /s Rt Op = 0 Rs Rt 0 0 0x1a divu Rs, Rt HI, LO = Rs /u Rt Op = 0 Rs Rt

0 0 0x1b mfhi Rd Rd = HI Op = 0 0 0 Rd 0 0x10 mflo Rd Rd = LO Op = 0 0 0 Rd 0 0x12

mthi Rs HI = Rs Op = 0 Rs 0 0 0 0x11 mtlo Rs LO = Rs Op = 0 Rs 0 0 0 0x13 s = Signed multiplication, u = Unsigned multiplication /s = Signed division, /u = Unsigned division

NO arithmetic exception can occur Integer Multiplication and Division COE 301 / ICS 233 Computer Organization KFUPM Muhamed Mudawar slide 30 String to Integer Conversion Consider the conversion of string "91052" into an integer '9' '1' '0' '5' '2' How to convert the string into an integer? Initialize: sum = 0 Load each character of the string into a register Check if the character is in the range: '0' to '9' Convert the character into a digit in the range: 0 to 9 Compute: sum = sum * 10 + digit Repeat until end of string or a non-digit character is encountered To convert "91052", initialize sum to 0 then sum = 9, then 91, then 910, then 9105, then 91052 Integer Multiplication and Division COE 301 / ICS 233 Computer Organization KFUPM Muhamed Mudawar slide 31 String to Integer Conversion Function #----------------------------------------------------------# str2int: Convert a string of digits into unsigned integer # Input: $a0 = address of null terminated string # Output: $v0 = unsigned integer value #----------------------------------------------------------str2int: li $v0, 0 # Initialize: $v0 = sum = 0 li $t0, 10 # Initialize: $t0 = 10 L1: lb $t1, 0($a0) # load $t1 = str[i] blt $t1, '0', done # exit loop if ($t1 < '0') bgt $t1, '9', done # exit loop if ($t1 > '9') addiu $t1, $t1, -48 # Convert character to digit mul

$v0, $v0, $t0 # $v0 = sum * 10 addu $v0, $v0, $t1 # $v0 = sum * 10 + digit addiu $a0, $a0, 1 # $a0 = address of next char j L1 # loop back done: jr $ra # return to caller Integer Multiplication and Division COE 301 / ICS 233 Computer Organization KFUPM Muhamed Mudawar slide 32 Integer to String Conversion Convert an unsigned 32-bit integer into a string How to obtain the decimal digits of the number? Divide the number by 10, Remainder = decimal digit (0 to 9) Convert decimal digit into its ASCII representation ('0' to '9') Repeat the division until the quotient becomes zero Digits are computed backwards from least to most significant Example: convert 2037 to a string Divide 2037/10 quotient = 203 remainder = 7 char = '7' Divide 203/10 quotient = 20 remainder = 3 char = '3' Divide 20/10 quotient = 2 remainder = 0 char = '0' Divide 2/10 quotient = 0 remainder = 2 char = '2' Integer Multiplication and Division COE 301 / ICS 233 Computer Organization KFUPM Muhamed Mudawar slide 33 Integer to String Conversion Function #---------------------------------------------------------# int2str: Converts an unsigned integer into a string # Input: $a0 = value, $a1 = buffer address (12 bytes) # Output: $v0 = address of converted string in buffer

#---------------------------------------------------------int2str: li $t0, 10 # $t0 = divisor = 10 addiu $v0, $a1, 11 # start at end of buffer sb $zero, 0($v0) # store a NULL character L2: divu $a0, $t0 # LO = value/10, HI = value%10 mflo $a0 # $a0 = value/10 mfhi $t1 # $t1 = value%10 addiu $t1, $t1, 48 # convert digit into ASCII addiu $v0, $v0, -1 # point to previous byte sb $t1, 0($v0) # store character in memory bnez $a0, L2 # loop if value is not 0 jr $ra # return to caller Integer Multiplication and Division COE 301 / ICS 233 Computer Organization KFUPM Muhamed Mudawar slide 34