Implementing Basic Arithmetic for Large Integers: Division: Normalization

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

[Prev] [Up] [Next]

Normalization

We will multiply both a and b by a Scaling-Factor f so that (bf)’s ﬁrst digit is at least (B − 1)∕2. Then, we will perform the division process on these modiﬁed operands af (dividend) and bf (divisor). The quotient of this division must be same as the quotient with original operands a and b. The remainder needs to be divided by f to give the remainder for division with original operands.

We can ﬁnd the scaling-factor f as follows. Let us try with f as a single digit number. In the multiplication bs{s = f}, the value (uv) in the result will follow, due to (3) and (4):

ef ≤ (uv) ≤ (f − 1) + ef

We want this value (uv) to satisfy the constraints:

(B − 1)∕2 ≤ (uv) ≤ B − 1

which can be achieved with:

(B − 1)∕2 ≤ ef and, (f − 1) + ef ≤ B − 1 ⇔ f ≥ (B − 1)∕(2e) and, f ≤ B∕ (e + 1)

So, we can choose f = ⌊B∕(e + 1)⌋.

[Prev] [Up] [Next]