Re: Re: fastest way to add up a billion numbers
- To: mathgroup at smc.vnet.net
- Subject: [mg74311] 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:53 -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> <C228A074-6F00-4632-ACBD-CFDF921B8D3C@mimuw.edu.pl>
On 17 Mar 2007, at 17:34, Andrzej Kozlowski wrote:
>
> 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
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: 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
- Re: fastest way to add up a billion numbers