MathGroup Archive 1997

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

Search the Archive

Re: Multiple sums.

  • To: mathgroup at smc.vnet.net
  • Subject: [mg5780] Re: Multiple sums.
  • From: Robert Villegas <villegas>
  • Date: Sat, 18 Jan 1997 14:58:34 -0500
  • Sender: owner-wri-mathgroup at wolfram.com

> so I wrote; (Well, i've copied it directly so the functions f and g are
> already there)
>
> sl[L_,n_]:=Module[{r=1-n/L,t,l},
>         t=(L r+1-Sum[l[p],{p,1,n-1}]);
>         For[ii=n-1,ii>0,ii--,
>                 t=Sum[(1+l[ii])*t,{l[ii],0,L r-Sum[l[k],{k,1,ii-1}]}];
>         ];
>         Return[t];
> ]
>
> Well, it is quite unreadeble but whats essential is that the ii in the range
> index won't evaluate, so the sums are made with (litterally) l[ii] and
> not with l[1],l[2] etc,


I'm not sure I know what this code is trying to do, but I think it's
taking an expression in n variables and summing out the nth, then the
(n-1)th, then the (n-2)th, and so on, through the 1st.  At each stage,
the summand, and potentially the lower and upper limits of summation
depend on the remaining variables (ones that haven't been summed out
yet).

I believe this will do your cumulative summation:

sl[L_, n_] :=
Module[{r = 1 - n/L, initialSum, upperLimit, index},
  upperLimit[u_] := L r - Sum[index[x], {x, 1, u - 1}];
  initialSum = L r + 1 - Sum[index[x], {x, 1, n - 1}];
  Fold[
    Sum[ (1 + index[#2]) #1, {index[#2], 0, upperLimit[#2]} ]&,
    initialSum,
    Range[n - 1, 1, -1]
  ]
]


Here is a test for a table of small values of L and n.  Your For-loop
implementation and the one above agree for all those values, though they
take an annoyingly long time to complete:


In[1]:= sl[L_,n_]:=Module[{r=1-n/L,t,l},
        t=(L r+1-Sum[l[p],{p,1,n-1}]);
        For[ii=n-1,ii>0,ii--,
                t=Sum[(1+l[ii])*t,{l[ii],0,L r-Sum[l[k],{k,1,ii-1}]}];
        ];
        Return[t];
]

In[2]:= Table[sl[L, n], {L, 6}, {n, 5}] //TableForm

Out[2]//TableForm= 1   0    0    0    0

                   2   1    0    0    0

                   3   4    1    0    0

                   4   10   6    1    0

                   5   20   21   8    1

                   6   35   56   36   10

In[3]:= sl[L_, n_] :=
Module[{r = 1 - n/L, initialSum, upperLimit, index},
  upperLimit[u_] := L r - Sum[index[x], {x, 1, u - 1}];
  initialSum = L r + 1 - Sum[index[x], {x, 1, n - 1}];
  Fold[
    Sum[ (1 + index[#2]) #1, {index[#2], 0, upperLimit[#2]} ]&,
    initialSum,
    Range[n - 1, 1, -1]
  ]
]

In[4]:= Table[sl[L, n], {L, 6}, {n, 5}] //TableForm

Out[4]//TableForm= 1   0    0    0    0

                   2   1    0    0    0

                   3   4    1    0    0

                   4   10   6    1    0

                   5   20   21   8    1

                   6   35   56   36   10


This can be made much faster.  In the previous implementations,
the summands become progressively more complicated, as the nesting
of Sum piles up.  At each stage, the new Sum tries to evaluation
symbolically, trying rules on the complicated summand (which contains
nested Sum's).  This costs a lot of time.  The following builds up
summations using a temporary head 'dummySum', which is replaced by
Sum only at the end, after all symbolics have been built up.  Then
the Sum's naturally evaluate from the inside out (because any
Mathematica expression evaluates its arguments first, which then
evaluate their arguments, and so on), so things proceed quickly.


In[5]:= sl[L_, n_] :=
Module[{r = 1 - n/L, initialSum, upperLimit, index, dummySum},
  upperLimit[u_] := L r - Sum[index[x], {x, 1, u - 1}];
  initialSum = L r + 1 - Sum[index[x], {x, 1, n - 1}];
  Fold[
    dummySum[ (1 + index[#2]) #1, {index[#2], 0, upperLimit[#2]} ]&,
    initialSum,
    Range[n - 1, 1, -1]
  ] /. dummySum -> Sum
]

In[6]:= Table[sl[L, n], {L, 6}, {n, 5}] //TableForm

Out[6]//TableForm= 1   0    0    0    0

                   2   1    0    0    0

                   3   4    1    0    0

                   4   10   6    1    0

                   5   20   21   8    1

                   6   35   56   36   10



Robby Villegas


  • Prev by Date: applying rule to one term??
  • Next by Date: special ColorFunction
  • Previous by thread: Multiple sums.
  • Next by thread: How to use inequalities with Solve?