From Knuth’s The Art of Computer Programming, Volume 2: Seminumerical Algorithms 3rd edition, pg. 272.

Given nonnegative integers $u = (u_{m+n-1} \dots u_1u_0)_b$ and $v = (v_{n-1}\dots v_1v_0)_b,$ where $u_{n-1} \neq 0$ and $n \gt 1,$ we can form the radix-$b$ quotient $\lfloor u/v \rfloor = (q_mq_{m-1}\dots q_0)_b$ and the remainder $u\mkern-1ex\mod v = (r_{n-1}\dots r_1r_0)_b.$

  1. (Normalization)
    • Let $d = \lfloor (b - 1) / b_{n - 1} \rfloor.$
      • Depending on the representation/system, it may be preferable to choose $d$ to be a power of $2.$
      • In any case, an acceptable $d$ would satisfy $v_{n - 1} \geq \lfloor b/2 \rfloor$.
    • Then, set $(u_{m + n}u_{m + n - 1} \dots u_1 u_0)_b$ equal to $d$ times $(u_{m + n - 1} \dots u_1 u_0)_b.$
      • If $d = 1,$ set $u_{m + n} = 0.$
    • Similiarly, set $(v_{n - 1} \dots u_1 u_0)_b$ equal to $d$ times $(v_{n - 1} \dots v_1 v_0)_b.$
  2. (Initialize $j$)
    • Let $j = m.$
    • The loop over $j$, i.e. steps 2 to 7, will essentially do a division of $(u_{j + n}\dots u_{j+1}u_j)_b$ by $(v_{n-1}\dots v_1v_0)_b$ to get a single digit of the quotient.
  3. (Calculate $\hat{q}$)
    • Set $\hat{q} = \lfloor (u_{j+n}b + u_{j + n - 1}) / v_{n - 1} \rfloor,$ and let $\hat{r} = (u_{j + n}b + u_{j + n - 1}\mod v_{n-1}$ be the remainder.
    • Test if $\hat{q} = b$ or $\hat{q}v_{n-2} \gt b\hat{r} + u_{j + n - 2}.$
      • If yes, then decrement $\hat{q}$ and add $v_{n-1}$ to $\hat{r}.$ If $\hat{r} \lt b,$ repeat.
      • Otherwise, continue.
  4. (Mulsub)
    • Replace $(u_{j + n}u_{j + n - 1}\dots u_{j})_b$ with $(u_{j + n} u_{j + n - 1} \dots u_j)_b - \hat{q}(v_{n - 1} \dots v_1 v_2)_b.$
    • The digits $(u_{j + n}, u_{j + n - 1}, \dots, u_j)$ should be kept positive.
      • If the result is actually negative, then $(u_{j + n} u_{j + n - 1} \dots u_j)_b$ should be left as the true value plus $b^{n + 1},$ namely the $b$’s complement of the true value, and the borrow to the left should be remembered.
  5. (Test Remainder)
    • Set $q_j = \hat{q}.$
    • If the result of step 4 was negative, goto 6, otherwise goto 7.
  6. (Add Back)
    • Decrement $q_j$ and add $(0v_{n - 1}\dots v_1 v_0)_b$ to $(u_{j + n} u_{j + n - 1} \dots u_{j + 1} u_j)_b.$
    • Note that a carry will occur to the left of $u_{j + n},$ but it should be ignored because it cancels with the borrow in step 4.
  7. (Loop on $j$)
    • Decrement $j.$ Goto 3 if $j \geq 0.$
  8. (Unnormalize)
    • Now $(q_m\dots q_1q_0)_b$ is the quotient.
    • The remainder can be obtained by dividing $(u_{n - 1} \dots u_1 u_0)_b$ by $d.$