Definition:Classical Algorithm/Primitive Addition

From ProofWiki
Jump to navigation Jump to search

Definition

The primitive operation for addition 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$.

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.



Base $10$ Addition Table

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

$\begin{array}{c|cccccccccc}

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


Sources

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