Multiprecision Arithmetic
Multiprecision Division and Remainder
Knuth's division algorithm, the normalisation step that makes quotient digit estimation reliable, and why division carries a larger constant than multiplication.
Engineering / MathematicsMultiprecision Arithmetic2 min readKV-MATH-0509
Division is the most intricate of the basic multiprecision operations. The difficulty is not the outer loop but the inner step: estimating each quotient digit accurately enough that correction is cheap.
The structure
Long division proceeds one quotient limb at a time, from the most significant end. At each step the algorithm estimates the next quotient digit, multiplies it back, subtracts, and corrects if the estimate was too large.
Classical division with remainder
- NormaliseShift both operands left so the divisor's leading limb has its top bit set. This is what makes the estimate accurate.
- EstimateDivide the leading two limbs of the current remainder by the leading limb of the divisor.
- Multiply and subtractMultiply the whole divisor by the estimate and subtract from the remainder.
- CorrectIf the subtraction went negative, decrement the estimate and add the divisor back.
- DenormaliseShift the remainder right by the normalisation amount. The quotient is unaffected.
Why normalisation matters
Signs and conventions
Division of signed integers admits more than one convention, and they disagree on negative operands. Which one is in force must be known.
| Convention | Remainder sign | Typical use |
|---|---|---|
| Truncated | Follows the dividend | Most programming languages |
| Floored | Follows the divisor | Mathematical convention |
| Euclidean | Always non-negative | Number-theoretic work |
Cost
Classical division is O(k * l) in the limb counts, with a constant noticeably larger than multiplication because of the estimate-and-correct inner loop. Fast division via Newton iteration achieves O(M(n)) but only pays off for large operands.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 1.2.4. 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.