Re: Re: fastest way to add up a billion numbers
- To: mathgroup at smc.vnet.net
- Subject: [mg74465] Re: [mg74445] Re: fastest way to add up a billion numbers
- From: Devendra Kapadia <dkapadia at wolfram.com>
- Date: Thu, 22 Mar 2007 01:13:10 -0500 (EST)
- References: <es92b2$3oj$1@smc.vnet.net><200703030555.AAA02643@smc.vnet.net>
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
>
>
>
- References:
- Re: fastest way to add up a billion numbers
- From: "dimitris" <dimmechan@yahoo.com>
- Re: fastest way to add up a billion numbers