Services & Resources / Wolfram Forums / MathGroup Archive

MathGroup Archive 2007

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

Search the Archive

Re: Re: Re: Re: fastest way to add up a billion numbers

Certianly for small vaues explicit addition is performed, as can be  
seen from:

Trace[Sum[i, {i, 1, n}] /. n -> 5]

Out[9]=
{{HoldForm[Sum[i, {i, 1, n}]],
    HoldForm[(1/2)*n*(n + 1)]},
   HoldForm[(1/2)*n*(n + 1) /. n -> 5],
   HoldForm[(5*(1 + 5))/2], {HoldForm[1 + 5],
    HoldForm[6]}, HoldForm[(5*6)/2], HoldForm[15]}

In[10]:=
Trace[Sum[i, {i, 1, 5}]]

Out[10]=
{HoldForm[Sum[i, {i, 1, 5}]], {HoldForm[i], HoldForm[1]},
   {HoldForm[i], HoldForm[2]}, {HoldForm[i], HoldForm[3]},
   {HoldForm[i], HoldForm[4]}, {HoldForm[i], HoldForm[5]},
   HoldForm[1 + 2 + 3 + 4 + 5], HoldForm[15]}

The second Trace certianly suggests explicit summation.

On the other hand, indeed we have:

In[22]:=
Trace[Sum[i, {i, 1, 10^9}]]

Out[22]=
{HoldForm[Sum[i, {i, 1, 10^9}]], {HoldForm[10^9],
    HoldForm[1000000000]}, HoldForm[500000000500000000]}


If this is right, it sugges that the algorithm switches at some point  
form explicit addition to using a formula. One could obviously find  
out the point at which the algorithm switches form one approach to  
the other, I suspect the number would b eunder 1000.

Andrzej Kozlowski



On 5 Mar 2007, at 17:20, Daniel Lichtblau wrote:

> 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: Transformation rules - explain please
  • Next by Date: Re: Re: logical/set theoretic programming
  • Previous by thread: Re: Re: Re: Re: fastest way to add
  • Next by thread: Re: fastest way to add up a billion numbers