MathGroup Archive 2006

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

Search the Archive

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.
************************************


  • Prev by Date: Re: Exporting plots with the kernel
  • Next by Date: Re: Re: infinite product
  • Previous by thread: Re: Sum problem
  • Next by thread: Re: Re: Sum problem