Karatsuba method

1. Apr 30, 2014

jmomo

1. The problem statement, all variables and given/known data
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.

2. Relevant 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

3. The attempt at a solution
I understand Karatsuba method is
(a1r+a0)(b1r+b0) = a1b1r2 +(a1b0+a0b1)r+a0b0
= a1b1r2 +(a1b1r+a0b0r−(a1−a0)(b1−b0)r)+a0b0
= (a0b0r+a0b0)+(a1b1r2+a1b1r)−(a1−a1)(b1−b0)r
but I do not understand how to implement this with only the degree given in the problem.

2. Apr 30, 2014

Zondrina

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.