Karatsuba Method

Question

For polynomials $f(x)$, $g(x)$ of degree $d = 2^{r-1}-1$, how do I check that multiplying $f(x)$ and $g(x)$ by the Karatsuba method requires $3^{r-1}$ multiplications in the field $F$?

Answer 1

Without loss of generality, let us set $d = 2^r - 1$ and show that $3^r$ multiplications are required.

We have $$ f(x) = a_0 + a_1x + \ldots + a_{2^r - 1}x^{2^r - 1}, $$ $$ g(x) = b_0 + b_1x + \ldots + b_{2^r - 1}x^{2^r - 1}. $$

Now the karatsuba algorithm will split each of these in $2$. For example, $$ f(x) = f_1(x) + f_2(x)x^{2^{r - 1}}, $$ where $f_1(x)$ and $f_2(x)$ are both $2^{r - 1} - 1$ degree polynomials.

Defining $g(x)$ the same, the algorithm would then multiply $$ f_1(x)g_1(x)[(f_1(x) + f_2(x))(g_1(x) + g_2(x)) - f_2(x)g_2(x) - f_1(x)g_1(x))]x^{2^{r-2}} + f_2(x)g_2(x)x^{2^{r-1}}.$$

This creates $3$ multiplications, namely $f_1(x)g_1(x)$, $f_2(x)g_2(x)$, and $(f_1(x) + f_2(x))(g_1(x) + g_2(x))$.

But all of these are degree $2^{r-1} - 1$ degree polynomials. Notice that this process will be the same for each of these polynomials, so lets reduce this to a recurrence relation,

$$ T(2^r) = 3T(2^{r-1}), T(1) = 1. $$

This is valid because eventually the polynomials will be completely reduced and return 1 multiplication, but on the way down, each chain splits into 3 new multiplication chains as we have seen.

This recurrence relation is easy to solve, $ T(2^r) = 3^kT(2^{r-k}) $ and setting $k = r$, we have $T(2^r) = 3^rT(1) = 3^r$.

So the statement is valid.