Nested loop with dependent bounds trip count

Question

hello.

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

If you want to know how many times the inner loop:

for j in max(l,k):N

Would be executed, just compute: N - max(l, k) assuming open range, N + 1 - max(l, k) assuming closed range.

For example, if:

l = 2
k = 7
N = 10

then it will run on 7, 8, 9, 10 (closed range), so indeed 10 + 1 - 7 = 4 times.

Answer 2

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.

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));

Answer 3

Hi,

the answer is no, as long as the loop bounds can depend from the outer variables in an arbitrary fashionm as this would provide a general means for getting closed form formulations of integral series.

To see this, consider the following:

for x in 0:N
  for y in 0:f(x)
    t += 1

The trip count t(N) equals the sum t(N) = f(0)+f(1)+f(2)+f(3)+...+f(N-1).

So if you can get a closed form formulation for t(N) regardless of f(), you have found a very general method of producing closed forms, too general I would say, because what you have here correspond to an integral, and it's known that not all integrals admit closed form formulations.