Arithmetic for Computers

3.1 Introduction

Computer Arithmetic: Arithmetic performed with finite binary representations and a limited number of bits.

Limited Precision: The restriction that a computer can represent only a finite subset of all possible numbers.

Arithmetic Logic Unit (ALU): Hardware that performs integer arithmetic and logical operations.

---

3.2 Addition and Subtraction

1) Binary Addition and Subtraction

Binary Addition: Addition performed bit by bit from least significant to most significant, propagating carries to higher positions.

Two's-Complement Subtraction: Subtraction performed by negating the second operand and adding it to the first.

$$A-B=A+(-B)$$

2) Overflow

Overflow: A condition in which an arithmetic result cannot be represented with the available number of bits.

Signed Addition Overflow: Overflow occurs when operands with the same sign produce a result with the opposite sign.

Operation	Operand conditions	Overflow result
$A+B$	$A \ge 0$, $B \ge 0$	Result $<0$
$A+B$	$A<0$, $B<0$	Result $\ge 0$
$A-B$	$A \ge 0$, $B<0$	Result $<0$
$A-B$	$A<0$, $B \ge 0$	Result $\ge 0$

Unsigned Overflow: A result outside the range $0$ to $2^n-1$, commonly detected using a carry or borrow condition.

Exception: An unexpected internal event that interrupts normal instruction execution and transfers control to an exception handler.

---

3.3 Multiplication

1) Binary Multiplication

Multiplicand: The value being multiplied.

Multiplier: The value that determines which shifted copies of the multiplicand are added.

Product: The result of multiplication.

Shift-and-Add Multiplication: A multiplication algorithm that examines each multiplier bit, conditionally adds the multiplicand, and shifts for the next bit position.

2) Product Size

Double-Length Product: Multiplying two $n$-bit values can require up to $2n$ bits to represent the exact result.

$$n\text{-bit operand} \times n\text{-bit operand} \rightarrow 2n\text{-bit product}$$

Signed Multiplication: Multiplication that accounts for operand signs and produces a two's-complement result.

Multiply Overflow: A condition in which the full product cannot be represented in the destination width.

3) MIPS Multiplication

mult: A MIPS instruction that multiplies two signed 32-bit register values and produces a 64-bit result.

multu: A MIPS instruction that multiplies two unsigned 32-bit register values and produces a 64-bit result.

Hi and Lo: Special MIPS registers that hold the upper and lower halves of a multiplication result.

mfhi and mflo: MIPS instructions that copy values from the Hi and Lo registers into general-purpose registers.

---

3.4 Division

1) Binary Division

Dividend: The value being divided.

Divisor: The value by which the dividend is divided.

Quotient: The whole-number result of division.

Remainder: The amount left after division.

$$\text{Dividend} = (\text{Quotient}\times\text{Divisor})+\text{Remainder}$$

Shift-and-Subtract Division: A division algorithm that repeatedly compares or subtracts a shifted divisor and generates quotient bits.

2) Signed Division

Signed Quotient: A quotient whose sign is negative only when the dividend and divisor have different signs.

Signed Remainder: A remainder that normally has the same sign as the dividend and satisfies the division identity.

3) MIPS Division

div: A MIPS instruction that divides signed integers, placing the quotient in Lo and the remainder in Hi.

divu: A MIPS instruction that performs unsigned integer division.

Division by Zero: An invalid operation that software must prevent or the architecture must handle according to its defined behavior.

---

3.5 Floating Point

1) Floating-Point Representation

Floating Point: A finite representation of real numbers using a sign, significand, and exponent.

Scientific Notation: A representation consisting of a significand multiplied by a base raised to an exponent.

$$1.xxxxx_2\times2^e$$

Normalized Number: A nonzero floating-point number whose significand has a standard leading digit.

Significand: The precision-bearing part of a floating-point number.

Exponent: The part that determines the scale or magnitude of a floating-point number.

2) IEEE 754

IEEE 754: The standard defining floating-point formats, arithmetic, rounding, and special values.

Biased Exponent: An exponent stored after adding a fixed bias so that negative and positive exponents can be represented as unsigned bit patterns.

$$\text{Stored exponent}=\text{Actual exponent}+\text{Bias}$$

Single Precision: A 32-bit IEEE 754 format with 1 sign bit, 8 exponent bits, and 23 fraction bits.

Double Precision: A 64-bit IEEE 754 format with 1 sign bit, 11 exponent bits, and 52 fraction bits.

Format	Sign	Exponent	Fraction	Bias
Single precision	1 bit	8 bits	23 bits	127
Double precision	1 bit	11 bits	52 bits	1023

For a normalized IEEE 754 binary number:

$$(-1)^S\times(1+F)\times2^{E-\text{Bias}}$$

Hidden Leading Bit: The implicit leading 1 of a normalized binary significand, which provides one additional bit of precision.

3) Special Values

Positive and Negative Zero: Values represented with an exponent and fraction of zero and distinguished by the sign bit.

Subnormal Number: A very small nonzero number represented without the implicit leading 1.

Infinity: A special value representing a result beyond the largest finite magnitude, such as certain overflow results or division of a nonzero value by zero.

Not a Number (NaN): A special value representing an undefined or unrepresentable result, such as $0/0$.

Floating-Point Overflow: A condition in which a result's magnitude is too large for the selected floating-point format.

Floating-Point Underflow: A condition in which a nonzero result's magnitude is too small to be represented normally.

4) Floating-Point Addition

Exponent Alignment: Shifting the smaller significand until both operands have the same exponent.

Floating-Point Addition: An operation that aligns exponents, adds significands, normalizes the result, and rounds it.

1. Compare the exponents.
2. Shift the smaller significand.
3. Add the significands.
4. Normalize the result.
5. Round and check for overflow or underflow.

5) Floating-Point Multiplication

Floating-Point Multiplication: An operation that adds exponents, multiplies significands, determines the sign, normalizes, and rounds the result.

$$\text{Result sign}=\text{Sign}_A\oplus\text{Sign}_B$$ $$\text{Result exponent}=E_A+E_B-\text{Bias}$$

6) Rounding and Accuracy

Rounding: Mapping an exact result to the nearest representable floating-point value according to a selected rounding mode.

Round to Nearest, Ties to Even: The default IEEE 754 rounding mode, which chooses the nearest value and resolves an exact tie by selecting the value with an even least significant bit.

Guard Bit: The first extra bit retained beyond the stored fraction during an intermediate calculation.

Round Bit: The second extra bit retained to help determine the rounded result.

Sticky Bit: A bit indicating whether any nonzero bits were discarded beyond the round bit.

Unit in the Last Place (ulp): The distance between adjacent representable floating-point values at a particular magnitude.

Relative Error: The absolute error divided by the magnitude of the exact value.

$$\text{Relative error} = \frac{|\text{Approximation}-\text{Exact value}|} {|\text{Exact value}|}$$

---

3.6 Parallelism and Computer Arithmetic: Subword Parallelism

Data-Level Parallelism: Performing the same operation on multiple data elements simultaneously.

Subword Parallelism: Dividing a wide register into smaller fields and applying one instruction to all fields in parallel.

Single Instruction, Multiple Data (SIMD): A processing model in which one instruction performs the same operation on multiple data elements.

Packed Data: Multiple small values stored together in one register for SIMD processing.

---

3.7 Real Stuff: SSE and AVX in x86

Streaming SIMD Extensions (SSE): x86 instruction-set extensions that provide SIMD operations using 128-bit vector registers.

Advanced Vector Extensions (AVX): x86 instruction-set extensions that expand vector processing capabilities and support wider vector registers.

Vector Register: A register that stores multiple data elements to be processed by one SIMD instruction.

Vector Width: The total number of bits processed by a vector instruction at one time.

---

3.8 Going Faster: Subword Parallelism and Matrix Multiply

Matrix Multiplication: An operation in which each output element is calculated as the dot product of a matrix row and a matrix column.

$$C_{ij} = \sum_k A_{ik}B_{kj}$$

Vectorized Matrix Multiplication: Matrix multiplication implemented with SIMD instructions so that multiple products and additions are performed together.

Data Reuse: Reusing values already loaded into registers or cache to reduce memory-access cost.

Arithmetic Intensity: The amount of arithmetic work performed relative to the amount of data transferred from memory.

---

3.9 Fallacies and Pitfalls

1) Shift and Division

Shift-Division Fallacy: A logical right shift is equivalent to division by a power of two only for unsigned values; signed division requires attention to sign extension and rounding direction.

Arithmetic Right Shift: A right shift that copies the sign bit into newly opened upper positions.

2) Floating-Point Properties

Nonassociativity of Floating-Point Addition: Floating-point addition can produce different results when operands are grouped in a different order.

$$(a+b)+c\ne a+(b+c)$$

Parallel Floating-Point Pitfall: Parallel evaluation may change the order of operations and therefore produce a slightly different floating-point result from sequential evaluation.

Floating-Point Equality Pitfall: Values produced through floating-point calculations should not always be compared for exact equality because rounding errors can accumulate.

3) Finite Precision

Finite-Precision Pitfall: Computer arithmetic approximates mathematical arithmetic because every representation has limited range and precision.

Numerical Analysis: The study of algorithms that produce accurate and stable approximations under finite-precision arithmetic.

---

3.10 Concluding Concepts

Integer Arithmetic: Exact within its representable range but subject to overflow when a result exceeds that range.

Floating-Point Arithmetic: A finite approximation of real-number arithmetic with a large range but limited precision.

Representation Determines Meaning: A bit pattern has no inherent meaning; its interpretation depends on the operation and data type applied to it.

Arithmetic Trade-off: Computer arithmetic balances range, precision, hardware cost, performance, and energy consumption.

Parallel Arithmetic: SIMD improves performance by applying one arithmetic instruction to multiple data elements, but floating-point results can depend on evaluation order.