Engineering / Mathematics — Integer Algorithms
Integer Division with Remainder
Multiprecision division: the normalisation step, digit estimation, correction, and why division is harder to implement than multiplication.
Executive summary
Division is the most intricate of the basic multiprecision operations. Unlike addition and multiplication, each output digit must be estimated and then corrected, and the estimate is only good enough after a normalisation step that is easy to omit and hard to debug.
The asymptotic cost matches multiplication, but the constant and the implementation difficulty are both substantially higher.
Learning objectives
- Explain why normalisation is required for accurate digit estimation.
- Describe the estimate-and-correct loop and bound the correction.
- State the cost of division relative to multiplication.
01Why estimation is needed
Long division produces one quotient digit at a time, each requiring the largest digit q such that q · b does not exceed the current remainder prefix. With multiprecision b, testing every candidate is far too slow, so the digit is estimated from the leading digits and corrected.
The estimate uses the top two digits of the remainder prefix over the top digit of the divisor. Without normalisation this estimate can be badly wrong; with normalisation it is off by at most two.
Normalisation
Both operands are scaled by the same factor d = ⌊B / (b_{n−1} + 1)⌋ so that the leading digit of the divisor satisfies b_{n−1} ≥ B/2.
Scaling both operands leaves the quotient unchanged; the remainder is recovered by dividing by d at the end.
02The algorithm
Multiprecision division with remainder
a with m digits, b with n digits, b ≠ 0q and r with a = bq + r, 0 ≤ r < b- Normalise: scale a and b by d so the divisor's leading digit is at least B/2.
- For i from m−n down to 0:
- Estimate q̂ from the top two digits of the current remainder over the divisor's top digit.
- Clamp q̂ to at most B−1.
- Subtract q̂ · b shifted by i from the remainder.
- While the remainder is negative, add back b shifted by i and decrement q̂.
- Record q̂ as quotient digit i.
- Denormalise the remainder by dividing by d; return quotient and remainder.
O((m − n + 1) · n) digit operationsCorrection bound
After normalisation, the estimated quotient digit exceeds the true digit by at most 2.
Consequently the add-back loop executes at most twice per digit, and its cost is absorbed into the main bound.
03Cost and special cases
| Case | Cost | Method |
|---|---|---|
| Divisor one digit | O(m) | Single pass, no estimation needed |
| Divisor a power of the base | O(m) | Digit shift |
| Divisor a power of two | O(m) | Bit shift |
| General | O((m−n+1)n) | Full estimate-and-correct loop |
| Repeated division by fixed modulus | O(ℓ²) after setup | Barrett or Montgomery reduction |
The last row matters for modular arithmetic. When the same modulus is used repeatedly, as in exponentiation, precomputing a reciprocal turns each reduction into two multiplications, replacing division entirely. Montgomery reduction achieves the same and additionally avoids the final conditional subtraction.
04Frequently asked questions
Why scale so the leading digit exceeds B/2?
Because the accuracy of the two-digit-over-one-digit estimate depends on the divisor's leading digit being large relative to the base. If it is small, the omitted lower digits carry proportionally more weight and the estimate degrades badly.
Is the quotient digit ever underestimated?
No — the estimate from truncated leading digits is always at least the true digit, which is why correction only ever decrements. This one-sidedness is what makes the add-back loop simple.
Should division be avoided in modular arithmetic?
Yes, wherever the modulus is reused. Montgomery multiplication performs modular reduction with multiplications and shifts only, and is standard in cryptographic implementations for exactly this reason.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 45-48.
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.