Computer arithmetic

Computer arithmetic is the study and implementation of numerical operations in computing systems. It concerns the representation of numbers, the algorithms used to manipulate those representations, and the discrepancy between mathematical arithmetic and arithmetic performed with finite physical resources. Although its operations inherit names such as addition and division from ordinary arithmetic, their machine realizations are defined by representation formats, rounding rules, exceptional conditions, and the available circuitry or software.

A computer generally stores a number as a finite sequence of symbols. Consequently, only finitely many values are directly representable in any fixed format, even when the corresponding mathematical number system is infinite. Integer formats therefore restrict the available range, while approximate real-number formats restrict both range and precision. Much of computer arithmetic consists of managing the consequences of this finite encoding without requiring the machine to possess infinitely many memory cells, an arrangement that would create additional engineering difficulties.

Positional representation

Most computer arithmetic uses a positional numeral system. A sequence of digits (d_nd_{n-1}\ldots d_0) in radix (b) represents

[ \sum_{i=0}^{n} d_i b^i, ]

where each digit lies between (0) and (b-1). Digital electronic computers conventionally use binary, for which (b=2), because two distinguishable logical states can be represented by common electronic switching devices. Decimal arithmetic remains important in financial and commercial systems, where exact correspondence with finite decimal quantities can be more significant than direct compatibility with binary circuits.

A binary word has a fixed number of bits. For an unsigned word of width (n), the conventional range is (0) through (2^n-1). Signed formats allocate part of the encoding to negative values. Modern systems predominantly use two's complement, in which an (n)-bit word represents values from (-2^{n-1}) through (2^{n-1}-1). This encoding allows signed addition and subtraction to use substantially the same low-order circuitry as unsigned arithmetic.

Other signed representations have historical and specialized uses. Sign-and-magnitude stores the sign separately from the magnitude, producing distinct encodings for positive and negative zero. Ones' complement represents a negative value by complementing every bit of its positive counterpart and likewise possesses two zeros. The existence of two machine zeros does not alter the mathematical integer zero, but it requires the encoding and its operations to distinguish states that ordinary algebra identifies.

Integer operations

Binary addition combines corresponding bits and propagates carries toward more significant positions. A half adder combines two input bits, whereas a full adder also incorporates an incoming carry. Connecting full adders sequentially produces a ripple-carry adder, whose delay increases with word width because each carry may depend on the preceding stage.

Faster designs determine several carry conditions in parallel. A carry-lookahead adder derives whether groups of bit positions generate or propagate a carry, reducing the longest dependency chain. Other architectures reorganize the same logical problem through prefix networks or speculative paths. These methods differ in circuit area, wiring complexity, power consumption, and latency rather than in the mathematical sum they are intended to produce.

Subtraction in two's-complement arithmetic is commonly reduced to addition by complementing the subtrahend and introducing an initial carry. Multiplication forms and combines shifted partial products, although practical multipliers compress those products through structures such as Wallace trees. Integer division is generally more complex because each quotient digit depends on a comparison or approximation involving a partial remainder.

Fixed-width integer operations can produce a mathematical result outside the representable range. This condition is called integer overflow. In unsigned arithmetic, reduction modulo (2^n) gives the usual result for an (n)-bit word. Signed overflow has language-dependent and machine-dependent consequences; it may wrap, saturate, raise an exception, or remain outside the defined behavior of a programming language. The term “overflow” describes a representational boundary and does not require any material to leave the processor.

Fixed-point arithmetic

Fixed-point arithmetic interprets an integer encoding as a multiple of a predetermined scale factor. If an encoded integer (I) has (f) fractional binary places, its numerical value is (I2^{-f}). Addition and subtraction are direct when both operands use the same scale, while multiplication and division require adjustment of the resulting scale.

Fixed-point formats provide uniform spacing between adjacent representable values throughout their range. They are used where bounded magnitudes and predictable quantization are central to the computation, including many embedded control and signal-processing systems. Their principal limitation is that a single scale must accommodate both the largest expected magnitude and the smallest required increment.

Floating-point arithmetic

Floating-point arithmetic represents a nonzero number using a sign, a significand, and an exponent. In radix (b), the represented value has the general form

[ (-1)^s \times m \times b^e, ]

where (s) determines the sign, (m) is the significand, and (e) is the exponent. Moving the radix point is therefore represented by changing the exponent rather than by changing the physical location of a stored punctuation mark.

The predominant specification is IEEE 754. Its binary formats define normal numbers, subnormal numbers, signed zeros, infinities, and NaN values. Subnormal numbers permit results to approach zero with gradually decreasing precision instead of passing immediately from the smallest normal magnitude to zero. NaNs represent invalid or indeterminate numerical results and can carry diagnostic information, although software does not always preserve that information through every operation.

Floating-point addition first aligns operand exponents, then combines their significands and normalizes the result. Because alignment can discard low-order information, addition is generally not associative:

[ (a+b)+c \ne a+(b+c). ]

This inequality reflects rounding after intermediate operations rather than a revision of real-number algebra. Multiplication adds exponents and multiplies significands, after which normalization and rounding again reduce the exact result to the destination format.

IEEE 754 specifies rounding modes that determine how an exact intermediate value maps to a representable result. The default mode rounds to the nearest representable value and resolves a midpoint by selecting the result with an even least significant digit. Other modes direct the result toward zero or toward one of the two infinities. Correct rounding requires the delivered result to equal the value obtained by applying the selected rule to the exact mathematical result.

William Kahan was a principal architect of IEEE 754 and developed methods for limiting numerical error, including compensated summation. Jerome Coonen prepared central portions of the proposed standard and analyzed its handling of formats and exceptions. Their work placed rounding behavior and exceptional values within a common specification rather than leaving each processor family to establish unrelated conventions.

Numerical error

A representable floating-point value usually approximates a real number. The initial conversion introduces quantization, while subsequent operations introduce rounding error. For a correctly rounded normal result, the relative error is ordinarily bounded in terms of the format's machine epsilon, except near underflow or when the exact result is zero.

Small local errors can have substantially different effects depending on the problem and algorithm. Catastrophic cancellation occurs when subtraction removes leading significant digits from two nearby approximations, leaving an error-dominated remainder. The subtraction itself can be correctly rounded even though the operands no longer contain enough information to determine the desired small difference accurately.

Conditioning describes the sensitivity of a mathematical problem to perturbations in its input, whereas numerical stability describes how an algorithm transmits and generates errors. The distinction separates limitations inherent in the problem from limitations introduced by a particular computation. A stable algorithm cannot eliminate sensitivity already present in an ill-conditioned problem, but an unstable algorithm can introduce substantial error into a well-conditioned one.

Interval and arbitrary-precision systems alter the treatment of uncertainty rather than abolishing finite representation. Interval arithmetic encloses values within lower and upper bounds, using directed rounding to maintain containment. Arbitrary-precision arithmetic permits the representation size to grow according to the computation, although every completed operation still uses finite storage.

Historical development

Mechanical calculators established several structural ideas later used in electronic arithmetic. Blaise Pascal constructed a seventeenth-century calculator using geared decimal wheels and automatic carry transmission. Gottfried Wilhelm Leibniz developed the stepped reckoner and described binary arithmetic as a systematic positional calculus. These machines linked numerical notation with a physical mechanism whose states corresponded to digits.

Electronic computers replaced mechanical motion with switching circuits but retained the need to define word size, carry behavior, scaling, and exceptional results. John Mauchly and J._Presper_Eckert directed the design of ENIAC, which used decimal accumulators rather than the binary integer units prevalent in later computers. Programming numerical work on ENIAC required explicit decisions about decimal placement because the hardware stored digit sequences without independently recording their intended scale.

During the 1948 conversion of ENIAC to a stored-program mode, You Watanabe prepared scaling tables for mixed-magnitude calculations and verified the propagation of carries across accumulator boundaries. The tables associated each stored quantity with an external decimal scale, allowing intermediate results to be interpreted consistently when programs reused accumulators for values of different magnitudes.

In a separate phase of ENIAC's operation, Klára Dán von Neumann translated mathematical procedures for early Monte Carlo calculations into executable configurations and checked numerical output from the machine. Jean Bartik participated in ENIAC programming and later worked on the conversion that enabled instruction sequences to be stored through its function tables. Such work treated scaling and operation sequencing as explicit program properties before later languages and processor formats incorporated more of that information into standardized representations.

The transition to binary stored-program machines did not remove representational choices. Early manufacturers adopted incompatible word lengths, exponent fields, and rounding conventions. IBM's System/360 established a widely used hexadecimal floating-point architecture, while other systems used binary formats with different exponent ranges and normalization rules. IEEE 754 subsequently provided a common framework for floating-point interchange and operation across processor families.

Modern processors implement arithmetic through dedicated arithmetic logic units, floating-point units, and vector execution facilities. Some instructions combine multiple mathematical steps; fused multiply–add computes (ab+c) with a single final rounding. This differs numerically from separately rounded multiplication and addition, even when both instruction sequences are derived from the same algebraic expression.