Re: Re: Sum problem
- To: mathgroup at smc.vnet.net
- Subject: [mg65336] Re: [mg65322] Re: Sum problem
- From: "Virgilio, Vincent - SSD" <Vincent.Virgilio at itt.com>
- Date: Mon, 27 Mar 2006 06:56:03 -0500 (EST)
- Sender: owner-wri-mathgroup at wolfram.com
- Thread-index: AcZQzCM7+7M7hNO7QCCh5kJjPdMlvAAiMk8g
Hello, Does this "tail recursion" work (instead of "plain recursion") because doSumAux is never a subexpression of itself? Rather, stack is saved by changing the last function argument "acc"? It looks like an example in the documentation for "Trace" in the Mathematica Book. The example shows nested sublists in an expression chain. The example Traced a recursive function that was a subexpression of itself, typical of simple recursion. A nearby example showed a /flat/ expression chain for a Trace of a recursive function that was /not/ a subexpression of itself, like your tail recursion. Thanks, Vince Virgilio -----Original Message----- From: Maxim [mailto:m.r at inbox.ru] To: mathgroup at smc.vnet.net Subject: [mg65336] [mg65322] Re: Sum problem On Fri, 24 Mar 2006 06:05:55 +0000 (UTC), Majka Arkadiusz <Arkadiusz.Majka at telekomunikacja.pl> wrote: > Hi , > > I have a problem that drives me crazy. In order to sum a (long) list > of elements (random numbers), say tab > > tab = Table[Random[], {10^7}]; > > we use > > In[3]:= > Plus@@tab > > Out[3]= > 4.999014220610286`*^6 > > ....but to check Sum we get > > In[6]:= > Sum[tab[[i]],{i,1,Length[tab]}] > > Part specification K$30 is neither an > integer nor a list of integers. > > There is no problem for > > Sum[tab[[i]], {i, 1, 10^6}] > > ...and for > > Sum[tab[[i]], {i, 1, 5*10^6}] > > So Sum is ok. for number of elements of tab less than certain number > that is < Length[tab] > > I also tested recursion methods (doSum[k_]:=doSum[k]=doSum[k-1] ...... > Etc) > and got the same : fine but not for many elements (of course I set > $RecursiveLimit and $IterationLimit as Infinity) > > I understand that to sum a list of elements we use Plus, Total etc > but nevertheless I want understand what I explained above. > > Best, > > Arek > This issue was discussed on MathGroup some two years ago; basically the problem is that Sum works as described in chapter A.4.2 of The Mathematica Book (that is, as an "iteration function") only when the number of steps is not greater than 10^6; otherwise it calls SymbolicSum`SymbolicSum: In[1]:= SeedRandom[1]; {Random[], Random[]} Out[1]= {0.66869268, 0.83119987} In[2]:= SeedRandom[1]; Sum[ArcTan[k + Random[]], {k, 10^6 + 1}] Out[2]= Sum[ArcTan[0.83119987 + k], {k, 1000001}] This is evaluated as a symbolic sum; the summand is evaluated twice, first with k renamed to K$n and then in its original form. The recursive method should certainly work in principle; the problem is that it will crash the kernel if the recursion is nested too deeply: doSum[k_] := doSum[k - 1] + tab[[k]] doSum[0] := 0 Block[{$RecursionLimit = Infinity}, doSum[Length@ tab]] (*crashes the kernel*) This can be done if we rewrite doSum in a tail-recursive fashion: doSumAux[k_, acc_] := doSumAux[k - 1, acc + tab[[k]]] doSumAux[0, acc_] := acc doSum[k_] := doSumAux[k, 0] Block[{$IterationLimit = Infinity}, doSum[Length@ tab]] which will give exactly the same result as Plus @@ Reverse@ tab. Maxim Rytin m.r at inbox.ru ************************************ This e-mail and any files transmitted with it are proprietary and intended solely for the use of the individual or entity to whom they are addressed. If you have received this e-mail in error please notify the sender. Please note that any views or opinions presented in this e-mail are solely those of the author and do not necessarily represent those of ITT Industries, Inc. The recipient should check this e-mail and any attachments for the presence of viruses. ITT Industries accepts no liability for any damage caused by any virus transmitted by this e-mail. ************************************