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