Arithmetic Operations

Addition

Binary Addition

Binary addition follows these rules:

• 0 + 0 = 0
• 0 + 1 = 1
• 1 + 0 = 1
• 1 + 1 = 10 (carry 1)

Half Adder and Full Adder

• Half adder: adds two one-bit binary numbers
• Full adder: adds two one-bit binary numbers together with the carry from the lower position

Multi-Bit Adders

• Ripple carry adder: computes the carry bit by bit, which is slower
• Carry look-ahead adder: computes all the bits at once, which is fast but has a complex circuit
• Carry select adder: precomputes the carries, balancing speed against complexity

Subtraction

Two’s Complement Representation

Negative numbers are usually represented in two’s complement in a computer:

• Sign-magnitude: the highest bit is the sign and the remaining bits are the magnitude
• Ones’ complement: positive numbers are unchanged, negative numbers have every bit inverted
• Two’s complement: positive numbers are unchanged, negative numbers have their ones’ complement plus 1

Two’s Complement Addition

Subtraction can be carried out as two’s complement addition:

A − B = A + (−B)

where (−B) is the two’s complement of B.

Overflow Detection

• Sign overflow: two positive numbers add up to a negative result, or two negative numbers add up to a positive result
• Carry overflow: there is a carry out of the most significant bit but the sign bit is unchanged

Multiplication

Shift-and-Add Multiplication

The basic multiplication algorithm:

1. Shift the multiplicand left
2. Decide whether to add the multiplicand based on each bit of the multiplier
3. Accumulate to obtain the result

Booth’s Algorithm

An improved multiplication algorithm:

• Reduces the number of partial products
• Works through shifts and additions or subtractions
• Applies to signed multiplication

Hardware Multipliers

• Array multiplier: computes all the partial products in parallel
• Tree multiplier: uses a tree structure to reduce the latency
• Pipelined multiplier: splits multiplication into several stages

Division

Restoring Division

The basic division algorithm:

1. Shift the dividend left
2. Attempt to subtract the divisor
3. If the result is positive, the quotient bit is 1; otherwise restore and the quotient bit is 0
4. Repeat until every bit has been processed

Non-Restoring Division

An improved division algorithm:

• Does not restore the value that was subtracted
• Compensates through adjustments in the following steps
• Removes the restoring step and improves the efficiency

Hardware Dividers

• Array divider: processes several bits in parallel
• Iterative divider: improves the precision by iterating many times
• Table lookup divider: uses a lookup table to speed up the computation

Floating-Point Arithmetic

Floating-Point Representation

The IEEE 754 standard:

• Single precision: 32 bits (1 sign bit, 8 exponent bits, 23 mantissa bits)
• Double precision: 64 bits (1 sign bit, 11 exponent bits, 52 mantissa bits)

Floating-Point Addition

1. Exponent alignment: make the exponents of the two numbers equal
2. Mantissa addition: add the aligned mantissas
3. Normalization: adjust the result into the standard form
4. Rounding: handle the precision according to the rounding mode

Floating-Point Multiplication

1. Exponent addition: add the two exponents
2. Mantissa multiplication: multiply the two mantissas
3. Normalization: adjust the result into the standard form
4. Rounding: handle the precision according to the rounding mode

Operation Optimisation

Parallel Operations

• SIMD instructions: single instruction, multiple data
• Vector operations: process several data items at once
• Parallel algorithms: several functional units work together

Pipelining

• Operation pipeline: splits an operation into several stages
• Instruction pipeline: overlaps the execution of several instructions
• Superscalar technique: issues several instructions at the same time

Cache Optimisation

• Data locality: exploits temporal and spatial locality
• Prefetching: loads data that will probably be needed, ahead of time
• Write buffering: reduces the latency of write operations

Performance Metrics

Operation Speed

• MIPS: millions of instructions per second
• FLOPS: floating-point operations per second
• Latency: the time taken to complete a single operation

Precision Control

• Rounding modes: toward zero, toward infinity, to nearest, and so on
• Precision loss: the change in precision during a computation
• Error analysis: the estimate of the accumulated error

Practical Applications

Scientific Computing

• Large-scale matrix operations
• Numerical integration and differentiation
• Signal processing and image processing

Financial Computing

• High-precision numerical computation
• Risk assessment and modelling
• Real-time trading systems

Graphics Processing

• 3D graphics rendering
• Physics simulation
• Game engine computation

---

Glossary