Suggest edit — SU-CS161 SEP232025

Title

Name

Note

---
title: "SU-CS161 SEP232025"
source: https://www.jemoka.com/posts/kbhsu_cs161_sep232025/
date: 2025-09-23
---

Divide and Conquer Break problem into smaller sub-problems.
example: multiplication Multiplying by powers of ten is easy, so we can break a multiplication into smaller groups.
For instance, we can break \(n\) digit integer into:
\begin{equation} [x_1, x_2, \dots, x_{\frac{n}{2}}] \times 10^{\frac{n}{2}} + [x_{\frac{n}{2}+1}, x_{\frac{n}{2}+2}, \dots] \end{equation}
Then we can multiply two large values by writing:
\begin{align} x \times y &amp;= \qty(a \times 10^{\frac{n}{2}} + b ) \qty(c \times 10^{\frac{n}{2}} + d) \\ &amp;= \qty(a \times c ) 10^{n} + \qty(a \times d + c \times b) 10^{\frac{n}{2}} + \qty( b \times d) \end{align}
Doing this is still \(4^{\log_{2}\qty(n)} = n^{2}\), which is where we started.
Karatsuba Integer Multiplication If we don&rsquo;t have to compute 4 multiplication terms, it can be better. We can make this not 4 terms by observing that computing:
\(ac\) \(bd\) \(\qty(a+b) \qty(c+d) = ac + bd + bc + ad\) We can get the middle term by \(\qty(a+b) \qty(c+d) - ac - bd\). This is now \(3^{\log_{2}\qty(n)} \approx n^{1.6}\), which is more efficient.