Karatsuba gave the optimal way for multiplying two polynomials of degree 1. He reduced the number of multiplications from 4 to 3.
Let the imput for $f$ be the degree of a polynomial and the output the number of multiplications needed to multiply two such polynomials.
Thus
$$f(1) = 3$$
And by iterating
$$ f(2^n -1) =< 3^n$$
That is karatsuba's result.
What are the best ( lowest ) values for
$$f(2) = ??$$ $$f(3) = 9 ??$$ $$f(4) = ??$$ $$f(5) = ??$$ $$f(6)= ??$$ $$f(7)= ??$$
And how do these formula look like ?
$f(2)$ seems to be $6$.
$$(a0 + a1 x + a2 x^2)(b0 + b1 x + b2 x^2)=$$
$$a0 b0 (C + 1 - x - x^2)$$ $$+ a1 b1 (C - x + x^2 - x^3)$$ $$ + a2 b2 (C - x^2 - x^3 + x^4)$$ $$ + (a0 + a1)(b0 + b1) (-C + x)$$ $$ + (a0 + a2)(b0 + b2) (-C + x^2)$$ $$ + (a1 + a2)(b1 + b2) (-C + x^3)$$ $$ + (a0+ a1 + a2)(b0 + b1 + b2) C$$
For an arbitrary polynomial $ C = C(x)$. Hence picking $C$ conviently removes a factor therefore reducing the above $7$ to $6$.
Although this answers the OP partially it also rises questions. Such as how many " C 's " are needed / possible for a given $f(n)$ ? Is the highest number of C's NEC the best solution ? Is there a closed form connection between $f(n)$ and the number of C ' s ? Etc etc
I Will ask Some of them in a seperate thread.
Anyways knowledge of the required amount of C would greatly simplify my computations.
Thank you.