Knuth Algorithm D

What it is

Algorithm D (from TAOCP Vol. 2, §4.3.1) is the classic multi-precision long-division algorithm: divide a multi-limb dividend by a multi-limb divisor, one quotient digit at a time.

The tricky parts

• Normalization — left-shift both operands so the divisor’s top limb has its high bit set, improving the quotient-digit estimate.
• Quotient estimation — estimate q̂ from the top two limbs, then correct it (at most twice) so it’s exact.
• Add-back — rarely, the estimate is one too high and a correction add is needed.

Why it matters here

It’s the correctness baseline for emulated 64-bit division on 32-bit limbs in SIMD integer arithmetic. Faster methods like Barrett reduction are checked against it.