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

*To*: mathgroup at smc.vnet.net*Subject*: [mg74511] Re: [mg74458] Re: [mg74445] Re: fastest way to add up a billion numbers*From*: Andrzej Kozlowski <akoz at mimuw.edu.pl>*Date*: Fri, 23 Mar 2007 19:14:19 -0500 (EST)*References*: <es92b2$3oj$1@smc.vnet.net><200703030555.AAA02643@smc.vnet.net> <200703210756.CAA01256@smc.vnet.net> <200703220609.BAA16805@smc.vnet.net>

On reflection, perhaps the fact that NSum gets "the right answer" in this particular example so quickly is not so amazing, after all. Obviously one can easily get a very accurate answer in such a simple case by using a very simple numerical method; for example by constructing an interpolating function using a small number of data and then using extrapolation; e.g. f=Interpolation[Table[{n,Sum[k,{k,1,n}]},{n,1,10^3}]]; and then: f[10^9] 500000000500000000 Obviously NSum does something much more sophisticated, but I was wrong to be surprised at its ability to get an accurate answer for this kind of regular sum. We can see that things are quite different with irregular sums, for example with sums of randomly generated numbers. Compare the behaviour of Sum (which really adds up numbers up to the limit of 10^6) and NSum, which clearly does not, in this case: In[1]:= Clear[f] In[2]:= SeedRandom[1]; In[3]:= f[x_] := Random[]; In[4]:= Timing[Sum[f[i], {i, 1, 10^6}]] Out[4]= {60.354257999999994*Second, 500033.1729350898} In[5]:= SeedRandom[1]; In[6]:= Timing[NSum[f[i], {i, 1, 10^6}]] From In[6]:= SequenceLimit::The general form of the sequence could not be determined, and the result may be incorrect. {0.13582199999999034*Second, 4.31715028543848} This, I think, shows clearly that it is not a good idea to use NSum for this sort of thing. In fact, even for a small number of terms NSum does not actually simply add the numbers it is supposed to sum. This can lead to curious results. Compare the answers returned by Sum and NSum below: f[x_]:=Random[]; SeedRandom[1]; Sum[f[i],{i,1,3}] 1.20449 SeedRandom[1]; NSum[f[i],{i,1,3}] 0.86343 Since the random seed was the same, the values of any three successive random numbers generated by applying f would have to be the same, but the sums returned by Sum and NSum are quite different. Andrzej Kozlowski On 22 Mar 2007, at 07:09, Andrzej Kozlowski wrote: > Actually, I think we know what happens; Sum simply switches to the > Gauss formula. This is convincingly shown (in my opinion) in my last > post in this thread: > > In[1]:= > f[n_Integer] := n > > In[2]:= > Sum[f[n], {n, 1, 10^6}] > > Out[2]= > 500000500000 > > In[3]:= > Sum[f[n], {n, 1, 10^6 + 1}] > > Out[3]= > Sum[f[n], {n, 1, 1000001}] > > Because of the way f is defined Sum is not able to use any global > formula so once the limit exceeds 10^6 it can't return any answer. If > you define f without the restriction to Integers you will obtain the > answer very quickly, because Mathematica will be able to use the > Gauss formula. > So this is why I think it is very intriguing to see what happens if > we use NSum. Observe: > > In[7]:= > Clear[f] > > In[8]:= > f[n_Real] := n > > In[9]:= > Timing[NSum[f[n], {n, 1, 10^9}]] > > Out[9]= > {0.3369880000000016*Second, 5.000000005*^17} > > So how did NSum get this answer? Daniel Lichtblau wrote that he did > not think NSum performed all the additions, but although in general I > always believe in what Daniel writes about Mathematica, this time (I > think it is the first time) I have some doubts. I don't think NSolve > can use any "global" formula, for the same reason that Sum could not > when restricted in this way. But then, how else it could obtain the > answer so quickly? There may be some clever numerical technique that > permits one to compute it without performing all the additions (and > without using the Gauss formula), but I do not know of nay. In any > case, the answer obtained is extremely accurate, which seems to > exclude the possibility of some sort of approximate technique being > used. I find this rather baffling and hope Daniel will find some time > to look into the source code and resolve the mystery. > > Andrzej Kozlowski > > > > On 21 Mar 2007, at 08:56, Raj wrote: > >> Thanks for the analysis Andrzej. It will certainly be interesting to >> know what happens after n exceeds 10^6 >> >> Regards, >> >> Raj >> >> >> On Mar 17, 10:51 pm, Andrzej Kozlowski <a... at mimuw.edu.pl> wrote: >>> On 17 Mar 2007, at 17:34, Andrzej Kozlowski wrote: >>> >>> >>> >>> >>> >>>> On 15 Mar 2007, at 10:56, hemph... at hemphills.net wrote: >>> >>>>> Andrzej Kozlowski <a... at mimuw.edu.pl> writes: >>> >>>>>> 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 certainly 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. >>> >>>>> I have version 5.1 for Linux. The algorithm switches >>>>> approaches at >>>>> 10^6+1. >>> >>>>> Scott >>>>> -- Scott Hemphill hemph... at alumni.caltech.edu >>>>> "This isn't flying. This is falling, with style." -- Buzz >>>>> Lightyear >>> >>>> One interesting way to demonstrate this is: >>> >>>> f[n_Integer] := n >>> >>>> Timing[Sum[f[n], {n, 1, 10^6}]] >>> >>>> {4.7203479999999995*Second, 500000500000} >>> >>>> Timing[Sum[f[n], {n, 1, 10^9}]] >>> >>>> {0.226001000000001*Second, Sum[f[n], {n, 1, 1000000000}]} >>> >>>> Note that it took Sum a non-trivial amount of time to return the >>>> last answer! >>> >>>> Now, this is also interesting: >>> >>>> g[n_Real] := n >>> >>>> Timing[NSum[g[n], {n, 1, 10^9}]] >>> >>>> {0.2843939999999998*Second, 5.000000005*^17} >>> >>>> It would be nice to have at least a reasonable hypothesis about >>>> what happened here. >>> >>>> Andrzej Kozlowski >>> >>> Of course it should have been: >>> >>> Timing[Sum[f[n], {n, 1, 10^6 + 1}]] >>> >>> {0.19891900000000007*Second, Sum[f[n], {n, 1, 1000001}]} >>> >>> Andrzej Kozlowski >> >> >> > >

**References**:**Re: fastest way to add up a billion numbers***From:*"dimitris" <dimmechan@yahoo.com>

**Re: fastest way to add up a billion numbers***From:*"Raj" <rajanikanth@gmail.com>

**Re: Re: fastest way to add up a billion numbers***From:*Andrzej Kozlowski <akoz@mimuw.edu.pl>