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>