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

*To*: mathgroup at smc.vnet.net*Subject*: [mg74138] Re: [mg73991] Re: [mg73973] Re: [mg73907] Re: fastest way to add up a billion numbers*From*: Andrzej Kozlowski <akoz at mimuw.edu.pl>*Date*: Mon, 12 Mar 2007 22:04:52 -0500 (EST)*References*: <es92b2$3oj$1@smc.vnet.net> <200703030555.AAA02643@smc.vnet.net> <200703040453.XAA25305@smc.vnet.net> <200703050946.EAA19233@smc.vnet.net> <45EC435A.30700@wolfram.com>

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 >

**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>