Definition:Classical Algorithm/Primitive Division

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