Definition:Classical Algorithm/Division

This article is complete as far as it goes, but it could do with expansion. In particular: Extend the algorithm to rational expansions of arbitrary length You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding this information. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Expand}} from the code. If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.

Definition

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:

\(\ds d\)

\(:=\)

\(\ds \floor {\dfrac b {v_{n - 1} - 1} }\)

\(\ds \sqbrk {u_{m + n} u_{m - 1} \dotsm u_1 u_0}_b\)

\(:=\)

\(\ds \sqbrk {u_{m + n - 1} u_{m - 2} \dotsm u_1 u_0}_b \times d\)

\(\ds \sqbrk {v_{n - 1} \dotsm v_1 v_0}_b\)

\(:=\)

\(\ds \sqbrk {v_{n - 1} \dotsm v_1 v_0}_b \times d\)

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$.

Proof

Work In Progress You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by completing it. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{WIP}} from the code.

Also see

• Classical Division Algorithm is Valid, which demonstrates that $u \div v = w \rem d$.

Sources

• 1998: Donald E. Knuth: The Art of Computer Programming: Volume 2: Seminumerical Algorithms (3rd ed.) ... (previous): $4.3$: Multiple Precision Arithmetic: $4.3.1$ The Classical Algorithms