# 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}_{-1}d_{n-2}. . . d_{2}d_{1}d_{0. }Each digit d_{i} is the *i ^{th}* least significant digit in number D. Value of each position is given by,

d_{0} = 10^{0} position

d_{1} = 10^{1} position

d_{2} = 10^{2} position

.

.

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

According to position value,

45 = 4*10^{1} + 5*10^{0}

23 = 2*10^{1} + 3*10^{0}

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^{1} + 5*10^{0}) * (2*10^{1} + 3*10^{0})

= (4 *2) *10^{2} + (4*3 + 5*2) *10^{1} + (5*3) *10^{0}

= 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_{1}a_{0} and B = b_{1}b_{0}, then

C = A * B = c_{2}10^{2} + c_{1}10^{1} + c_{0}10^{0}

Where,

c_{2} = a_{1} * b_{1}

c_{1} = a_{1}* b_{0} + a_{0}* b_{1}

c_{0} = a_{0} * b_{0}

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
c_{2} ← DC_DUMB_MULTIPLICATION(a_{1}, b_{1})
c_{0} ← DC_DUMB_MULTIPLICATION(a_{0}, b_{0})
x ← DC_DUMB_MULTIPLICATION(a_{1}, b_{0})
y ← DC_DUMB_MULTIPLICATION(a_{0}, b_{1})
c_{1} ← x + y
**return **c_{2}*10^{n} + c_{1} * 10^{n/2}+ c_{0}
**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_{1}a_{0} = 2345, hence a_{1} = 23 and a_{0} = 45

B = b_{1}b_{0} = 0678, hence b_{1} = 06 and b_{0} = 78

C = A * B =c_{2}10^{4} + c_{1}10^{2} + c_{0}10^{0}

c_{2} = a_{1} * b_{1}

= 23 * 06

= 138

c_{1 }= a_{1}*b_{0} + a_{0}*b_{1}

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

= 2064

c_{0 }= a_{0} * b_{0}

=(45 * 78)

= 3510

C = c_{2}10^{2} + c_{1}10^{1} + c_{0}10^{0}

= 138*10^{4} + 2064*10^{2} + 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_{2} = a_{1} * b_{1}

c_{1} = a_{1}*b_{0} + a_{0}*b_{1} **…(1)**

c_{0} = a_{0}*b_{0}

**Second approach:**

Let us rewrite c_{1} as,

c_{1 }= (a_{1} + a_{0}) * (b_{1} + b_{0}) – (c_{2} + c_{0})

= (a_{1}b_{1} + a_{1}b_{0} + a_{0}b_{1} + a_{0}b_{0}) – (a_{1}b_{1} + a_{0}b_{0})

= a_{1}*b_{0} + a_{0}*b_{1} **…(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_{1}a_{0} = 2345,

hence, a_{1} = 23 and a_{0} = 45 and

B = b_{1}b_{0} = 0678,

hence, b_{1} = 06 and b_{0} = 78

c_{2} = a_{1} * b_{1}

= 23 * 06

= 138

c_{0} = a_{0}*b_{0}

= (45 * 78)

= 3510

c_{1} = (a_{1} + a_{0}) * (b_{1} + b_{0}) – (c_{2} + c_{0})

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

= 68 * 84 – 3648

= 2064

It is same as c_{1} = (a_{1}*b_{0} + a_{0}*b_{1}) of dumb multiplication approach, but does only one multiplication rather than two.

C = c_{2} * 10^{4} + c_{1} * 10^{2} + c_{0}

= 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_{2}10^{n} + c_{1}10^{n/2} + c_{0}

Where, c_{2} = a_{1} * b_{1}

c_{0} = a_{0}*b_{0}

c_{1} = (a_{1} + a_{0}) * (b_{1} + b_{0}) – (c_{2} + c_{0})

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|)
c_{2} ← DC_ CLEVER_MULTIPLICATION(a_{1}, b_{1})
c_{0} ← DC_ CLEVER_MULTIPLICATION(a_{0}, b_{0})
x ← DC_ CLEVER_MULTIPLICATION(a_{1} + a_{0}, b_{1} + b_{0})
**return **c_{2}*10^{n} + (x – c_{2} – c_{0}) * 10^{n/2} + c_{0}
**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^{2}T(n/2^{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^{2}T(n/8)) = 3^{3}T(n/2^{3}) **… (6) **

.

.

After k iterations,

T(n) = 3^{k}T(n/2^{k}) **…(7)**

Every time number of digits in number reduces by factor 2, so it can go as deep as log_{2}n,

So, k = log_{2}n ⇒ n = 2^{k}

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

T (n) = n^{log23} × 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^{2}), 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 ^{2}).**

**Solution:**

Let A = a_{1}a_{0} = 0957,

hence a_{1} = 09 and a_{0} = 57 and

B = b_{1}b_{0} = 9873,

hence b_{1} = 98 and b_{0} = 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_{2} * 10^{4} + c_{1} * 10^{2} + c_{0}

Where, c_{2} = a_{1} * b_{1}

c_{0} = a_{0}*b_{0}

c_{1} = (a_{1} + a_{0}) * (b_{1} + b_{0}) – (c_{2} + c_{0})

Let us compute c_{0}, c_{1} and c_{2}.

c_{2} = a_{1} * b_{1} = 09 * 98

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

Here X = x_{1}x_{0} = 09 and hence x_{1} = 0 and x_{0} = 9

Y = y_{1}y_{0} = 98 = 09 and hence y_{1} = 9 and y_{0} = 8

z_{2} = x_{1} * y_{1}

= 0 * 9

= 0

z_{0} = x_{0} * y_{0}

= 9 * 8

= 72

z_{1} = x_{0} + x_{1}) * (y_{0} + y_{1}) – (z_{2} + z_{0})

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

= (9*17) – 72

= 81

Z = z_{2} * 10^{2} + z_{1} * 10 + z_{0}

= 0 + 810 + 72

= 882

c_{0} = a_{0}*b_{0} = (57 * 73)

Like c_{2}, 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_{1}.

c_{0} = 4161

c_{1} = (a_{1} + a_{0}) * (b_{1} + b_{0}) – (c_{2} + c_{0})

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

= (66 * 171) – 5043

= 6243

C = c_{2} * 10^{4} + c_{1} * 10^{2} + c_{0}

= 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_{1} a_{0} = 2101

⇒ a_{1} = 21 and a_{0} = 01

B = b_{1} b_{0} = 1130

⇒ b_{1} = 11 and b_{0} = 30

Efficient integer multiplication is achieved as

A * B = c_{2} * 10^{4} + c_{1} * 10^{2} + c_{0 }** ….(1)**

Where,

c_{2} = a_{1} * b_{1} = 21 * 11

c_{0} = a_{0} * b_{0} = 01 * 30

c_{1} = (a_{1} + a_{0}) * (b_{1} + b_{0}) – (c_{2} + c_{0})

**Find c _{2}**

c_{2} = a_{1} * b_{1} = 21 * 11

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

Here,

A_{1} = 21 ⇒ a_{1} = 2 and a_{0} = 1

B_{1} = 11 ⇒ b_{1} = 1 and b_{0} = 1

A_{1} * B_{1} = x_{2} * 10^{2} + x_{1} * 10^{1} + x_{0}

x_{2} = a_{1} * b_{1}

= 2 * 1

= 2

x_{0} = a_{0} * b_{0}

= 1 * 1

= 1

x_{1} = (a_{1} + a_{0}) * (b_{1} * b_{0}) – (x_{2} + x_{0})

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

= (3 * 2 ) – 3

= 3

c_{2} = A_{1} * B_{1} = x_{2} * 10^{2} + x_{1} * 10 + x_{0}

= 200 + 30 + 1

= 231

**Find c _{0}**

c_{0} = a_{0} * b_{0} = 01 * 30

| b_{0} | > 1, So recursively solve the problem 01 * 30

Here,

A_{2} = 01 ⇒ a_{1} = 0 and a_{0} = 1

B_{2} = 30 ⇒ b_{1} = 3 and b_{0} = 0

A_{2} * B_{2} = y_{2} * 10^{2} + y_{1} * 10 + y_{0}

y_{2} = a_{1}* b_{1}

= 0 * 3

= 0

y_{0} = a_{0 }* b_{0}

= 1 * 0

= 0

y_{1} = (a_{1 }+ a_{0}) * (b_{1 }+ b_{0}) – (y_{2}+ y_{0})

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

= 0

c_{0} = A_{2} * B_{2} = y_{2} * 10_{2} + y_{1} * 10+ y_{0}

= 0 + 3 * 10 + 0

= 30

**Find c _{1}**

c_{1} = (a_{1} + a_{0}) * (b_{1} + b_{0}) – (c_{2} + c_{0})

= (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_{1} = 2, a_{0} = 2

B1 = 41 ⇒ b_{1} = 4, b_{0} = 1

z_{2} = a_{1} * b_{1}

= 2 * 4

= 8

z_{0} = a_{0} * b_{0}

= 2 * 1

= 2

z_{1} = (a_{1} + a_{0}) * (b_{1} + b_{0}) – (z_{2} + z_{0})

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

= 4 * 5 – 10

= 10

A1 * B1 = z_{2} * 10^{2} + z_{1} * 10^{1}+ z_{0}

= 800 + 100 + 2

= 902

Put this value back in Equation (2),

c_{1} = 902 – 261

= 641

Put c_{2}, c_{1} and c_{0} 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