# Multiplication

This chapter concerns the naive multiplication algorithms and their non-trivial advanced counterparts which all take the form of DnC strategy.

## Integer Multiplication

Recall from what the teachers taught in grade-school a typical integer multiplication may take a form like below:

 ![](/files/-LQpLveSkeJn_xsuGwWk)Figure 1. The grade-school integer multiplication algorithm

In this naive algorithm, the total number of operations is 3 (*3 operations per row for multiplication and addition*)· 3 (*3 rows in total*) = 9. Thus, roughly the running time estimation is с ⋅ n2, bounded by Ο(n2).

It is so widely adopted that less attention been paid to a more complex, yet efficient method.

### [Karatsuba Multiplication](https://en.wikipedia.org/wiki/Karatsuba_algorithm)

Assuming we are multiplying two n-digit numbers x and y; then dividing each of them: x = 10n/2 ⋅ a + b, y = 10n/2 ⋅ c + d

And multiply them together as: x ⋅ y = 10nac + 10n/2(bc + ad) + bd

Then, the algorithm in a [DnC](broken://pages/-LQpLueuStjmV1CIsFw6) pattern has complexity: Τ(n) = 4Τ(n/2) + Ο(n)

Applying the math trick discovered by [Carl Friedrich Gauss](https://en.wikipedia.org/wiki/Carl_Friedrich_Gauss), that (bc + ad) = (a + b)(c + d) - ac - bd, the complexity will be reduced to Τ(n) = 3Τ(n/2) + Ο(n)

#### Pseudocode

```


MULTIPLY(x, y)
  x, y are positive integers
  output: their product

  n = min(x, y)
  if n is 1, return xy

  xL, xR = leftmost [n/2], rightmost [n/2] of x
  yL, yR = leftmost [n/2], rightmost [n/2] of y

  P1 = MULTIPLY(xL, yL)
  P2 = MULTIPLY(xR, yR)
  P3 = MULTIPLY(xL + xR, yL + yR)

  return P1 * 10n + (P3 - P1 - P2) * 10n/2 + P2

```

***Note**: the x and y could be odd or even numbers and produce the correct result by padding bits before recursive calls and dropping bits before combination phase.*

#### Algorithm Analysis

Upon analyzing the complexity of both the naive and Karatsuba multiplication, the \[Master Method]\[master-method] comes into play.

In naive version of integer multiplication, Τ(n) = Ο(n2); The DnC multiplication without optimization would be Τ(n) = 4 Τ(n / 2) + Ο(n) = Ο(nlog24) = Ο(n2);

Obviously, the DnC multiplication without optimization equates the efficiency of the naive algorithm. After applying [Karatsuba multiplication](/algorithm-notes/outline/overview/multiplication.md#karatsuba-multiplication) the overall complexity would be Τ(n) = 3 Τ(n / 2) + Ο(n) = Ο(nlog23) ≈ Ο(n1.59).

Hence, the Karatsuba multiplication beats the naive integer multiplication algorithm in their running time efficiency.

## Matrix Multiplication

Matrix Multiplication, termed as Matrix dot Product as well, is a form of multiplication involving two matrices Χ (n ✗ n), Υ (n ✗ n)like below:

 ![](/files/-LQpLveUF-OI3qK8fFMH)Figure 2. Matrix Dot Product Mathematical Notation

The preceeding formula indicates a Ο(n3) running time given for each entry in the resulting array requires Ο(n) operations and there are Ο(n2) in total.

### Naive Matrix Split

It is intuitive to devise a [DnC](broken://pages/-LQpLueuStjmV1CIsFw6) pattern like below:

 ![](/files/-LQpLveW7IHVkDoWVdxG)Figure 3. Matrix Divided into Blocks

The resulting matrix dot product has 8 sub matrix products, 4 more additions and we could formulate a recurrence relation:

Τ(n) = 8 Τ(n / 2) + Ο(n2)

According to \[Master Method]\[master-method], the recurrence relation above boils down to: Ο(nlog28) = Ο(n3). Same as it is with the default matrix multiplication method though, there is a way to more efficiently compute the result.

### Strassen Matrix Multiplication

Developed by [V. Strassen](https://en.wikipedia.org/wiki/Volker_Strassen), an intricate matrix decomposition magically reduces the complexity;

 ![](/files/-LQpLveY4-CyKPUFAQ3j)Figure 4. Strassen Multiplication Matrix Decomposition

where

 Р1 = A (F - H), Р2 = (A + B) H, Р3 = (C + D) E, Р4 = D (G - E), Р5 = (A + D)(E + H), Р6 = (B - D)(G + H), Р7 = (A - C)(E + F)

Thus, new recurrence relation: Τ(n) = 7Τ(n / 2) + Ο(n2)

By the \[Master Method]\[master-method], the running time is Ο(nlog27) ≈ Ο(n2.81); it beats the [naive-matrix-split](/algorithm-notes/outline/overview/multiplication.md#naive-matrix-split) method of [polynomial time](/algorithm-notes/outline/asymptotic-analysis.md) Ο(n3).

\[master-method]: master-method.md


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://cs-notes.gitbook.io/algorithm-notes/outline/overview/multiplication.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.