Nested loop with dependent bounds trip count

Question

just out of curiosity I tried to do the following, which turned out to be not so obvious to me; Suppose I have nested loops with runtime bounds, for example:

 t = 0 //  trip count
 for l in 0:N
   for k in 0:N
     for j in max(l,k):N
        for i in k:j+1
           t += 1

 t is loop trip count

is there a general algorithm/way (better than N^4 obviously) to calculate loop trip count?

if not, I would be curious to know how you would approach just this particular loop. the above loop is symmetric (it's loops over symmetric rank-4 tensor), and I am also interested in methods to detect loop symmetry.

I am working on the assumption that the iteration bounds depend only on constant or previous loop variables. link/journal article, If you know of one, would be great.

Answer 1

I believe the inner loop will run

t = 1/8 * (N^4 + 6 * N^3 + 7 * N^2 + 2 * N)

times.

I did not really solve the problem directly, I fitted a 4-th order polynomial expression to exactly calculated t for N from 1 to 50 hoping that I'll get exact fit.

To calculate exact t I used

sum(sum(sum(sum(1,i,k,j+1),j,max(l,k),N),k,1,N),l,1,N)

which should be the equivalent of actually running your loops.

data fit, log scale http://img714.imageshack.us/img714/2313/plot3.png

The fit for N from 1 to 50 matches exactly and calculating it for N=100 gives 13258775 using both methods.

EDIT: The exercise was done using open source algebra system maxima, here's the actual source (output discarded):

nr(n):=sum(sum(sum(sum(1,i,k,j+1),j,max(l,k),n),k,1,n),l,1,n);
M : genmatrix( lambda([i,j],if j=1 then i else nr(i)), 50, 2 );
coefs : lsquares_estimates(M, [x,y], y = A*x^4+B*x^3+C*x^2+D*x+E, [A,B,C,D,E]);
sol(x):=ev(A*x^4+B*x^3+C*x^2+D*x+E, coefs);
sol(N);
S : genmatrix( lambda([i,j], if j=1 then i else sol(i)), 50, 2);
M-S;
plot2d([[discrete,makelist([M[N][1],M[N][2]],N,1,50)], sol(N)], [N, 1, 60], [style, points, lines], [color, red, blue], [legend, "simulation", sol(N)], [logy]);
compare(nr(100),sol(100));