Integer Multiplication

---

Contents

---

Conceptually, the multiplication of two integers $a$ and $n$ can be represented as

$a\times n=\text{sign(n)}\times (\underset{|n|\text{times}}{\underbrace{a+a+\cdots +a}})$

---

Divide and Conquer

D/C 1

 INPUT    two integers a and n
OUTPUT    an integer an

MULT(a, n)
1    if n == 1
2        return a
3    return a + MULT(a, n - 1)

In this less common D/C approach to integer multiplication, the problem size is being reduced by one for each recursive call.

$\underset{\text{combine}}{\underbrace{\underset{\text{sub problem}}{\underbrace{a}}+\underset{\text{sub problem}}{\underbrace{\mathtt{\text{MULT}}(a,n-1)}}}}$

$\begin{array}{rl}T(n)& =1+T(n-1)\\ & =1+1+T(n-2)\\ & =\dots \\ & =1+1+1+\cdots +T(1)\\ & =\underset{n\text{times}}{\underbrace{1+1+1+\cdots +1}}\\ & =n\\ & =\mathrm{\Theta }(n)\end{array}$

D/C 2

 INPUT    two integers a, and n even
OUTPUT    an integer an

MULT(a, n)
1    if n == 1
2        return a
3    s1 = mult(a, n/2)   # sub problem
4    s2 = mult(a, n/2)   # sub problem
5    return s1 + s2      # combine

In this common D/C approach to integer multiplication, the problem size is being reduced by half for each recursive call.

$\underset{\text{combine}}{\underbrace{\underset{\text{sub problem}}{\underbrace{\mathtt{\text{MULT}}(a,n/2)}}+\underset{\text{sub problem}}{\underbrace{\mathtt{\text{MULT}}(a,n/2)}}}}$

$T(n)=\underset{\text{subproblems}}{\underbrace{\stackrel{\text{divide}}{\text{2}}}}\times \underset{\text{cost per subproblem}}{\underbrace{\stackrel{\text{conquer}}{T(b/2)}}}+\underset{\text{cost of combination}}{\underbrace{\stackrel{\text{combine}}{\mathrm{\Theta }(1)}}}$

$T(n)=2T(n/2)+\mathrm{\Theta }(1)$

By the Master Theorem we have

$a=2,b=2,d=0⟹d<{\log }_{b}a⟸0<1$

$T(n)=\mathrm{\Theta }(n^{{\log }_{b}a})=\mathrm{\Theta }(n^{{\log }_{2}2})=\boxed{{\displaystyle \mathrm{\Theta }(n)}}$

This algorithm can be optimized! Since the two problems are symmetric as long as b is even, just one of the two sub problems needs to be evaluated.

 INPUT    two integers a, and n even
OUTPUT    an integer an

MULT(a, n)
1    if n == 1
2        return a
3    s = mult(a, n/2)   # sub problem
4    return s1 + s1     # combine

$T(n)=T(n/2)+\mathrm{\Theta }(1)$

By the Master Theorem we have

$a=1,b=2,d=0⟹d={\log }_{b}a⟸0=0$

$T(n)=\mathrm{\Theta }(n^d\log n)=\mathrm{\Theta }(n^0\log n)=\boxed{{\displaystyle \mathrm{\Theta }(\log n)}}$

---