Integer Multiplication

Integer Multiplication#

Contents#

Conceptually, the multiplication of two integers \(a\) and \(n\) can be represented as

\(a \times n = \text{sign(n)} \times (\underbrace{a + a + \dotsb + a}_{|n| \,\,\,\text{times}})\)

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.

\(\underbrace{\underbrace{\quad\quad\quad a \quad\quad\quad}_{\text{sub problem}} + \underbrace{\texttt{MULT}(a, n - 1)}_{\text{sub problem}}}_{\text{combine}}\)

\( \begin{aligned} T(n) &= 1 + T(n - 1) \\ &= 1 + 1 + T(n - 2) \\ &= \dots \\ &= 1 + 1 + 1 + \dotsb + T(1) \\ &= \underbrace{1 + 1 + 1 + \dotsb + 1}_{n \,\,\,\text{times}} \\ &= n \\ &= \Theta(n) \\ \end {aligned} \)

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.

\(\underbrace{\underbrace{\texttt{MULT}(a, n/2)}_{\text{sub problem}} + \underbrace{\texttt{MULT}(a, n/2)}_{\text{sub problem}}}_{\text{combine}}\)

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

\(T(n) = 2 T(n/2) + \Theta(1)\)

By the Master Theorem we have

\(a = 2, b = 2, d = 0 \implies d \lt \log_b a \impliedby 0 \lt 1\)

\(T(n) = \Theta(n^{\log_b a}) = \Theta(n^{\log_2 2}) = \boxed{\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) + \Theta(1)\)

By the Master Theorem we have

\(a = 1, b = 2, d = 0 \implies d = \log_b a \impliedby 0 = 0\)

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

Contents