= Packed restoring division
{title2=$p_k=bQ_k+R_k$}
For an $n$-bit unsigned dividend $a$ and positive divisor $b$, read the dividend <bits> from most to least significant. If the processed prefix is $p$, maintain $p=bQ+R$ with $0\le R<b$. Appending <bit> $d$ gives trial <remainder> $T=2R+d$; append <quotient> <bit> $[T\ge b]$ and replace the <remainder> by $T-b[T\ge b]$. This preserves the <quotient>–<remainder> identity.
The old dividend and new <quotient> can share one $n$-bit <processor register>: after $k$ iterations its value is $(a2^k\bmod2^n)+Q_k$, where $Q_k<2^k$. The shifted dividend occupies the upper positions and the accumulated <quotient> occupies the lower positions, so no information is overwritten. The high <processor register> holds $R_k$. For an $n$-bit dividend the next trial <remainder> is no larger than the next prefix, hence fits in $n$ <bits> through the final iteration. This last bound is specific to the dividend width; it must not be assumed for unrestricted multiword dividends.
Back to article page
