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

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

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

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

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