Next: Division Up: Arithmetic and Logical Operations Previous: Addition and Subtraction

# Multiplication

## The 64 bit HI/LO algorithm may also be implemented in SAL: ```# # Compute the product of two 32 bit integers with 64 bit result. # # Multiply two 32-bit numbers, V1 and V2, to produce a 64 bit result in # the HI/LO registers. The algorithm is high-school math: # # A B # x C D # ------ # AD || BD # AC || CB || 0 # # where A and B are the high and low short words of V1, C and D are the short # words of V2, AD is the product of A and D, and V1 || V2 is (V1 << 16) + V2. # We need to be careful not to overflow. C code is given in comments. # .data LO: .word # least significant word of result HI: .word # most siginificant word of result V1: .word 0x20000000 # number to multiply V2: .word 0x40000000 # number to multiply B: .word # lo 16 bits of V1 A: .word # hi 16 bits of V1 D: .word # lo 16 bits of V2 C: .word # hi 16 bits of V2 Mask: .word 0xFFFF # 16 bit mask X: .word Y: .word .text __start: srl A,V1,16 # a = (v1 >> 16) & 0xffff; and B,V1,Mask # b = v1 & 0xffff; srl C,V2,16 # c = (v2 >> 16) & 0xffff; and D,V2,Mask # d = v2 & 0xffff; mul LO,B,D # LO = b * d; mul HI,A,C # HI = a * c; mul X,B,C # x = a * d + c * b; mul Y,A,D add X,X,Y srl Y,LO,16 # y = ((LO >> 16) & 0xffff) + x; add Y,Y,X and LO,LO,Mask # LO = (LO & 0xffff) sll X,Y,16 # LO = LO | ((y & 0xffff) << 16); or LO,LO,X srl Y,Y,16 # HI += (y >> 16) & 0xffff; add HI,HI,Y put HI put ' ' put LO done ``` The algorithm works without modification for a negative multiplier and a positive multiplicand. It can be extended to work for 2's complement integers. To multiply two negative numbers or a positive multiplier and negative multiplicand, two approaches are possible: Convert negative numbers to positive, multiply positive numbers and then convert result to correct sign. Sign extend both numbers to 64 bits and perform 64 bit multiplication. The correct result will be found in the least significant 64 bits of the product. An example of method #2 applied to 4-bit 2's complement integers is shown below. The 4-bit integers 1101 (-3) and 0110 (6) are sign extended to 8 bits before multiplication. The correct result (-18) is found in the rightmost 8 bits. ``` 11111101 (-3) x 00000110 (6) ---------- 00000000 11111101 11111101 00000000 00000000 00000000 00000000 + 00000000 ----------------- 11101110 (-18)```

Next: Division Up: Arithmetic and Logical Operations Previous: Addition and Subtraction

CS 301 Class Account
Thu Nov 5 12:25:05 AST 1998