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$?

| cite | improve this question | | | | |
  • $\begingroup$ 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.) $\endgroup$ – Ted Mar 27 '12 at 7:43
  • $\begingroup$ 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. $\endgroup$ – badnews Mar 27 '12 at 8:55

The usual way to write this as a multiple sum would be

$$\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$.

| cite | improve this answer | | | | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.