Multiprecision Arithmetic
Multiprecision Addition and Subtraction
Carry and borrow propagation, sign handling, and why addition sets the baseline cost against which every other operation is measured.
Engineering / MathematicsMultiprecision Arithmetic2 min readKV-MATH-0506
Addition is the cheapest non-trivial multiprecision operation and the reference point for all the others. Its structure is simple; the complications are entirely in sign handling.
Unsigned addition
Unsigned addition of k-limb integers
- AlignTreat the shorter operand as zero-padded to the length of the longer.
- Add limbwiseAdd corresponding limbs plus the incoming carry.
- Propagate carryThe carry out is 1 exactly when the sum exceeds the base; with a power-of-two base this is a shift.
- Extend if neededA final carry adds one limb to the result.
Sign handling
Signed addition dispatches on the signs of the operands. This is where implementations most often go wrong.
| Signs | Action | Result sign |
|---|---|---|
| Same | Add magnitudes | Common sign |
| Different, |a| > |b| | Subtract |b| from |a| | Sign of a |
| Different, |a| < |b| | Subtract |a| from |b| | Sign of b |
| Different, |a| = |b| | Result is zero | Canonical zero, no sign |
Subtraction and borrow
Subtraction of magnitudes assumes the first operand is the larger, which the dispatch above guarantees. Borrow propagates exactly as carry does, and the result may have leading zero limbs that must be trimmed to restore normalisation.
Cost
This linear cost is the baseline. Algorithms are frequently designed to replace multiplications and divisions with additions and shifts for exactly this reason — see the binary GCD.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 1.2.2. Structural reference unverified: the source file was not available during authoring; chapter and section numbers are taken from the published edition and have not been checked against a physical copy.