Definition:Classical Algorithm/Primitive Division
Jump to navigation
Jump to search
Definition
The primitive operation for division which can be used in the classical algorithms is defined as follows.
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