Nested loop with dependent travel segment

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 / method (better than N ^ 4, obviously) to calculate the number of cycle disconnections?

If not, I would be interested to know how you approach this particular cycle. the above loop is symmetric (it loops over the symmetric rank-4 tensor), and I'm also interested in methods for detecting loop symmetry.

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

Answer 1

,

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

.

, 4- t N 1 50, , .

t,

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

.

, http://img714.imageshack.us/img714/2313/plot3.png

N 1 50 N = 100 13258775 .

EDIT: maxima, ( ):

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 2

, :

for j in max(l,k):N

, : N - max(l, k), , N + 1 - max(l, k), .

, :

l = 2
k = 7
N = 10

7, 8, 9, 10 ( ), 10 + 1 - 7 = 4 .

Answer 3

, , .

, :

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

t (N) t (N) = f (0) + f (1) + f (2) + f (3) +... + f (N-1).

So, if you can get a closed form for t (N), regardless of f (), you have found a very general method for creating closed forms that are too general, I would say because the fact that you are here corresponds to the integral, and It is known that not all integrals admit closed formulations.