Definition:Classical Algorithm/Division

From ProofWiki
Jump to navigation Jump to search



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



Also see


Sources