\begin{definition}[Definition:Classical Algorithm/Division]
Let $u = \sqbrk {u_{m + n - 1} u_{m - 2} \dotsm u_1 u_0}_b$ and $v = \sqbrk {v_{n - 1} v_{n - 2} \dotsm v_1 v_0}_b$ be $m + n$-digit and $n$-digit integers respectively, where $v_{n - 1} \ne 0$ and $n > 1$.
The '''classical division algorithm''' forms:
:their $m + 1$-digit quotient $\floor {\dfrac u v} = q = \sqbrk {q_m q_{m - 1} \dotsm q_1 q_0}_b$
and:
:their $n$-digit remainder $u \pmod v = r = \sqbrk {r_{n - 1} \dotsm r_1 r_0}_b$
The steps are:
:$(\text D 1): \quad$ Normalize:
::::Set:
{{begin-eqn}}
{{eqn | l = d
      | o = :=
      | r = \floor {\dfrac b {v_{n - 1} - 1} }
}}
{{eqn | l = \sqbrk {u_{m + n} u_{m - 1} \dotsm u_1 u_0}_b
      | o = :=
      | r = \sqbrk {u_{m + n - 1} u_{m - 2} \dotsm u_1 u_0}_b \times d
}}
{{eqn | l = \sqbrk {v_{n - 1} \dotsm v_1 v_0}_b
      | o = :=
      | r = \sqbrk {v_{n - 1} \dotsm v_1 v_0}_b \times d
}}
{{end-eqn}}
::::Note that if $d = 1$, all that needs to be done is to set $u_{m + n} := 0$.
:$(\text D 2): \quad$ Initialise $j$:
::::Set $j := m$
:$(\text D 3): \quad$ Calculate the quotient $\hat q$ and remainder $\hat r$:
::::Set $\hat q := \floor {\dfrac {u_{j + n} b + u_{j + n - 1} } {v_{n - 1} } }$
::::Set $\hat r := \paren {u_{j + n} b + u_{j + n - 1} } \pmod {v_{n - 1} }$
::::Test whether $\hat q = b$ or $\hat q v_{n - 1} > b \hat r + u_{j + n - 2}$.
::::If so, decrease $\hat q$ by $1$ and increase $\hat r$ by $v_{n - 1}$.
::::If $\hat r < b$ repeat this test.
:$(\text D 4): \quad$ Multiply and Subtract:
::::Replace $\sqbrk {u_{j + n} u_{j + n - 1} \dotsm u_j}_b$ by $\sqbrk {u_{j + n} u_{j + n - 1} \dotsm u_j}_b - \hat q \sqbrk {0 v_{n - 1} v_{n - 2} \dotsm v_1 v_0}_b$
::::If the result of this step is negative, add $b_{n + 1}$ to it.
:$(\text D 5): \quad$ Test remainder:
::::Set $q_j := \hat q$.
::::If the result of '''Step $(\text D 4)$''' was negative, go to '''Step $(\text D 6)$'''
::::Otherwise go to '''Step $(\text D 7)$'''
:$(\text D 6): \quad$ Add back:
::::Decrease $q_j$ by $1$
::::Add $\sqbrk {0 v_{n - 1} v_{n - 2} \dotsm v_1 v_0}_b$ to $\sqbrk {u_{j + n} u_{j + n - 1} \dotsm u_j}_b$ (ignoring the carry)
:$(\text D 7): \quad$ Loop on $j$:
::::Decrease $j$ by $1$
::::If $j \ge 0$ go back to '''Step $(\text D 3)$'''
:$(\text D 8): \quad$ Unnormalise:
::::The required quotient is $\sqbrk {q_m q_{m - 1} \dotsm q_1 q_0}_b$
::::The required remainder is obtained by dividing $\sqbrk {u_{n - 1} u_{m - 2} \dotsm u_1 u_0}_b$ by $d$.
\end{definition}