Re: speed of multiplying polynomials

*To*: mathgroup at smc.vnet.net*Subject*: [mg72563] Re: speed of multiplying polynomials*From*: mcmcclure at unca.edu*Date*: Mon, 8 Jan 2007 05:20:53 -0500 (EST)*References*: <enpste$e5t$1@smc.vnet.net>

On Jan 6, 11:28 pm, dmhar... at math.harvard.edu wrote: > I'm trying to figure out how fast mathematica can multiply polynomials > with integer coefficients. Depends how you do it. Here's very simple way to multiply polynomials. poly := Sum[Random[Integer, {1, 1000}]*x^i, {i, 0, 1000}]; SeedRandom[1]; Expand[poly*poly]; // Timing {1.20313 Second, Null} On the other hand, suppose we represent a polynomial as a list; then, we can use ListConvolve. listpoly := Table[Random[Integer, {1, 1000}], {1001}]; SeedRandom[1]; ListConvolve[PadRight[listpoly, 2001], PadRight[listpoly, 2001], 1]; // Timing {0.002973 Second, Null} About 400 times faster. You can remove the semi-colons to examine the output and see that the results are equivalent. Lists are a fundamental data structure and in this case we are able to express the desired object using a list and we can express the operation using a command which acts on Lists. Symbolic manipulation, by contrast, is likely to be much slower. Mark