Prev: Minimization with constraint expresses as CDF[] >=
Next: pursuit curve (differential equations)
From: Roman Pearce on 17 Jan 2007 06:15
> 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).

From: Roman Pearce on 20 Jan 2007 02:41
Roman Pearce wrote:
> 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.

Sorry, this is nonsense. I was confusing addition with multiplication.

First  |  Prev  | 
Pages: 1 2 3
Prev: Minimization with constraint expresses as CDF[] >=
Next: pursuit curve (differential equations)