[Date Index]
[Thread Index]
[Author Index]
Re: Re: fastest way to add up a billion numbers
Actually, I think we know what happens; Sum simply switches to the
Gauss formula. This is convincingly shown (in my opinion) in my last
post in this thread:
In[1]:=
f[n_Integer] := n
In[2]:=
Sum[f[n], {n, 1, 10^6}]
Out[2]=
500000500000
In[3]:=
Sum[f[n], {n, 1, 10^6 + 1}]
Out[3]=
Sum[f[n], {n, 1, 1000001}]
Because of the way f is defined Sum is not able to use any global
formula so once the limit exceeds 10^6 it can't return any answer. If
you define f without the restriction to Integers you will obtain the
answer very quickly, because Mathematica will be able to use the
Gauss formula.
So this is why I think it is very intriguing to see what happens if
we use NSum. Observe:
In[7]:=
Clear[f]
In[8]:=
f[n_Real] := n
In[9]:=
Timing[NSum[f[n], {n, 1, 10^9}]]
Out[9]=
{0.3369880000000016*Second, 5.000000005*^17}
So how did NSum get this answer? Daniel Lichtblau wrote that he did
not think NSum performed all the additions, but although in general I
always believe in what Daniel writes about Mathematica, this time (I
think it is the first time) I have some doubts. I don't think NSolve
can use any "global" formula, for the same reason that Sum could not
when restricted in this way. But then, how else it could obtain the
answer so quickly? There may be some clever numerical technique that
permits one to compute it without performing all the additions (and
without using the Gauss formula), but I do not know of nay. In any
case, the answer obtained is extremely accurate, which seems to
exclude the possibility of some sort of approximate technique being
used. I find this rather baffling and hope Daniel will find some time
to look into the source code and resolve the mystery.
Andrzej Kozlowski
On 21 Mar 2007, at 08:56, 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
>
>
>
Prev by Date:
**a suprising result from Integrate (Null appeared in the result!)**
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: Re: fastest way to add up a billion numbers**
| |