Definition:Classical Algorithm/Primitive Operation
Definition
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\) |
Sources
- 1998: Donald E. Knuth: The Art of Computer Programming: Volume 2: Seminumerical Algorithms (3rd ed.) ... (previous) ... (next): $4.3$: Multiple Precision Arithmetic: $4.3.1$ The Classical Algorithms