Re: Re: Re: Re: fastest way to add
- To: mathgroup at smc.vnet.net
- Subject: [mg74025] Re: [mg73991] Re: [mg73973] Re: [mg73907] Re: fastest way to add
- From: Daniel Lichtblau <danl at wolfram.com>
- Date: Tue, 6 Mar 2007 05:33:06 -0500 (EST)
- References: <es92b2$3oj$1@smc.vnet.net> <200703030555.AAA02643@smc.vnet.net> <200703040453.XAA25305@smc.vnet.net> <200703050946.EAA19233@smc.vnet.net>
Andrzej Kozlowski wrote:
> If you compare these three timing (and particularly the last one) you
> will see that your suspision is wrong.
>
> In[1]:=
> Timing[Sum[i, {i, 1, 10^9}]]
>
> Out[1]=
> {0.11999199999999999*Second, 500000000500000000}
>
> In[2]:=
> Timing[NSum[i, {i, 1, 10^9}]]
>
> Out[2]=
> {0.0862520000000001*Second, 5.000000005*^17}
>
> In[3]:=
> Timing[Sum[i, {i, 1, n}] /. n -> 10^9]
>
> Out[3]=
> {0.02608200000000005*Second, 500000000500000000}
>
> Only the last method (the fastest) does what you suspected (which is
> why I do not think it a "legitimate" solution to the posted problem).
> The fastest method that actually adds up numbers uses NSum (which of
> course gives only an approaximate answer).
>
> Andrzej Kozlowski
>
> On 4 Mar 2007, at 05:53, Murray Eisenberg wrote:
>
>
>>I wonder what the timing for a sum of the form Sum[n,{n,nstart,nend}]
>>really indicates. I suspect that Mathematica is not actually summing
>>but rather just uses Gauss' well-known closed-form formula for such a
>>sum of consecutive positive integers.
>> [...]
None of these add all the numbers. Actually I am not absolutely certain
of what NSolve does but I really doubt it is doing the arithmetic that
fast. To see Sum speed when it does add everything try Sum[i, {i,10^6}]
(I think Bill Rowe pointed this out in a previous response).
I would guess the relative slowness of Out[1] vs Out[3] can be explained
by a couple of things. One is that quite possibly some symbolic
summation code is being loaded on that first invocation. Even accounting
for this that sum will be slower than teh symbolic-with-replacement. I
will speculate that the rest of the speed difference is from
preprocessing. I suppose I could check the code but, well, I really
don't want to.
What I have wondered is why the original note avoided the explicit
formula. If it was because the typical data set to be summed is huge but
does not have structure amenable to symbolic methods, then something
like Total will be needed. In this case I think one must split the input
into chunks of manageable size, say 10^7 elements, so as to avoid
running out of memory. But in this case it would be fairly clear that
Sum cannot be used, because there would be no way to specify the general
summand. Well, one could do Sum[hugetable[[j]],{j,10^9}] but if that
were optimal nobody would need Total.
Daniel Lichtblau
Wolfram Research
- References:
- Re: fastest way to add up a billion numbers
- From: "dimitris" <dimmechan@yahoo.com>
- Re: Re: fastest way to add up a billion numbers
- From: Murray Eisenberg <murray@math.umass.edu>
- Re: Re: Re: fastest way to add up a billion numbers
- From: Andrzej Kozlowski <akoz@mimuw.edu.pl>
- Re: fastest way to add up a billion numbers