MathGroup Archive 2007

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: speed of multiplying polynomials

  • To: mathgroup at smc.vnet.net
  • Subject: [mg72743] Re: speed of multiplying polynomials
  • From: "Roman Pearce" <rpearcea at gmail.com>
  • Date: Wed, 17 Jan 2007 07:00:48 -0500 (EST)
  • References: <200701070439.XAA14676@smc.vnet.net><eoa7fe$n2v$1@smc.vnet.net>

> Actually, there is another issue. I have tried ListConvolve for a few
> cases, and compared its performance to polynomial multiplication in
> certain other computer algebra systems.
...
> But for small degree, larger coefficients (say degree 100, coefficients
> in [0, 10^500]), Mathematica was something like 20 times slower.

I bet it is incrementally adding up large numbers.  For example, if I
have 1000 numbers c[0], ..., c[999], and those numbers are big, then
the obvious algorithm (in C):

for(i=0, sum=0; i < 1000; i++)
  sum += c[i];

is a disaster. Each addition will be linear time in the length of the
partial sum, which is O(n^2).  Adding up n numbers with n digits this
way is O(n^3), whereas a divide-and-conquer approach would be O(n^2).
I have no idea if Mathematica in fact does this, but the mistake is
surprisingly common.  People do this with polynomials as well as
integers, and then they wonder why their algorithms are slow.  It
doesn't matter if it's coded in C, this happens whenever the object
being constructed is large (ie: more than a machine word).


  • Prev by Date: Convolution Integral
  • Next by Date: Re: Re: Re: Re: Limit and Root Objects
  • Previous by thread: Re: speed of multiplying polynomials
  • Next by thread: Re: speed of multiplying polynomials