TOPICS
Search

Clipped Product


A clipped product is a specified range of digits or coefficients of a product, computed without necessarily forming the remaining parts (Norman and Watt 2024). Suppose

 u=sum_(i)u_it^i.
(1)

For a finite interval I of integer indices, define the clipped value and clipped product by

clip_(t,I)(u)=sum_(i in I)u_it^i
(2)
clip_(t,I)(fg)=sum_(i in I)(fg)_it^i.
(3)

For integers, t=B>1 is the radix and the u_i are base-B digits. For polynomials, t=x is an indeterminate and the u_i are coefficients in the underlying polynomial ring.

For example, let f(x)=1+2x+3x^2 and g(x)=4+5x+6x^2. Then

f(x)g(x)=4+13x+28x^2+27x^3+18x^4
(4)
clip_(x,{1,2})(fg)=13x+28x^2.
(5)

For polynomial products, a requested coefficient range depends only on selected coefficient pairs. For integer products, a carry from discarded lower digits can enter the requested range, so additional lower product columns may be needed. Algorithms for clipped products can be based on classical multiplication, Karatsuba multiplication, or the fast Fourier transform. Products retaining only a low, middle, or high portion are special cases of clipped products (Norman and Watt 2024).


See also

Coefficient, Convolution, Fast Fourier Transform, Karatsuba Multiplication, Multiplication, Polynomial

Explore with Wolfram|Alpha

References

Norman, A. C. and Watt, S. M. "Computing Clipped Products." In Boulier, F.; Mou, C.; Sadykov, T. M.; and Vorozhtsov, E. V. (Eds.), Computer Algebra in Scientific Computing (CASC 2024). Cham, Switzerland: Springer, pp. 273-291, 2024. https://doi.org/10.1007/978-3-031-69070-9_16.

Cite this as:

Weisstein, Eric W. "Clipped Product." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/ClippedProduct.html

Subject classifications