# Toom-Cook Multiplication. How many x's to use for the M-Matrix

I wondered by the toom-cook Radix-B multiplication about the correlation from the number of interpolation points x's n and the number of digits m,n of the numbers that will be multiplied (i.e.: a=\Sigmam-1i=0 a*Bi).
So is there a rule how many x the multiplication need?

Edit: I got a hypotheses let a(x) a polynome of degree i and b(x) a polynome of degree j.
The result will be a polynome of degree i+j, so therefor we need i+j+1 interpolation points x's. Is this hypotheses right

P.S.: the indexing in the slides are confusion in the explaination in the slides.

+1 vote

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*R^{1} + a*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,...,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*x[i]^{1} + a*x[i]^{0}
• B[i] := b[k-1]*x[i]^{k-1} + ... + b*x[i]^{1} + b*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].

by (162k points)
selected by
ah, thank you. Oh I missed to reread on this slide.

+1 vote