Re: Re: fastest way to add up a billion numbers
- To: mathgroup at smc.vnet.net
- Subject: [mg74468] Re: [mg74445] Re: fastest way to add up a billion numbers
- From: "Rajanikanth Jammalamadaka" <rajanikanth at gmail.com>
- Date: Thu, 22 Mar 2007 01:14:52 -0500 (EST)
You are most welcome and thanks to everyone who helped.
Regards,
Raj
On 3/21/07, Devendra Kapadia <dkapadia at wolfram.com> wrote:
>
> Hello Raj,
>
> The Sum function uses a procedural method in examples such as
> the one considered below (where both limits of summation are
> positive integers) provided that the length of the summation
> interval does not exceed 10^6.
>
> Beyond this value, we attempt a symbolic evaluation
> after replacing the upper and lower limit with symbolic
> parameters. If an answer is found by this method, then
> the symbolic parameters are replaced by the integer limits,
> thereby providing a fast evaluation in cases such as
> the addition of a billion numbers.
>
> As shown by Andrzej Kozlowski, Sum returns unevaluated if the
> symbolic method, as described above, fails to return an answer.
>
> This problem is fixed in the development version, where Sum
> tries the procedural method again in case symbolic evaluation
> has failed. Hence Andrzej's example returns an answer in
> this version when the upper limit is 10^6+1.
>
> ===========================
>
> In[2]:= f[n_Integer] := n
>
> In[3]:= Timing[Sum[f[n], {n, 1, 10^6}]]
>
> Out[3]= {1.55, 500000500000}
>
> In[4]:= Timing[Sum[f[n], {n, 1, 10^6+1}]]
>
> Out[4]= {2.27, 500001500001}
>
> ===========================
>
> We also expect to provide users with an option for setting the
> limit (10^6) in this version.
>
> Thanks to you and everyone else for your comments on this
> problem and apologies for the confusion that it has
> caused.
>
> Sincerely,
>
> Devendra Kapadia,
> Wolfram Research, Inc.
>
>
>
>
>
> On Wed, 21 Mar 2007, 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
> >
> >
> >
>
--
"For him who has conquered the mind, the mind is the best of friends; but
for one who has failed to do so, his very mind will be the greatest enemy."
Rajanikanth