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).

**References**:**speed of multiplying polynomials***From:*dmharvey@math.harvard.edu