Re: fastest way to add up a billion numbers

*To*: mathgroup at smc.vnet.net*Subject*: [mg74445] Re: fastest way to add up a billion numbers*From*: "Raj" <rajanikanth at gmail.com>*Date*: Wed, 21 Mar 2007 02:56:06 -0500 (EST)*References*: <es92b2$3oj$1@smc.vnet.net><200703030555.AAA02643@smc.vnet.net>

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