I'm trying to solve a polynomial multiplication problem recursively through using Toom-Cook (Toom-3) once and Karatsuba (Toom-2) five times, although I'm stuck after the first round of Karatsubas.
The base equations are:
P(x)=1+2x+3x^2+4x^3+5x^4
Q(x)=5+4x+3x^2+2x^3+x^4
Work so far:
After padding with 0 to get n%3=0 I broke into 3 Karatsubas:
K1 K2 K3
[1+2x] [3x^2+4x^3] [5x^4+0x^5]
[5+4x] [3x^2+2x^3] [1x^4+0x^5]
and yielded:
K1 => 5+14x+8x^2
K2 => 9+18x+8x^2
K3 => 5
After several awkward attempts, I'm not sure how to proceed from here, but I know I still have two more Karatsubas somewhere along the way. Or have I gone about it the wrong way?
Figured it out. I need to be using Karatsuba within the computation of the Toom-Cook when you multiply the terms instead of trying to break up it beforehand.