Engineering / Mathematics — Integer Algorithms
Integer Addition and Subtraction
Multiprecision addition and subtraction: carry and borrow propagation, sign handling, and why both are linear.
Executive summary
Addition and subtraction of multiprecision integers are digit-wise operations with a carry or borrow chain, linear in the length of the longer operand.
The arithmetic is elementary; the complications are entirely in sign handling and in maintaining the representation invariants.
Learning objectives
- Implement carry propagation correctly.
- Reduce signed addition to unsigned addition and subtraction.
- Justify the linear cost bound.
01Unsigned addition
Multiprecision addition
non-negative a, b in base Ba + b- Let a have m digits and b have n digits, with m ≥ n. Set carry c = 0.
- For i from 0 to n−1: compute t = aᵢ + bᵢ + c; set rᵢ = t mod B and c = t div B.
- For i from n to m−1: compute t = aᵢ + c; set rᵢ = t mod B and c = t div B.
- If c is non-zero, append it as digit r_m.
- Strip any leading zeros and return r.
O(max(m, n)) digit operationsThe carry is always 0 or 1, because (B−1) + (B−1) + 1 = 2B − 1 < 2B. This bound is what allows the accumulator to be a single wide word and is why the loop needs no inner iteration.
02Subtraction and the borrow chain
Subtraction mirrors addition with a borrow in place of a carry, but requires the subtrahend to be no larger than the minuend. General signed subtraction is reduced to the unsigned case by comparing magnitudes first.
Compare magnitudes
Determine which operand is larger in absolute value; this decides the sign of the result.
Subtract smaller from larger
Run the unsigned borrow loop on the ordered pair.
Attach the sign
The result takes the sign of the operand with larger magnitude.
Normalise
Strip leading zeros produced by cancellation, and canonicalise zero.
03Signed operations as a case analysis
| Operation | Signs | Reduces to |
|---|---|---|
| a + b | same | Unsigned add, keep common sign |
| a + b | differ | Unsigned subtract smaller magnitude from larger |
| a − b | same | Unsigned subtract, sign from magnitude comparison |
| a − b | differ | Unsigned add, keep sign of a |
Both operations are Θ(ℓ) in the length of the longer operand: every digit must be examined in the worst case, and no more than a constant amount of work is done per digit. There is no faster method, since the output alone has that many digits.
04Frequently asked questions
Can the carry ever exceed 1?
Not in plain addition of two operands. It can in accumulating variants that add several products into one position, as in the inner loop of multiplication, where the accumulator must be wide enough to hold the running total.
Is subtraction ever implemented via complement rather than borrow?
Sometimes, by adding the complement and correcting. It avoids the magnitude comparison branch and can be faster on architectures where branches are costly, at the price of an extra pass.
Why is addition not sublinear?
Because the result has as many digits as the longer input, so simply writing the output takes linear time. No algorithm can beat the output size.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 41-42.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.