Implementing Basic Arithmetic for Large Integers: Division: Correction in the Estimate

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

[Prev] [Up] [Next]

Correction in the Estimate

Due to (9), we know that the desired d is of the form d₁ − Δ, where Δ = 0,1,2,…. What happens when we do multiplication bs{s = d₁ − Δ} for any Δ = 0,1,2,…? The value (uv) in the result must follow (due to (4)):

(uv) ≤ (d − Δ − 1)+ e(d − Δ ) 1 1

(10)

Suppose, for any given Δ, we can ﬁnd out the condition C_Δ under which this (uv) is always less than (yz). Then, b(d₁ − Δ) must be less than x (using (6)). So, we can be sure that the desired d must be one among d₁ − Δ, d₁ − Δ + 1, …, d₁, whenever condition C_Δ holds.

Let us try to ﬁnd out such a condition. Equation (10) provides an upper-bound on (uv) and equation (8) provides a lower-bound on (yz). If we ensure that the (uv) upper-bound is less than (yz) lower-bound, we are guaranteed to get (uv) < (yz). To do that:

(d − Δ − 1)+ e(d − Δ) < ed 1 1 1 ⇔ (d1 − Δ − 1) < eΔ ⇔ e > (d1 − Δ − 1)∕Δ

(Note that above is not possible with Δ = 0). As (B − 1) > (d₁ − Δ − 1), so, if we have e ≥ (B − 1)∕Δ, the above condition is guaranteed to be met. Thus, the desired condition C_Δ, which guarantees that the d is one among d₁ − Δ, d₁ − Δ + 1, …, d₁ is:

C Δ: e ≥ (B − 1)∕Δ

(11)

For Δ = 1, it looks diﬃcult to achieve this condition. For Δ = 2, it is achieved whenever e ≥ (B − 1)∕2. Since the divisor b need not have its ﬁrst digit e with e ≥ (B − 1)∕2, so we will follow a process called Normalization to achieve this, whenever e < (B − 1)∕2. Note that (B − 1)∕2 itself is not an integer for even B.

[Prev] [Up] [Next]