Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 1 down vote accepted

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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