Services & ResourcesWolfram ForumsMathGroup Archive

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

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

• To: mathgroup at smc.vnet.net
• Subject: [mg73998] Re: [mg73973] Re: [mg73907] Re: fastest way to add up a billion numbers
• From: Murray Eisenberg <murray at math.umass.edu>
• Date: Mon, 5 Mar 2007 04:50:42 -0500 (EST)
• Organization: Mathematics & Statistics, Univ. of Mass./Amherst
• References: <es92b2$3oj$1@smc.vnet.net> <200703030555.AAA02643@smc.vnet.net> <200703040453.XAA25305@smc.vnet.net> <A35F0ECC-2DB3-4260-8C66-8BC9008E14DA@mimuw.edu.pl>
• Reply-to: murray at math.umass.edu

Very interesting -- and then I'm surprised to conclude that Mathematica 
does NOT, apparently, attempt to use the Gauss formula even in the first 
case.

I should think efficiency would dictate using it; but then perhaps the 
extra processing needed to check whether a particular invocation of Sum 
could use that special case result overall would decrease efficiency of Sum.

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.
>>
>> dimitris wrote:
>>> There is recent post of mine asking something relevant here.
>>>
>>> You can find also a relevant thread here:
>>>
>>> http://forums.wolfram.com/mathgroup/archive/2005/May/msg00600.html
>>>
>>> One billion numbers?
>>> Here is what I get to my PC
>>>
>>> In[3]:=
>>> Range[10^9]
>>>> From In[3]:=
>>> No more memory available.
>>> Mathematica kernel has shut down.
>>> Try quitting other applications and then retry.
>>>
>>> In[1]:=
>>> Table[i, {i, 1, 10^9}];
>>>
>>>> From In[1]:=
>>> No more memory available.
>>> Mathematica kernel has shut down.
>>> Try quitting other applications and then retry.
>>>
>>> Anyway...
>>>
>>> lst = Range[10^6];
>>>
>>> Timing[Plus @@ lst]
>>> {0.34299999999999997*Second, 500000500000}
>>>
>>> Timing[Total[lst]]
>>> {0.2659999999999999*Second, 500000500000}
>>>
>>> Timing[Fold[Plus, 0, lst]]
>>> {0.703*Second, 500000500000}
>>>
>>> Timing[lst /. {x_, y___} -> x + y]
>>> {0.45300000000000007*Second, 500000500000}
>>>
>>> Timing[Tr[lst]]
>>> {0.3899999999999997*Second, 500000500000}
>>>
>>> Timing[Sum[lst[[i]], {i, 1, 10^6}]]
>>> {1.4379999999999997*Second, 500000500000}
>>>
>>>
>>> But for your case I should simply suggest
>>>
>>> Timing[Sum[i,{i,1,10^9}]]
>>> {0.047 Second,500000000500000000}
>>>
>>>
>>> Regards
>>> Dimitris
>>>
>>>
>>>
>>>
>>> =CF/=C7 Raj =DD=E3=F1=E1=F8=E5:
>>>> hi!
>>>>
>>>> Could somebody tell me what would be the fastest way to add up a
>>>> billion numbers(from 1 to 10^9 i.e the first billion numbers) in
>>>> Mathematica?
>>>>
>>>> Ofcourse the answer is n(n+1)/2, but is there any other way in
>>>> Mathematica other than the following one:
>>>>
>>>> Total@@Range[10^9]
>>>>
>>>> Thanks,
>>>>
>>>> Raj
>>>
>>>
>>
>> --Murray Eisenberg                     murray at math.umass.edu
>> Mathematics & Statistics Dept.
>> Lederle Graduate Research Tower      phone 413 549-1020 (H)
>> University of Massachusetts                413 545-2859 (W)
>> 710 North Pleasant Street            fax   413 545-1801
>> Amherst, MA 01003-9305
>>
> 

-- 
Murray Eisenberg                     murray at math.umass.edu
Mathematics & Statistics Dept.
Lederle Graduate Research Tower      phone 413 549-1020 (H)
University of Massachusetts                413 545-2859 (W)
710 North Pleasant Street            fax   413 545-1801
Amherst, MA 01003-9305

• References:
  • Re: fastest way to add up a billion numbers
    • From: "dimitris" <dimmechan@yahoo.com>
  • Re: Re: fastest way to add up a billion numbers
    • From: Murray Eisenberg <murray@math.umass.edu>