Definition:Classical Algorithm/Primitive Subtraction

From ProofWiki
Jump to navigation Jump to search

Definition

The primitive operation for subtraction which can be used in the classical algorithms is:

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.



In this context, the carry digit is often referred to as a borrow.


Base $10$ Subtraction Table

The primitive subtraction operation for conventional base $10$ arithmetic on two $1$-digit integers can be presented as a pair of operation tables as follows:

$\begin{array}{c|cccccccccc}

d & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline 0 & 0 & 9 & 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1 \\ 1 & 1 & 0 & 9 & 8 & 7 & 6 & 5 & 4 & 3 & 2 \\ 2 & 2 & 1 & 0 & 9 & 8 & 7 & 6 & 5 & 4 & 3 \\ 3 & 3 & 2 & 1 & 0 & 9 & 8 & 7 & 6 & 5 & 4 \\ 4 & 4 & 3 & 2 & 1 & 0 & 9 & 8 & 7 & 6 & 5 \\ 5 & 5 & 4 & 3 & 2 & 1 & 0 & 9 & 8 & 7 & 6 \\ 6 & 6 & 5 & 4 & 3 & 2 & 1 & 0 & 9 & 8 & 7 \\ 7 & 7 & 6 & 5 & 4 & 3 & 2 & 1 & 0 & 9 & 8 \\ 8 & 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1 & 0 & 9 \\ 9 & 9 & 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1 & 0 \\ \end{array} \qquad \begin{array}{c|cccccccccc} c & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 2 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 3 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ 4 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ 5 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 6 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ 7 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 8 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 9 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \end{array}$


Sources

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