WOLFRAM

Services & Resources / Wolfram Forums / MathGroup Archive

MathGroup Archive 2007

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

Search the Archive

Re: Re: Re: fastest way to add up a billion numbers

On reflection, perhaps the fact that NSum gets "the right answer" in  
this particular example so quickly is not so amazing, after all.  
Obviously one can easily get a very accurate answer in such a simple  
case by using a very simple numerical method; for example by  
constructing an interpolating function using a small number of data  
and then using extrapolation; e.g.

f=Interpolation[Table[{n,Sum[k,{k,1,n}]},{n,1,10^3}]];

and then:

f[10^9]

500000000500000000

Obviously NSum does something much more sophisticated, but I was  
wrong to be surprised at its ability to get an accurate answer for  
this kind of regular sum. We can see that things are quite different  
with irregular sums, for example with sums of randomly generated  
numbers. Compare the behaviour of Sum (which really adds up numbers  
up to the limit of 10^6) and NSum, which clearly does not, in this case:


In[1]:=
Clear[f]

In[2]:=
SeedRandom[1];

In[3]:=
f[x_] := Random[];

In[4]:=
Timing[Sum[f[i], {i, 1, 10^6}]]

Out[4]=
{60.354257999999994*Second,
   500033.1729350898}

In[5]:=
SeedRandom[1];

In[6]:=
Timing[NSum[f[i], {i, 1, 10^6}]]

 From In[6]:=
SequenceLimit::The general form of the sequence could not
     be determined, and the result may be incorrect.


{0.13582199999999034*Second,
   4.31715028543848}


This, I think, shows clearly that it is not a good idea to use NSum  
for this sort of thing. In fact, even for a small number of terms  
NSum does not actually simply add the numbers it is supposed to sum.  
This can lead to curious results. Compare the answers returned by Sum  
and NSum below:


f[x_]:=Random[];


SeedRandom[1];


Sum[f[i],{i,1,3}]


1.20449


SeedRandom[1];


NSum[f[i],{i,1,3}]


0.86343

Since the random seed was the same, the values of any three  
successive random numbers generated by applying f would have to be  
the same, but the sums returned by Sum and NSum are quite different.

Andrzej Kozlowski




On 22 Mar 2007, at 07:09, Andrzej Kozlowski wrote:

> 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: Re: Re: Definite Integration in Mathematica
  • Next by Date: Re: Applying a list of functions to a single number
  • Previous by thread: Re: Re: fastest way to add up a billion numbers
  • Next by thread: Re: Re: fastest way to add up a billion numbers