Implementing Basic Arithmetic for Large Integers: Division: Computing a Quotient-Digit

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

[Prev] [Up] [Next]

Computing a Quotient-Digit

When we perform long-division manually for decimal numerals, we usually depend on trial-and-error to ﬁnd a quotient-digit d. If the IDD is less than the divisor, d is simply 0. Otherwise, we can make a guess about d based on some initial digits of the divisor and the IDD. Then we need to multiply guess d with the divisor to check if the guess is correct. If incorrect, we make another guess and so on. In our earlier example, for IDD 1349, the guess of d = 4, based simply on 13∕3 (13 from 1349, 3 from 365) is incorrect (365 ⋅ 4 = 1460 exceeds 1349) and needs another try with d = 3.

We need to make this trial-and-error method eﬃcient (requiring less number of corrections) and well-deﬁned, for any base B numeral system. We will be discussing a method proposed by Pope and Stein in [3], which is also described in Knuth’s book [4] (section Multiple Precision Arithmetic). To guess d, it uses the ﬁrst digit of b and ﬁrst two digits of the IDD (which, as mentioned earlier, is treated as having width n_b + 1).

A variant of this method which uses ﬁrst two digits of b and ﬁrst three digits of the IDD has been discussed by Hansen in [5], which is also a good resource on this topic. The theorems behind this variant have been attributed to Krishnamurthy and Nandi [6].

Let us denote the IDD of some iteration by x = (x_{n_b}x_{n_b−1}…x₁x₀), where x_{n_b}, x_{n_b−1} etc may be 0. In favor of simpler symbols, we will denote x_{n_b},x_{n_b−1} as y,z and b_{n_b−1} (the MSD of b) as e. The 2-digit number formed by y and z will be denoted as (yz).

Before we proceed further, we will make some observations about multiplication of b by a single digit s, that will help us in the discussion below. Such multiplication will be referred as “multiplication bs{s = …}” with s as speciﬁed.

We can use the schoolbook’s multiplication method to help us understand this:

e bnb−2 bnb− 3 ... b1 b0 -------------------------×--s--- u v tnb−2 tnb−3 ... t1 t0

Please refer to article [2], section “Multiplication by a Digit”, Lemma 2. The digits u, v at positions n_b, n_b−1 of the result, will together form a number (uv) as given by (c_{n_b−2} is the carry from earlier position):

(uv) = cnb− 2 + es

(2)

So,

(uv) ≥ es

(3)

Also, due to Lemma 1 in article [2], any carry cannot exceed (s − 1). So,

(uv ) ≤ (s− 1) + es

(4)

Whenever we will need to compare bs (for any digit s) with the IDD x, we can ﬁrst ignore their last n_b − 1 digits and simply compare the values formed by their two most signiﬁcant digits: (uv) and (yz). Then we can use:

(uv ) > (yz) ⇒ bs > x (5) (uv ) < (yz) ⇒ bs < x (6)

[Prev] [Up] [Next]