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

*To*: mathgroup at smc.vnet.net*Subject*: [mg74310] Re: [mg74230] Re: fastest way to add up a billion numbers*From*: Andrzej Kozlowski <akoz at mimuw.edu.pl>*Date*: Sun, 18 Mar 2007 00:46:21 -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> <et54hq$atu$1@smc.vnet.net> <200703150956.EAA20440@smc.vnet.net>

On 15 Mar 2007, at 10:56, hemphill at hemphills.net wrote: > Andrzej Kozlowski <akoz 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 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. > > I have version 5.1 for Linux. The algorithm switches approaches at > 10^6+1. > > Scott > -- Scott Hemphill hemphill 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

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

**Re: fastest way to add up a billion numbers***From:*hemphill@hemphills.net