counting iterations of a loop by evaluating a sum

[Patrick]

Hi,

I'd like to count the iterations of a loop nest by evaluating a sum.
Consider the following loop nest:

for (k = 0; k < N; k++)
for (i = k+1; i < N; i++)
for (j = k+1; j <= i; j++)
...

I'd like to count the total number of iterations of that loop nest.
I've used mathematica a bit, and you could solve this problem with
something like this:

Sum[1, {k, 0, N}, {i, k+1, N}, {j, k+1, i-1}]

The result should be in terms of N. For this loop nest the closed
form is:

1 / 6 * (1 + N) * (N^2 - N)

I've been trying to figure out how to do this sort of problem in Sage,
but I have been unsuccessful. Any help would be greatly appreciated.

Thanks,
Patrick

[Burcin Erocal]

Hi,

Unfortunately Sage doesn't have native code to find closed forms for
sums at the moment. You will have to use maxima directly to solve this problem.

I have an implementation of various (mostly theoretical) parts of
symbolic summation algorithms, but it has no user interface. I expect
to push this code in Sage at the end of May, after I sort the user
interface out and add some other basic dependencies in Sage.

Cheers,
Burcin

[Jason Grout]

Burcin Erocal wrote:
> Hi,
>
> On Thu, 26 Mar 2009 09:31:09 -0700 (PDT)
> Patrick <Patrick....@gmail.com> wrote:
>
>> I'd like to count the iterations of a loop nest by evaluating a sum.
>> Consider the following loop nest:
>>
>> for (k = 0; k < N; k++)
>> for (i = k+1; i < N; i++)
>> for (j = k+1; j <= i; j++)
>> ...
>>
>> I'd like to count the total number of iterations of that loop nest.
>> I've used mathematica a bit, and you could solve this problem with
>> something like this:
>>
>> Sum[1, {k, 0, N}, {i, k+1, N}, {j, k+1, i-1}]
>>
>> The result should be in terms of N. For this loop nest the closed
>> form is:
>>
>> 1 / 6 * (1 + N) * (N^2 - N)
>>
>> I've been trying to figure out how to do this sort of problem in Sage,
>> but I have been unsuccessful. Any help would be greatly appreciated.
>
> Unfortunately Sage doesn't have native code to find closed forms for
> sums at the moment. You will have to use maxima directly to solve this problem.
>

You can use maxima as illustrated in William's message here:

http://groups.google.com/group/sage-support/browse_thread/thread/45849ec99438bbac/008b4a34dbf72cf6

sage: a=maxima('sum(sum(sum(1,j,k+1,i-1), i, k+1, N), k, 0, N),
simpsum').sage()
sage: a
(2*N^3 + 3*N^2 + N)/12 - (N^3 + N^2)/2 + (N^2 + N)/4 + N^2*(N + 1)/2 -
N*(N + 1)/2
sage: a.simplify_full()
(N^3 - N)/6

Jason

[Patrick]

That's perfect. Thanks!

On Mar 26, 5:41 pm, Jason Grout <jason-s...@creativetrax.com> wrote:
> Burcin Erocal wrote:
> > Hi,
>
> > On Thu, 26 Mar 2009 09:31:09 -0700 (PDT)
> > Patrick <Patrick.J.Cla...@gmail.com> wrote:
>
> >> I'd like to count the iterations of a loop nest by evaluating a sum.
> >> Consider the following loop nest:
>
> >>    for (k = 0; k < N; k++)
> >>       for (i = k+1; i < N; i++)
> >>           for (j = k+1; j <= i; j++)
> >>              ...
>
> >> I'd like to count the total number of iterations of that loop nest.
> >> I've used mathematica a bit, and you could solve this problem with
> >> something like this:
>
> >>     Sum[1, {k, 0, N}, {i, k+1, N}, {j, k+1, i-1}]
>
> >> The result should be in terms of N.  For this loop nest the closed
> >> form is:
>
> >>    1 / 6 * (1 + N) * (N^2 - N)
>
> >> I've been trying to figure out how to do this sort of problem in Sage,
> >> but I have been unsuccessful.  Any help would be greatly appreciated.
>
> > Unfortunately Sage doesn't have native code to find closed forms for
> > sums at the moment. You will have to use maxima directly to solve this problem.
>
> You can use maxima as illustrated in William's message here:
>

> http://groups.google.com/group/sage-support/browse_thread/thread/4584...