WOLFRAM

Services & Resources / Wolfram Forums / MathGroup Archive

MathGroup Archive 2007

[Date Index] [Thread Index] [Author Index]

Search the Archive

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