Divide and conquer! 💪
How complex is multiplication?
- tags
- #Multiplication #Algorithmic
- categories
- Algorithms Complexity Theory
- reading time
- 2 minutes
The time complexity describes the amount of computer time it takes to run an algorithm. It is estimated by counting the number of elementary operations performed by the algorithm. Since an algorithm’s running time may vary among different inputs of the same size, one commonly considers the worst-case time. Algorithmic complexities are classified according to the type of function appearing in the big O notation. Here are some examples:
| Name | Time complexity |
|---|---|
| Constant time | $\mathcal{O}(1) $ |
| Logarithmic time | $\mathcal{O}(\log n) $ |
| Linear time | $\mathcal{O}(n) $ |
| Linearithmic time | $\mathcal{O}(n \log n)$ |
| Quadratic time | $\mathcal{O}(n^2) $ |
| Polynomial time | $2^{\mathcal{O}(\log n)} = poly(n)$ |
| Exponential time | $2^{poly(n)}$ |
Multiplication algorithms
Schoolbook multiplication
Consider this example $102 \times 257$:
| 1 | 0 | 2 | |||
|---|---|---|---|---|---|
| $\times$ | 2 | 5 | 7 | ||
| ——– | —- | —- | —- | —- | —- |
| 7 | 1 | 4 | |||
| $+$ | 5 | 1 | 0 | ||
| $+$ | 2 | 0 | 4 | ||
| ——– | —- | —- | —- | —- | —- |
| 2 | 6 | 2 | 1 | 4 |
-
Without worrying about additions, how many digit multiplications we need?
-
Suppose we have two n-digit numbers and wish to multiply them. What is the (worst-case) time complexity of this operation?
Divide-and-conquer multiplication
Can we do any better?
2-digit numbers
Consider two 2-digit numbers $X$ and $Y$. Their base-10 representation is $X = 10x_1 + x_0$ and $Y = 10y_1 + y_0$. Their product is $X \cdot Y = (10x_1 + x_0)(10y_1 + y_0) = 100x_1y_1 + 10(x_1y_0+x_0y_1) + x_0y_0$.
- How many multiplications this product involves?
- Can you re-write the middle term $x_1y_0 + x_0y_1$ to re-use $x_0y_0$ and $x_1y_1$? How many multiplications the product involves now?
4-digit numbers
Now consider two 4-digit numbers $X$ and $Y$. We can write them as $X = 100x_1 + x_0$ and $Y = 100y_1 + y_0$.
- Can you re-do the same optimization as for 2-digits?
- Multiply 2345 and 6789 following this optimization.
n-digit numbers
In general we can write two n-digit numbers as $X = 10^{n/2}x_0 + x_1$ and $Y = 10^{n/2}y_0 + y_1$.
- Can you derive an algorithm than involves less digit multiplications than the schoolbook method?
- What is the time complexity of your algorithm?
