MathGroup Archive 2007

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

Search the Archive

Re: Re: Re: Re: fastest way to add

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

  • Prev by Date: Re: Rigid body equations
  • Next by Date: Re: beginner plot function with parameter
  • Previous by thread: Re: Re: Re: fastest way to add up a billion numbers
  • Next by thread: Re: Re: Re: Re: fastest way to add up a billion numbers