Definition:Classical Algorithm/Primitive Operation

From ProofWiki
Jump to navigation Jump to search

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

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