Computer Arithmetic

CS205 Computer Organization and Architecture

Acknowledgment

These materials are based on William Stallings' "Computer Organization and Architecture," 10th Edition, specifically Chapter 10.

Chapter 03: Computer Arithmetic

Objectives

After studying this chapter, you should be able to:
1. Understand the distinction between binary format number representation and algorithms for basic arithmetic operations.
2. Explain twos complement representation.
3. Present an overview of techniques for performing basic arithmetic operations in twos complement notation.
4. Understand the use of significant, base, and exponent in floating-point number representation.
5. Present an overview of the IEEE 754 standard for floating-point representation.
6. Understand key concepts related to floating-point arithmetic, including guard bits, rounding, subnormal numbers, underflow, and overflow.

Arithmetic & Logic Unit (ALU)

The ALU is the part of the computer that performs arithmetic and logical operations on data.
Other computer system elements primarily exist to bring data to the ALU for processing and to output the results.
The ALU is based on simple digital logic devices that store binary digits and perform simple Boolean logic operations.

ALU Inputs and Outputs

Control Signals: Control the operation performed by the ALU.
Operand Registers: Hold the input data for the ALU.
ALU: Performs the arithmetic or logical operation.
Result Registers: Store the output of the ALU.
Flags: Indicate the status of the ALU operation (e.g., overflow, zero).

Integer Representation

In the binary number system, arbitrary numbers can be represented with:
- Digits zero and one
- The minus sign (for negative numbers)
- The period, or radix point (for numbers with a fractional component)
For computer storage and processing, we only use binary digits (0,1) to represent numbers due to the lack of special symbols for the minus sign and radix point.

Sign-Magnitude Representation

Sign-magnitude representation is the simplest form that employs a sign bit to represent negative and positive integers.
Drawbacks:
- Addition and subtraction require considering the signs and relative magnitudes of the numbers.
- There are two representations of 0 (+0 and -0).
Due to these drawbacks, sign-magnitude representation is rarely used in implementing the integer portion of the ALU.
All of these alternatives involve treating the most significant (leftmost) bit in the word as a sign bit.
If the sign bit is 0, the number is positive.
If the sign bit is 1, the number is negative.

Characteristics of Twos Complement Representation and Arithmetic

Range: $-2^{n-1}$ through $2^{n-1} – 1$
Number of Representations of Zero: One
Negation: Take the Boolean complement of each bit of the corresponding positive number, then add 1 to the resulting bit pattern viewed as an unsigned integer.
Expansion of Bit Length: Add additional bit positions to the left and fill in with the value of the original sign bit.
Overflow Rule: If two numbers with the same sign (both positive or both negative) are added, then overflow occurs if and only if the result has the opposite sign.
Subtraction Rule: To subtract B from A, take the twos complement of B and add it to A.

Alternative Representations for 4-Bit Integers

Decimal Representation, Sign-Magnitude Representation, Twos Complement Representation, Biased Representation
The table provides a comparative overview of how different integer representation methods handle positive and negative numbers, including the representation of zero.

Use of a Value Box for Conversion Between Twos Complement Binary and Decimal

An eight-position two's complement value box with place values: -128, 64, 32, 16, 8, 4, 2, 1
Example:
- Convert binary 10000011 to decimal: $-128 + 2 + 1 = -125$
- Convert decimal -120 to binary: $-128 + 8 = -120$

Range Extension

The range of numbers that can be expressed is extended by increasing the bit length.
In sign-magnitude notation, this is accomplished by moving the sign bit to the new leftmost position and filling in with zeros.
This procedure will not work for twos complement negative integers.
The rule is to move the sign bit to the new leftmost position and fill in with copies of the sign bit.
For positive numbers, fill in with zeros, and for negative numbers, fill in with ones. This is called sign extension.

Fixed-Point Representation

The radix point (binary point) is fixed and assumed to be to the right of the rightmost digit.
Programmers can use the same representation for binary fractions by scaling the numbers so that the binary point is implicitly positioned at some other location.

Negation

Twos complement operation:
- Take the Boolean complement of each bit of the integer (including the sign bit).
- Treating the result as an unsigned binary integer, add 1.
The negative of the negative of that number is itself:
- +18 = 00010010 (twos complement)
  - Bitwise complement = 11101101
  - + 1
  - 11101110 = -18
- -18 = 11101110 (twos complement)
  - Bitwise complement = 00010001
  - + 1
  - 00010010 = +18

Negation Special Cases

Special Case 1:
- 0 = 00000000 (twos complement)
  - Bitwise complement = 11111111
  - Add 1 to LSB + 1
  - Result 100000000
  - Overflow is ignored, so: -0 = 0
Special Case 2:
- -128 = 10000000 (twos complement)
  - Bitwise complement = 01111111
  - Add 1 to LSB + 1
  - Result 10000000
  - So: -(-128) = -128
  - Monitor MSB (sign bit). It should change during negation.

Addition of Numbers in Twos Complement Representation

Examples:
- (-7) + (+5) = -2
- (-4) + (+4) = 0
- (+3) + (+4) = 7
- (-4) + (-1) = -5
- (+5) + (+4) results in Overflow
- (-7) + (-6) results in Overflow

Overflow Rule

If two numbers are added, and they are both positive or both negative, then overflow occurs if and only if the result has the opposite sign.

Subtraction Rule

To subtract one number (subtrahend) from another (minuend), take the twos complement (negation) of the subtrahend and add it to the minuend.

Subtraction of Numbers in Twos Complement Representation (M – S)

Examples of subtracting numbers represented in two's complement:
- 2 - 7 = -5
- 5 - 2 = 3
- -5 - 2 = -7
- 5 - (-2) = 7
- 7 - (-7) results in Overflow
- -6 - 4 results in Overflow

Block Diagram of Hardware for Addition and Subtraction

Diagram includes A Register, B Register, Adder, Complementer, Switch (select addition or subtraction), Overflow bit (OF).

Multiplication of Unsigned Binary Integers

Shows the multiplication of 1011 (11) by 1101 (13) resulting in 10001111 (143).

Hardware Implementation of Unsigned Binary Multiplication

Diagram includes Multiplicand, n-Bit Adder, Shift and Add Control Logic, Multiplier.
Example shows the step-by-step multiplication process with initial values and the add/shift operations.

Multiplication of Two Unsigned 4-Bit Integers Yielding an 8-Bit Result

$1011 \neq 1101$
Partial products are shifted and added to produce the final 8-bit result.

Floating-Point Representation Principles

With a fixed-point notation, it is possible to represent a range of positive and negative integers centered on or near 0.
By assuming a fixed binary or radix point, this format allows the representation of numbers with a fractional component as well.
Limitations:
- Very large numbers cannot be represented nor can very small fractions.
- The fractional part of the quotient in a division of two large numbers could be lost.

Typical 32-Bit Floating-Point Format

Format:
- Sign bit (1 bit), biased exponent (8 bits), significand (23 bits)
Examples:
- $1.1010001 \neq 2^{10100} = 0 10010011 10100010000000000000000 = 1.6328125 \neq 2^{20}$
- $-1.1010001 \neq 2^{10100} = 1 10010011 10100010000000000000000 = –1.6328125 \neq 2^{20}$
- $1.1010001 \neq 2^{-10100} = 0 01101011 10100010000000000000000 = 1.6328125 \neq 2^{-20}$
- $-1.1010001 \neq 2^{-10100} = 1 01101011 10100010000000000000000 = –1.6328125 \neq 2^{-20}$

Floating-Point Significand

The final portion of the word.
Any floating-point number can be expressed in many ways.
Normal number:
- The most significant digit of the significand is nonzero.
The following are equivalent, where the significand is expressed in binary form:
- $0.110 \neq 2^5$
- $110 \neq 2^2$
- $0.0110 \neq 2^6$

Expressible Numbers in Typical 32-Bit Formats

Twos Complement Integers:
- Number Line: Expressible Negative Numbers, Zero, Expressible Positive Numbers, Negative Overflow, Positive Overflow
Floating-Point Numbers:
- Number Line: Negative Overflow, Expressible Negative Numbers, Negative Underflow, Zero, Positive Underflow, Expressible Positive Numbers, Positive Overflow
- $2^{31} – 1$ , $2^{-127}$ , $-2^{31}$ , $-2^{-127}$ , $-(2 – 2^{-23}) * 2^{128}$ , $(2 - 2^{-23}) * 2^{128}$

IEEE Standard 754

The most important floating-point representation is defined.
The standard was developed to facilitate the portability of programs from one processor to another and to encourage the development of sophisticated, numerically oriented programs.
The standard has been widely adopted and is used on virtually all contemporary processors and arithmetic coprocessors.
IEEE 754-2008 covers both binary and decimal floating-point representations.

IEEE 754-2008

Defines the following different types of floating-point formats:
- Arithmetic format:
  - All the mandatory operations defined by the standard are supported by the format. The format may be used to represent floating-point operands or results for the operations described in the standard.
- Basic format:
  - This format covers five floating-point representations, three binary and two decimal, whose encodings are specified by the standard, and which can be used for arithmetic. At least one of the basic formats is implemented in any conforming implementation.
- Interchange format:
  - A fully specified, fixed-length binary encoding that allows data interchange between different platforms and that can be used for storage.

IEEE 754 Formats

binary32 format (single precision):
- sign bit (1 bit), biased exponent (8 bits), trailing significand field (23 bits)
binary64 format (double precision):
- sign bit (1 bit), biased exponent (11 bits), trailing significand field (52 bits)
binary128 format (quad precision):
- sign bit (1 bit), biased exponent (15 bits), trailing significand field (112 bits)

IEEE 754 Format Parameters

Table outlines the properties of binary32, binary64, and binary128 formats.
Parameters include Storage width, Exponent width, Exponent bias, Max/Min Exponent, approximate Normal number range, Trailing significand width, Number of exponents/fractions/values, and smallest/largest positive normal number and subnormal magnitude.

Additional Formats

Extended Precision Formats:
- Provide additional bits in the exponent (extended range) and in the significand (extended precision).
- Lessens the chance of a final result that has been contaminated by excessive roundoff error.
- Lessens the chance of an intermediate overflow aborting a computation whose final result would have been representable in a basic format.
- Affords some of the benefits of a larger basic format without incurring the time penalty usually associated with higher precision.
Extendable Precision Format:
- Precision and range are defined under user control.
- May be used for intermediate calculations, but the standard places no constraint or format or length.

Floating-Point Numbers and Arithmetic Operations

Floating Point Numbers:
- $X = Xs \neq B^{XE}$
- $Y = Ys \neq B^{YE}$
Arithmetic Operations:
- $X + Y = Xs \neq B^{XE - YE} + Ys \neq B^{YE}$ , if $XE <= Y_E$
- $X - Y = Xs \neq B^{XE - YE} - Ys \neq B^{YE}$ , if $XE <= Y_E$
- $X \neq Y = (Xs \neq Ys) \neq B^{XE + YE}$
- $X / Y = (Xs / Ys) \neq B^{XE - YE}$
Examples:
- $X = 0.3 \neq 10^2 = 30$
- $Y = 0.2 \neq 10^3 = 200$
- $X + Y = (0.3 \neq 10^{2-3} + 0.2) \neq 10^3 = 0.23 \neq 10^3 = 230$
- $X – Y = (0.3 \neq 10^{2-3} – 0.2) \neq 10^3 = (-0.17) \neq 10^3 = –170$
- $X \neq Y = (0.3 \neq 0.2) \neq 10^{2+3} = 0.06 \neq 10^5 = 6000$
- $X / Y = (0.3 / 0.2) \neq 10^{2-3} = 1.5 \neq 10^{-1} = 0.15$

Floating-Point Addition and Subtraction (Z = X ± Y)

Check if X = 0. If yes, return Y.
Check if Y = 0. If yes, return X.
Compare exponents. If exponents are not equal, increment the smaller exponent and shift the significand right.
Add or subtract signed significands.
If the significand is 0, return 0.
Normalize results: Shift significand left and decrement exponent until normalized.
Check for exponent underflow/overflow.
Round the result.
Check for significand overflow. If overflow, shift significand right and increment exponent.

Precision Considerations: Rounding

IEEE standard approaches:
- Round to nearest:
  - The result is rounded to the nearest representable number.
- Round toward +∞:
  - The result is rounded up toward plus infinity.
- Round toward -∞:
  - The result is rounded down toward negative infinity.
- Round toward 0:
  - The result is rounded toward zero.

Summary

ALU
Integer representation
- Sign-magnitude representation
- Twos complement representation
Range extension
Fixed-point representation
Floating-point representation
- Principles
- IEEE standard for binary floating-point representation
Integer arithmetic
- Negation
- Addition and subtraction
- Multiplication
Division
Floating-point arithmetic
- Addition and subtraction
- Multiplication and division
Precision consideration
IEEE standard for binary floating-point arithmetic