Your hypothesis is right. You find the information (currently) on slide 83 of the PRAM chapter, and I found no bug or confusion there. The explanation is as follows for Toom/Cook[k]:
- split the digit sequence of the radix-B number into k parts and obtain this way a polynomial of degree k-1, i.e., a[k-1]*R^{k-1} + ... + a[1]*R^{1} + a[1]*R^{0} where R := B^p for p digits in one part a[i]
- multiplying two polynomials of degrees x and y yields a polynomial of degree x+y
- thus, multiplying the two numbers (which are now interpreted as polynomials) yields a product polynomial of degree (k-1)+(k-1) = 2k-2
- any polynomial of degree g can be determined by g+1 interpolation points
- hence, we need 2k-1 interpolation points to determine the coefficients of the product polynomial
- Thus, we choose now some points x[0],...,x[2k-2] and evaluate the two polynomial at these points, i.e., we compute
- A[i] := a[k-1]*x[i]^{k-1} + ... + a[1]*x[i]^{1} + a[1]*x[i]^{0}
- B[i] := b[k-1]*x[i]^{k-1} + ... + b[1]*x[i]^{1} + b[1]*x[i]^{0}
- next we compute the values of the product polynomial, by simply multiplying A[i]*B[i] for each interpolation point x[i]
- with the 2k-1 pairs (x[i], A[i]*B[i]) we can now determine the coefficients of the product polynomial
- a final step is required to adjust the coefficients such that they are less than B^p
For the multiplications A[i]*B[i] one proceeds recursively in the same way so that an algorithm with work O(n^log_k(2k-1)) and depth O(log(n)^2) is obtained.
There is no correlation between the number of digits of the numbers and the parameter k. Toom/Cook[k] is splitting any given number with n digits into k parts (maybe additional zero digits have to be prepended). The parameter k is thereby fixed by the algorithm Toom/Cook[k].
