With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

8.2    COOK-TOOM ALGORITHM

The Cook-Toom algorithm is a linear convolution algorithm for polynomial multiplication. It is based on the Lagrange interpolation theorem. The Lagrange interpolation theorem states that,

“Let β0, … , βn be a set of n + 1 distinct points, and let f(βi), for i = 0, 1, … , n be given. There is exactly one polynomial f(p) of degree n or less that has value f(βi) when evaluated at βi for i = 0, 1, … , n. It is given by

Consider an N-point sequence h = {h0, h1, … , hN−1} and an L-point sequence x = {x0, x1, … , xL−1}. The linear convolution of h and x can be expressed in terms of polynomial multiplication as follows:

where h(p) = hN−1pN−1 + · · · + h1p + h0, x(p) = xL−1pL−1 + · · · + x1p + x0 and s(p) = s L + N−2PL+N−2 + · · · + s1p + s0. The output polynomial s(p) has degree L + N – 2 and has L + N – 1 different coefficients. Therefore, it can be uniquely determined by its values at L + N − 1 different points. Let β0,β1, … ,βL+N−2 be L + N − 1 different real numbers. If s(βi), for i = 0, 1, … , L + N − 2 are known, s(p) can be computed using the Lagrange interpolation theorem as

It can be proved that (8.5) is the unique solution for s(p) given the values of ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required