Re: Re: Re: Re: fastest way to
- To: mathgroup at smc.vnet.net
- Subject: [mg74015] Re: [mg73998] Re: [mg73973] Re: [mg73907] Re: fastest way to
- From: "Christoph Lhotka" <lhotka at astro.univie.ac.at>
- Date: Tue, 6 Mar 2007 05:27:41 -0500 (EST)
Hello all together!
Just some comments, to this beautifull discussion...
1)
Sum[i,{i,1,10^1000}] returns the result within a fraction of a second, because
it uses indeed Gauss´ formula, if it´s faster then summing up numerically. It
would be interesting, where the threshold lies (of course not at n=10^6) (the
reason for that is the internal automatic algorithm selection)!
2)
This question in computer theory is not a time but a memory issue! How much
memory do you need to store 10^9 integer numbers on your computer system?
Please try in Fortran or C! This is the reason why Total[Range[10^9]] will not
work on most computer systems, at least not with those, which are unable to
store the intermediate result of Range[10^9] in their memory. But to my
opinion its the fastest way for the general question of summing up lists
(which can be stored in memory).
3) a working solution for really limiting cases...
I would suggest the following construct (of course it is slower, but it will
work also for the 10^1000 case and can be easily generalized to other
problems). Define a stream, say
In[..]:=stream:=k++
Then the function
In[..]:=Timing[k = 1; Block[{res = 0}, Do[res = res + stream, {#}]; res]
&[10^9]]
This will need (on my computer) too long. But do you really think this is
slow? If you need to generalize it to some other problem, you could use the
Stream functions of Mathematica (OpenStream,Read,...) and sum up any data,
limited by the size of where it is stored. The benefit of such a construct is
the fact, that it will work with O(n) complexity (just limited by the access
time of the file on your hard-disk), because it only needs to store 2 integer
numbers in memory during calculation.. At this point I think Fortran may be
faster...
4) an improoved (Mathematica) version
Of course one can combine the power of the function Total with 3) according to
the question, how much memory the computer has:
In[..]:=
Timing[With[{n = 10^9, m = 1000000}, Total[Total[Range @@ #] & /@ Inner[List,
Range[1, n, m], Range[m, n, m], List]]]]
will take on my computer 300 seconds.
In the end I think Mathematica is the winner, because of two reasons: Version
4) and the the crucial thing, that the internal algorithm selection (in e.g.
Sum[i,{i,1,10^1000000) of Mathematica really seems to work and give good and
fast results...
With kind regards,
Christoph
On Mon, 5 Mar 2007 04:50:42 -0500 (EST)
Murray Eisenberg <murray at math.umass.edu> wrote:
> 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
>
-- Mag. Christoph Lhotka --
University of Vienna / Department of Astronomy
Tuerkenschanzstrasse 17, A-1180 Vienna, Austria
fon. +43 (1) 4277 51841
mail. lhotka at astro.univie.ac.at