Large Integer Multiplication using Divide and Conquer

Large Integer Multiplication is a common procedure in computer-assisted problem solving. Multiplying big numbers is not only difficult, but also time-consuming and error-prone.

In this article, we will look at two approaches to multiplying big numbers: the grade school method and the divide and conquer method.

Large Integer Multiplication using Grade School Multiplication

In school, we studied the traditional multiplication technique. The multiplicand is multiplied by each digit of the multiplier in that technique, and a partial result of each multiplication is added by performing appropriate shifting. This method is also known as the Traditional Multiplication Method.

The following example demonstrates how to perform grade school multiplication in both American and English way.

This approach is simple to grasp, yet it is time-consuming and inefficient. If multiplicand has n digits and multiplier has m digits, the complexity of multiplication would be O(mn).

This technique takes quadratic time, which is insufficient for big numbers. Let’s look into a more convenient method of multiplication.

Large Integer Multiplication using Divide and Conquer Approach

There are two ways to perform large integer multiplication using divide and conquer. The first method – we call dumb method – does not improve the running time. Second method – we call clever approach – performs better then the traditional approach for integer multiplication.

Dumb Approach:

Let us represent number D as D = d_n-1d_n-2. . . d₂d₁d_0. Each digit d_i is the i^th least significant digit in number D. Value of each position is given by,

d₀ = 10⁰ position

d₁ = 10¹ position

d₂ = 10² position

.

 .

d_{n – 1} = 10^{n – 1} position.

According to position value,

45 = 4*10¹ + 5*10⁰

23 = 2*10¹ + 3*10⁰

For any real values a, b, c and d,

(a + b)*(c + d) = (a*c + a*d + b*c + b*d)

So, 45 * 23    =   (4*10¹ + 5*10⁰) * (2*10¹ + 3*10⁰)

=   (4 *2) *10² + (4*3 + 5*2) *10¹ + (5*3) *10⁰

= 800 + 220 + 15 

= 1035

Let’s derive formula to multiply two numbers of two digits each. Consider C = A * B. If we consider A = a₁a₀ and B = b₁b₀, then               

C = A * B = c₂10² + c₁10¹ + c₀10⁰

Where, 

c₂ = a₁ * b₁

c₁ = a₁* b₀ + a₀* b₁

c₀ = a₀ * b₀

This method does four multiplications, same as conventional method. This is as dumb as grade school multiplication. Algorithm for this approach is described below :

Algorithm DC_DUMB_MULTIPLICATION(A, B)
// Description : Perform multiplication of large numbers using divide and conquer strategy.
// Input : Number A and B, where A = an-1…a1a0, 
B = bn-1... b1b0
// Output : Multiplication of A and B as C, i.e. C = A * B

if |a| == 1 or |b| == 1 then
    return A * B
else
    n ← max(|A|, |B|)	// returns maximum number digits
    c2 ← DC_DUMB_MULTIPLICATION(a1, b1)
    c0 ← DC_DUMB_MULTIPLICATION(a0, b0)
    x ← DC_DUMB_MULTIPLICATION(a1, b0)
    y ← DC_DUMB_MULTIPLICATION(a0, b1)
    c1 ← x + y
    return c2*10n + c1 * 10n/2+ c0
end

Example: Multiply 2345 with 678 using divide and conquer approach.

Solution:

Size of both operands must be even, so pad zero to the multiplier.

A = 2345 and B = 0678

A = a₁a₀ = 2345, hence a₁ = 23 and a₀ = 45

B = b₁b₀ = 0678, hence b₁ = 06 and b₀ = 78

C = A * B =c₂10⁴ + c₁10² + c₀10⁰

c₂ = a₁ * b₁ 

= 23 * 06

= 138       

c₁ = a₁*b₀ + a₀*b₁ 

= (23*78) + (45 * 06)

= 2064

c₀ = a₀ * b₀

=(45 * 78)

= 3510

C = c₂10² + c₁10¹ + c₀10⁰

= 138*10⁴ + 2064*10² + 3510

= 15, 89, 910

Clever Approach:

Previous DC approach does four multiplications. Let’s reformulate it to reduce numbers of multiplications to three.

First approach:

According to dumb approach,

c₂ = a₁ * b₁

c₁ = a₁*b₀ + a₀*b₁ …(1)

c₀ = a₀*b₀

Second approach:

Let us rewrite c₁ as,

c₁ = (a₁ + a₀) * (b₁ + b₀) – (c₂ + c₀)

= (a₁b₁ + a₁b₀ + a₀b₁ + a₀b₀) – (a₁b₁ + a₀b₀)

= a₁*b₀ + a₀*b₁ …(2)

Equation (1) and Equation (2) are the same, but the second approach of computing c1 involves only one multiplication rather than two as it requires in the first approach.

For A = a₁a₀ = 2345,

hence, a₁ = 23 and a₀ = 45 and

B = b₁b₀ = 0678,    

hence, b₁ = 06 and b₀ = 78

c₂ = a₁ * b₁ 

= 23 * 06

= 138

c₀ = a₀*b₀

= (45 * 78)

= 3510

c₁ = (a₁ + a₀) * (b₁ + b₀) – (c₂ + c₀)

= (23 + 45) * (06 + 78) – (138 + 3510)

= 68 * 84 – 3648

= 2064

It is same as c₁ = (a₁*b₀ + a₀*b₁) of dumb multiplication approach, but does only one multiplication rather than two.

C = c₂ * 10⁴ + c₁ * 10² + c₀

= 1380000 + 206400 + 3510 = 15, 89, 910

This formulation leads to same result, with three multiplications only.

Generalization:

If size of integer is n digit, then we can generalize multiplication as,

C = c₂10ⁿ + c₁10^n/2 + c₀

Where, c₂ = a₁ * b₁

c₀ = a₀*b₀

c₁ = (a₁ + a₀) * (b₁ + b₀) – (c₂ + c₀)                                                                                                  

This can be solved by applying recursion till n reaches to 1.

Algorithm DC_CLEVER_MULTIPLICATION(A, B)
// Description : Perform multiplication of large numbers using divide and conquer strategy.
// Input : Number A and B, where A = an-1…a1a0, and B = bn-1...b1b0
// Output : Multiplication of A and B as C, i.e. C = A * B

if |a| == 1 or |b| == 1 then
    return  A * B
else
    n ← max(|A|, |B|)	
    c2 ← DC_ CLEVER_MULTIPLICATION(a1, b1)
    c0 ← DC_ CLEVER_MULTIPLICATION(a0, b0)
    x ← DC_ CLEVER_MULTIPLICATION(a1 + a0, b1 + b0)
    return c2*10n + (x – c2 – c0) * 10n/2 + c0
end

Complexity Analysis

For n digit integer, we have to perform 3 multiplications of integers of size (n / 2). Recurrence equation for this problem is given as,

T(n) = 3T(n/2), if n > 1

T(n) = 1, if n = 1

Proof:

T(n) = 3T(n/2) … (3)

Let us solve this recurrence by an iterative approach. Substitute n by n/2 in Equation (3)

T(n/2) = 3T(n/4) … (4)

Put this value in Equation (3),

T(n) = 3(3T(n/4)) = 3²T(n/2²) … (5)

Substitute n by n/2 in Equation (4)

T(n/4) = 3T(n/8)

Put this value in Equation (3)

T(n) = 3(3²T(n/8)) = 3³T(n/2³) … (6)

.

.

After k iterations,

T(n) = 3^kT(n/2^k) …(7)

Every time number of digits in number reduces by factor 2, so it can go as deep as log₂n,

So, k = log₂n ⇒ n = 2^k

Thus from equation (5), T(n) = 3^kT( 2^k /2^k)

T (n) = n^log₂3 × T(1) (∵ n^logba = a^logb n)

T (1) = 1(Only one multiplication is required to multiply two numbers of digits 1)                                

So, T(n) = n^log23 = O(n^1.58)

Grade school method multiplies each digit of the multiplier with each digit of the multiplicand. So for each digit of the multiplier, n multiplications are performed with multiplicand. This is done each of the n bits of the multiplier. So running time of that method was O(n²), whereas the divide and conquer approach reduces the running time to O(n^1.58). For large numbers, the difference becomes significant.

Example

Problem: Perform multiplication of given large integers 957 ´ 9873 in timeless than O(n²).

Solution:

Let A = a₁a₀ = 0957,

hence a₁ = 09 and a₀ = 57 and

B = b₁b₀ = 9873, 

hence b₁ = 98 and b₀ = 73

Given problem is of size 4, so n = 4.

Solution to this problem using divide and conquer approach can be given as,

C = c₂ * 10⁴ + c₁ * 10² + c₀

Where, c₂ = a₁ * b₁

c₀ = a₀*b₀

c₁ = (a₁ + a₀) * (b₁ + b₀) – (c₂ + c₀)

Let us compute c₀, c₁ and c₂.

c₂ = a₁ * b₁ = 09 * 98

This is a new problem of size 2, solve it recursively,

Here X = x₁x₀ = 09 and hence x₁ = 0 and x₀ = 9

Y = y₁y₀ = 98 = 09 and hence y₁ = 9 and y₀ = 8

z₂ = x₁ * y₁ 

= 0 * 9

= 0

z₀ = x₀ * y₀ 

= 9 * 8

= 72

z₁ = x₀ + x₁) * (y₀ + y₁) – (z₂ + z₀)

= (0 + 9) *(9 + 8) – (0 + 72)

= (9*17) – 72

= 81

Z = z₂ * 10² + z₁ * 10 + z₀

= 0 + 810 + 72  

= 882

c₀ = a₀*b₀ = (57 * 73)

Like c₂, this is also a problem of size 2 and solved similar in a recursive manner, and the same will apply to the computation of c₁.

c₀ = 4161

c₁ = (a₁ + a₀) * (b₁ + b₀) – (c₂ + c₀)

= (09 + 57) * (98 + 73) – (882 + 4161)

= (66 * 171) – 5043

= 6243

C = c₂ * 10⁴ + c₁ * 10² + c₀

= 8820000 + 624300 + 4161

= 94, 48, 461

This formulation leads to same result, with three multiplications only.

Problem: Show the steps in multiplying the following two integers using efficiency integer multiplication method 2101 * 1130.

Solution:

Given the numbers

A = a₁ a₀ = 2101

⇒  a₁ = 21 and a₀ = 01

B = b₁ b₀ = 1130

⇒  b₁ = 11 and b₀ = 30

Efficient integer multiplication is achieved as

A * B = c₂ * 10⁴ + c₁ * 10² + c₀  ….(1)

Where,       

c₂ = a₁ * b₁  = 21 * 11

c₀ = a₀ * b₀  =  01 * 30

c₁ = (a₁ + a₀) * (b₁ + b₀) – (c₂ + c₀)

Find c₂

c₂ = a₁ * b₁  =  21 * 11

| a | >1 and | b | > 1, So  recursively solve the problem 21 * 11.

Here,

A₁ = 21 ⇒ a₁  = 2  and   a₀ = 1

B₁ = 11 ⇒ b₁  = 1  and   b₀ = 1

A₁ * B₁ = x₂ * 10² + x₁ * 10¹ + x₀

x₂ = a₁ * b₁

= 2 * 1

= 2

x₀ = a₀ * b₀ 

= 1 * 1

= 1

x₁ = (a₁ + a₀) * (b₁ * b₀) – (x₂ + x₀)

= (2 + 1) * (1 + 1) – (2 + 1)

= (3 * 2 ) – 3

= 3

c₂ = A₁ * B₁ = x₂ * 10² + x₁ * 10 +  x₀

= 200 + 30 + 1

= 231

Find c₀

c₀ = a₀ * b₀ = 01 * 30

| b₀ | > 1,  So  recursively solve the problem 01 * 30

Here,

A₂ = 01 ⇒ a₁ = 0 and a₀ = 1

B₂ = 30 ⇒ b₁ = 3 and b₀ = 0

A₂ * B₂ = y₂ * 10² + y₁ * 10 + y₀

y₂ = a₁* b₁

= 0 * 3

= 0

y₀ = a₀ * b₀

= 1 * 0

= 0

y₁ = (a₁ + a₀) * (b₁ + b₀) – (y₂+ y₀)

= (0 * 3) * (1 + 0) – (0 + 0) 

= 0

c₀ = A₂ * B₂ =  y₂ * 10₂ +  y₁ * 10+  y₀

= 0 + 3 * 10 + 0 

= 30

Find c₁

c₁ = (a₁ + a₀) * (b₁ + b₀) – (c₂ + c₀)

= (21 + 01) * (11 + 30) – (231 + 30)

= (22 * 41) – (261)          …(2)

22 * 41 is the new problem of size n/2

Find 22 * 41

Here,

A1 = 22 ⇒ a₁ = 2, a₀ = 2

B1 = 41 ⇒ b₁ = 4, b₀ = 1

z₂ = a₁ * b₁

= 2 * 4

= 8

z₀ = a₀ * b₀

= 2 * 1

= 2

z₁ = (a₁ + a₀) * (b₁ + b₀) – (z₂ + z₀)

= (2 + 2) * (4 + 1 ) – (8 + 2)

= 4 * 5 – 10 

= 10

A1 * B1 = z₂ * 10² + z₁ * 10¹+ z₀

= 800 + 100 + 2

= 902

Put this value back in Equation (2),

c₁ = 902 – 261

= 641

Put c₂,  c₁  and  c₀ in Equation (1),

A * B = 2310000 + 64100 + 30

= 2374130

Some Popular Problems Solved using Divide and Conquer

• Linear Search
• Binary Search
• Convex Hull
• Max-Min Problem
• Larger Integer Multiplication
• Strassen’s Matrix Multiplication
• Finding Exponent Problem
• Merge Sort
• Quick Sort

---

Additional Reading: Click to read