Implementing Basic Arithmetic for Large Integers: Division: Long-Division as an Iterative Algorithm

[This page is auto-generated; please prefer to read the article’s PDF Form.]

[Prev] [Up] [Next]

Long-Division as an Iterative Algorithm

Let us denote the dividend by a = (a_{n_a−1}a_{n_a−2}…a₁a₀) having n_a digits, and the divisor by b = (b_{n_b−1}b_{n_b−2}…b₁b₀) having n_b digits, in base B numeral system. The case when n_a < n_b simply implies the quotient is 0 and remainder is a. So, we only need to consider the other case, n_a ≥ n_b.

The long-division algorithm can be seen as an iterative process where each iteration generates exactly one quotient-digit. In each iteration, the “current” IDD x, having width n_b + 1 is considered and a digit d needs to be found such that:

bd ≤ x (1) b(d + 1) > x

Once this quotient-digit d is found, subtraction (x−bd) is done and the next digit from a is suﬃxed to the result, to form the next IDD. This continues until there are no more digits to bring down from a. At that point, the subtraction result, (x − bd), is the remainder of this division.

Note that the result of subtraction t = (x − bd) in any iteration follows:

t = x− bd < b(d+ 1) − bd = b

i.e. t ≤ b − 1. So, t has at most n_b digits.

The next IDD, which is formed by suﬃxing a digit (say, a_i) from a to t is (tB + a_i), and must have at most n_b + 1 digits. Also, it must follow:

tB + a ≤ (b − 1)B + (B − 1) = bB − 1 < bB i

The initial IDD is also chosen as having n_b digits from the dividend, and must be less than bB, which has n_b + 1 digits. So, we can conclude that every IDD must have at most n_b + 1 digits, and must be less than bB. Though, as mentioned earlier, we will always be treating them as having width n_b + 1.

Further, any number d which satisﬁes (1) must follow d ≤ x∕b < bB∕b = B. That is, d ≤ B − 1, and so d must be a single digit number.

Now we look into the problem of computing quotient-digit d in each iteration.

[Prev] [Up] [Next]