# Represent loop nests as multiple summations?

This may be trivial but I would appreciate if someone could point me in the right direction here.. I am trying to express the number of instances in a loop nest in a general form. As a mathematical expression I would think this would be a multiple summation.

Example, loop nest:

for k in f_1(N):
for j in f_2(k):
for i in f_3(k,j):
do something


Where $f_n(x)$ is a function that generates a set of indices for loop $n$ given input $x$. I would say that each loop nest function can take as input any of the outer indices (or not -- it could be completely static/independent).. not quite sure if I've expressed that right.

From that I have: $\sum_{k}^{f_{1}(N)}\sum_{j}^{f_{2}(k)}|f_{3}(k,j)|$

Assuming this is correct, which it may not be!, how would one make this more generic to handle any number of loops say in the form with loop $l=1,...,N$?

• Something is wrong with your loop. You can't have "for k in f_k(N)", where the loop variable k also occurs in the defining expression f_k(N). (Why? That would be like writing "for i = 1 to i" in a more standard loop situation.) – Ted Mar 27 '12 at 7:43
• Ted I guess you are correct, I think it was bad labeling. I have edited the labels to make it clear that the loop variable isn't a function of the loop index function. – badnews Mar 27 '12 at 8:55

$$\sum_{k\in f_1(N)}\sum_{j\in f_2(k)}|f_3(k,j)|\;.$$
I don't think there's any generalization beyond that, since we don't know anything about the $f_i$.