Definition:Classical Algorithm

From ProofWiki
Jump to navigation Jump to search

Definition

The classical algorithms are the conventional techniques for performing arithmetic on numbers with more than $1$ digit.


Addition

Let $u = \sqbrk {u_{n - 1} u_{n - 2} \dotsm u_1 u_0}_b$ and $v = \sqbrk {v_{n - 1} v_{n - 2} \dotsm v_1 v_0}_b$ be $n$-digit integers.

The classical addition algorithm forms their $n + 1$-digit sum $u + v$:

$w = \sqbrk {w_n w_{n - 1} \dotsm w_1 w_0}_b$

where $w_n$ is either $0$ or $1$.


The steps are:

$(\text A 1): \quad$ Set $j = 0$, $k = 0$.
$j$ is used to run through all the digit positions
$k$ keeps track of the carry digit between each step.
$(\text A 2): \quad$ Calculate digit $j$:
Calculate $\begin {cases} s = \paren {u_j + v_j + k} \pmod b \\ c = \floor {\dfrac {u_j + v_j + k} b} \end {cases}$ using the primitive addition.
Set $w_j$ to $s$.
Set $k$ to $c$.
$(\text A 3): \quad$ Add $1$ to $j$, using conventional integer addition.
If $j < n$, return to $(\text A 2)$.
Otherwise, set $w_n$ equal to $k$ and exit.


Subtraction

Let $u = \sqbrk {u_{n - 1} u_{n - 2} \dotsm u_1 u_0}_b$ and $v = \sqbrk {v_{n - 1} v_{n - 2} \dotsm v_1 v_0}_b$ be $n$-digit integers.

The classical subtraction algorithm forms their $n$-digit difference $u - v$:

$w = \sqbrk {w_n w_{n - 1} \dotsm w_1 w_0}_b$

where $w_n$ is either $0$ or $1$.


The steps are:

$(\text S 1): \quad$ Set $j = 0$, $k = 0$.
$j$ is used to run through all the digit positions
$k$ keeps track of the carry digit between each step.
$(\text S 2): \quad$ Calculate digit $j$:
Calculate $\begin {cases} d = \paren {u_j + v_j - k} \pmod b \\ c = \floor {\dfrac {u_j - v_j + k} b} \end {cases}$ using the primitive subtraction.
Set $w_j$ to $d$.
Set $k$ to $c$.
$(\text S 3): \quad$ Add $1$ to $j$, using conventional integer addition.
If $j < n$, return to $(\text S 2)$.
Otherwise exit.


Multiplication

Let $u = \sqbrk {u_{m - 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$-digit and $n$-digit integers respectively.

The classical multiplication algorithm forms their $m + n$-digit product $u v$:

$w = \sqbrk {w_{m + n - 1} w_{m + n - 2} \dotsm w_1 w_0}_b$


The steps are:

$(\text M 1): \quad$ Initialise:
Set $w_{m - 1}, w_{m - 2}, \dotsc, w_1, w_0 := 0$
Set $j := 0$
$(\text M 2): \quad$ Is $v_j = 0$?
If so, go to Step $(\text M 6)$.
$(\text M 3): \quad$ Initialise loop:
Set $i := 0$
Set $k := 0$
$(\text M 4): \quad$ Multiply and Add:
Set $t := u_i \times v_j + w_{i + j} + k$
Set $w_{i + j} := t \pmod b$
Set $k := \floor {\dfrac t b}$
$(\text M 5): \quad$ Loop on $i$:
Increase $i$ by $1$.
If $i < m$, go back to Step $(\text M 4)$.
Otherwise, set $w_{j + m} := k$
$(\text M 6): \quad$ Loop on $j$:
Increase $j$ by $1$.
If $j < n$, go back to Step $(\text M 2)$.
Otherwise exit.


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:
\(\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$.


Primitive Operations

The primitive operations of the classical algorithms are the following operations which are performed on two $1$-digit integers $x$ and $y$:


Addition

Let $x$ and $y$ be $1$-digit integers.

Let $z$ be a carry digit such that either $z = 0$ or $z = 1$.

Addition of $x$, $y$ and $z$ gives a $1$-digit sum $s$ and a $1$-digit carry $c$ such that:


\(\ds s\) \(=\) \(\ds \paren {x + y + z} \pmod b\)
\(\ds c\) \(=\) \(\ds \floor {\dfrac {x + y + z} b}\)
\(\ds \) \(=\) \(\ds \begin{cases} 1 & : x + y + z \ge b \\ 0 & : x + y + z < b \end{cases}\)


A particular theorem is missing.
In particular: Prove that $0 \le c \le 1$
You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding the theorem.
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 {{TheoremWanted}} from the code.



Subtraction

Let $x$ and $y$ be $1$-digit integers.

Let $z$ be a carry digit such that either $z = 0$ or $z = -1$.

Subtraction of $y$ from $x$ with $z$ gives a $1$-digit difference $d$ and a $1$-digit carry $c$ such that:


\(\ds d\) \(=\) \(\ds \paren {x - y + z} \pmod b\)
\(\ds c\) \(=\) \(\ds \floor {\dfrac {x - y + z} b}\)
\(\ds \) \(=\) \(\ds \begin{cases} 0 & : x - y + z \ge 0 \\ -1 & : x - y + z < 0 \end{cases}\)


A particular theorem is missing.
In particular: prove that $-1 \le c \le 0$
You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding the theorem.
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 {{TheoremWanted}} from the code.



Multiplication

Multiplication of two $1$-digit integers $x$ and $y$ gives a $1$-digit product $p$ and a $1$-digit carry $c$ such that:


\(\ds p\) \(=\) \(\ds x \times y \pmod b\)
\(\ds \) \(\) \(\ds \)
\(\ds c\) \(=\) \(\ds \dfrac {x \times y - p} b\)


Division

Let $y$ be a $1$-digit integer.

Let $x$ be a $2$-digit integer $x_1 b + x_2$, where $x_1$ and $x_2$ are $1$-digit integers.


Suppose $x_1 \ge y$.

Then division of $x_1$ by $y$ gives a $1$-digit quotient $q$ and a $1$-digit remainder $r$, which is used as a carry, such that:

\(\ds x_1\) \(=\) \(\ds q \times y + r\)


Suppose $x_1 < y$.

Then division of $x = x_1 b + x_2$ by $y$ gives a $1$-digit quotient $q$ and a $1$-digit remainder $r$, which is used as a carry, such that:

\(\ds x\) \(=\) \(\ds q \times y + r\)


Historical Note

For hundreds of years, the classical algorithms were the only algorithms known.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Definition:Classical_Algorithm&oldid=492649"