Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
CS4203/EE4363
Arithmetic for Computers • Operations on integers • Addition and subtraction • Multiplication and division • Dealing with overflow • Floating-point real numbers • Representation and operations Addition/Subtraction in Binary with Negative Number Decimal: 0 - 1 = -1 Hexadecimal: 0 - 1 = -1 Binary: 0000 + 0001 =1111 Decimal: -1 + 1 = 0 Hexadecimal: -1 + 1 = 0 Binary: 1111 + 0001 =0000 Decimal: -1 - 1 = -2 Hexadecimal: -1 - 1 = -2 Binary: 1111 - 0001 =1110 2’s-Complement Integers • Negation rule: • Invert bits and add 1 • Some properties: • Only one representation for 0 • Exactly as many positive numbers as negative numbers • Slight asymmetry – there is one negative number with no positive counterpart 2’s Complement Addition Integer Addition Example: 7 + 6 • Overflow if result out of range • Adding +ve and –ve operands, no overflow • Adding two +ve operands • Overflow if result sign is 1 • Adding two –ve operands • Overflow if result sign is 0 Integer Subtraction • Add negation of second operand • Example: 7 – 6 = 7 + (–6) +7: 0000 0000 … 0000 0111 –6: 1111 1111 … 1111 1010 +1: 0000 0000 … 0000 0001 • Overflow if result out of range • Subtracting two +ve or two –ve operands, no overflow • Subtracting +ve from –ve operand • Overflow if result sign is 0 • Subtracting –ve from +ve operand • Overflow if result sign is 1 Problems with Finite Math • Finite size of representation: • Digital circuit cannot be arbitrarily large. • Overflow detection – easy to determine when the number becomes too large. • Represent negative numbers: • Unique representation of 0. -4 0 4 8 12 16 20 0000 0100 1000 1100 10000 10100 Infinite universe of integers ∞-∞ 4-bit numbers Overflow and Finite Universe . . .1111 0000 0001 0010 0011 0100 0101 . . . Decrease Increase Infinite universe of integers No overflow ∞-∞ 0000 Forbidden fence 1000 00011111 1001 Finite Universe of 4-bit binary integers 0010 0011 0100 0101 0110 0111 1010 1011 1100 1101 1110 In cr ea se D ec re as e Dealing with Overflow • Some languages (e.g., C) ignore overflow • Use MIPS addu, addui, subu instructions • Other languages (e.g., Ada, Fortran) require raising an exception • Use MIPS add, addi, sub instructions • On overflow, invoke exception handler • Save PC in exception program counter (EPC) register • Jump to predefined handler address • mfc0 (move from coprocessor reg) instruction can retrieve EPC value, to return after corrective action Arithmetic for Multimedia • Graphics and media processing operates on vectors of 8- bit and 16-bit data • Use 64-bit adder, with partitioned carry chain • Operate on 8×8-bit, 4×16-bit, or 2×32-bit vectors • SIMD (single-instruction, multiple-data) • Saturating operations • On overflow, result is largest representable value • c.f. 2s-complement modulo arithmetic • E.g., clipping in audio, saturation in video 32-bit Ripple-Carry Adder FA0 FA1 FA2 FA31 a0 b0 c0 = 0 a1 b1 a2 b2 a31 b31 s0 s1 s2 c32 (discard) s31c31 c2 c1 c32 c31 . . . c2 c1 0 a31 . . . a2 a1 a0 + b31 . . . b2 b1 b0 s31 . . . s2 s1 s0 Speeding Up the Adder 16-bit ripple carry adder a0-a15 b0-b15 c0 = 0 s0-s15 16-bit ripple carry adder a16-a31 b16-b31 0 16-bit ripple carry adder a16-a31 b16-b31 1 M ul tip le xe r s16-s31 0 1 This is a carry-select adder N-bit Adder Design Options Type of adder Time complexity (delay) Space complexity (size) Ripple-carry O(N) O(N) Carry-lookahead O(log2N) O(N log2N) Carry-skip O(√N) O(N) Carry-select O(√N) O(N) Multiplication Multiplication 1000 × 1001 1000 0000 0000 1000 1001000 Length of product is the sum of operand lengths multiplicand multiplier product Combinational Multiplier A0