Karatsuba multiplication algorithm complexity

Question

Can someone please explain what each of the operations listed refer to explicitly?

For instance, how are there "4 additions of 2k-bit numbers"? From inspecting that last expression, I only see a single 2k-bit term, $2^{2k}m_1n_2$

Answer 1

$2k$-bit numbers refers to the length of the number, not its position.

The description is a bit misleading because it distinguishes between additions and subtractions for $k$-bit numbers, but counts a subtraction of $2k$-bit numbers as an addition. Also, $n_2$ is a typo, must be $n_1$. To match the description exactly, we need one more simplification

$$2^{2k} m_1 n_1 + 2^k m_1 n_1 - 2^k (m_1 - m_0)(n_1 - n_0) + 2^k m_0 n_0 + m_0 n_0$$ $$=2^{2k} m_1 n_1 + 2^k m_1 n_1 + 2^k (m_0 - m_1)(n_1 - n_0) + 2^k m_0 n_0 + m_0 n_0$$

Now let's look at the operations.

Two subtractions are $m_0 - m_1$ and $n_1 - n_0$. Since $m_0$ and $m_1$ are positive numbers of length $k$ bit, the difference is a $k$-bit number with sign, the same for $n_1 - n_0$. (Technically it requires $k+1$ bits, and to avoid the multiplication of $k+1$-bit numbers in the next step we do need some tricks here, but it will still be linear in $k$)

Three multiplications are $m_1 n_1$, $(m_0 - m_1)(n_1 - n_0)$, and $m_0 n_0$. All multiplicands here have length $k$ (in the middle case with sign), so the products have length $2k$.

The four additions are the top level additions in the big formula. Technically the numbers involved are at most $4k$ bits ($2^{2k} m_1 n_1$ can be $4k$ bits), but they are counted as $2k$-bit additions because to add to something multiplied by a power of $2$, for example $2^{2k} m_1 n_1$, we just do $2k$-bit addition, but shifted so that we start adding to the position we need.