Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

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>