[Date Index]
[Thread Index]
[Author Index]
Re: Re: Re: Re: fastest way to add up a billion numbers
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.
Andrzej Kozlowski
On 5 Mar 2007, at 17:20, Daniel Lichtblau wrote:
> Andrzej Kozlowski wrote:
>> If you compare these three timing (and particularly the last one)
>> you will see that your suspision is wrong.
>> In[1]:=
>> Timing[Sum[i, {i, 1, 10^9}]]
>> Out[1]=
>> {0.11999199999999999*Second, 500000000500000000}
>> In[2]:=
>> Timing[NSum[i, {i, 1, 10^9}]]
>> Out[2]=
>> {0.0862520000000001*Second, 5.000000005*^17}
>> In[3]:=
>> Timing[Sum[i, {i, 1, n}] /. n -> 10^9]
>> Out[3]=
>> {0.02608200000000005*Second, 500000000500000000}
>> Only the last method (the fastest) does what you suspected (which
>> is why I do not think it a "legitimate" solution to the posted
>> problem). The fastest method that actually adds up numbers uses
>> NSum (which of course gives only an approaximate answer).
>> Andrzej Kozlowski
>> On 4 Mar 2007, at 05:53, Murray Eisenberg wrote:
>>> I wonder what the timing for a sum of the form Sum[n,
>>> {n,nstart,nend}]
>>> really indicates. I suspect that Mathematica is not actually
>>> summing
>>> but rather just uses Gauss' well-known closed-form formula for
>>> such a
>>> sum of consecutive positive integers.
>>> [...]
>
> None of these add all the numbers. Actually I am not absolutely
> certain of what NSolve does but I really doubt it is doing the
> arithmetic that fast. To see Sum speed when it does add everything
> try Sum[i, {i,10^6}] (I think Bill Rowe pointed this out in a
> previous response).
>
> I would guess the relative slowness of Out[1] vs Out[3] can be
> explained by a couple of things. One is that quite possibly some
> symbolic summation code is being loaded on that first invocation.
> Even accounting for this that sum will be slower than teh symbolic-
> with-replacement. I will speculate that the rest of the speed
> difference is from preprocessing. I suppose I could check the code
> but, well, I really don't want to.
>
> What I have wondered is why the original note avoided the explicit
> formula. If it was because the typical data set to be summed is
> huge but does not have structure amenable to symbolic methods, then
> something like Total will be needed. In this case I think one must
> split the input into chunks of manageable size, say 10^7 elements,
> so as to avoid running out of memory. But in this case it would be
> fairly clear that Sum cannot be used, because there would be no way
> to specify the general summand. Well, one could do Sum[hugetable
> [[j]],{j,10^9}] but if that were optimal nobody would need Total.
>
>
> Daniel Lichtblau
> Wolfram Research
>
Prev by Date:
**Re: Transformation rules - explain please**
Next by Date:
**Re: Re: logical/set theoretic programming**
Previous by thread:
**Re: Re: Re: Re: fastest way to add**
Next by thread:
**Re: fastest way to add up a billion numbers**
| |