具有相关边界行程计数的嵌套循环

Question

出于好奇，我尝试执行以下操作，结果对我来说并不那么明显； 假设我有运行时边界的嵌套循环，例如：

 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

是否有一个通用算法/方式（显然比 N^4 更好）来计算循环行程计数？

如果没有，我很想知道你将如何处理这个特定的循环。上面的循环是对称的（它是对称 4 阶张量上的循环），我也对检测循环对称性的方法感兴趣。

我正在假设迭代边界仅取决于常量或先前的循环变量。链接/期刊文章，如果您知道一篇，那就太好了。

Answer 1

我相信内循环会运行

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

多次。

我并没有真正直接解决这个问题，我拟合了一个 4 阶多项式表达式来精确计算 N 从 1 到 50 的 t，希望我能得到精确的拟合。

为了计算精确的 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。

编辑：
该练习是使用开源代数系统 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）。

因此，如果无论 f() 如何，您都可以获得 t(N) 的闭合形式公式，那么您就找到了一种生成闭合形式的非常通用的方法，我会说太笼统了，因为这里对应于积分，并且 < em>众所周知，并非所有积分都接受封闭形式公式。