0 votes

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.
 

in * TF "Emb. Sys. and Rob." by (810 points)

1 Answer

+1 vote
 
Best answer

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].

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

Related questions

Imprint | Privacy Policy
...