[Date Index]
[Thread Index]
[Author Index]
Re: Re: fastest way to add up a billion numbers
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
Prev by Date:
**TraditionalForm[HoldForm[...]] query**
Next by Date:
**Re: Re: fastest way to add up a billion numbers**
Previous by thread:
**Re: fastest way to add up a billion numbers**
Next by thread:
**Re: Re: fastest way to add up a billion numbers**
| |