Karatsuba Method Homework: Check 3(r-1) Multiplications in F

[jmomo]

Homework Statement

For polynomials f(x),g(x) of degree d = 2^(r−1)−1, check that multiplying f(x) and g(x) by the Karatsuba method requires 3^(r-1) multiplications in the field F.

Homework Equations

You can can more clearly see problem on page 383 #10:
http://igortitara.files.wordpress.com/2010/04/a-concrete-introduction-to-higher-algebra1.pdf

The Attempt at a Solution

I understand Karatsuba method is
(a₁r+a₀)(b₁r+b₀) = a₁b₁r² +(a₁b₀+a₀b₁)r+a₀b₀
= a₁b₁r² +(a₁b₁r+a₀b₀r−(a₁−a₀)(b₁−b₀)r)+a₀b₀
= (a₀b₀r+a₀b₀)+(a₁b₁r²+a₁b₁r)−(a₁−a₁)(b₁−b₀)r
but I do not understand how to implement this with only the degree given in the problem.

 

[STEMucator]

Karatsuba multiplication has an advantage over the usual multiplication algorithm when $n$ is large enough.

For example, take the polynomials $f(x)$ and $g(x)$ and suppose that $r=1$. Then $d = 0$ and the Karatsuba method requires only $1$ multiplication since $f(x)$ and $g(x)$ are both constant.

Now to see the effectiveness, suppose $r = 2$. Then $d = 1$ and the Karatsuba method requires $3$ multiplications. Although by the usual FOIL method, we would require $4$ multiplications.

I believe induction will be of assistance.