********** 3d1d *********** > cat impact/expl_3d1d.in for( i=1 ; i<=p+4 ; i++ ) for( j=1; j<=5 ; j++ ) for( k=1 ; k<=2*p/3 ; k++ ) A[3*i+4*j+6*k+1] = 42; -- Which elements of array A are accessed by this loop nest? How many are there ? > ******** 3d1d: ISCC ********* > cat impact/isc_3d1d.in card ([p] -> { [x] : exists i, j, k : 1 <= i <= p + 4 and 1 <=j <= 5 and 3 <= 3k <= 2p and x = 3i+4j+6k+1}); > time BARVI/bin/iscc { (10 + 7 * p) : exists (e0 = [(-1 + p)/3]: 3e0 = -1 + p and p >= 5); ((14 + 347/40 * p - 21/32 * p^2 - 11/64 * p^3 - 15/128 * p^4 + 21/1280 * p^5) + (-201/40 + 77/16 * p + 93/64 * p^2 + 19/16 * p^3 - 57/256 * p^4) * [(p)/3] + (-273/32 - 261/64 * p - 279/64 * p^2 + 153/128 * p^3) * [(p)/3]^2 + (243/64 + 27/4 * p - 405/128 * p^2) * [(p)/3]^3 + (-459/128 + 1053/256 * p) * [(p)/3]^4 - 2673/1280 * [(p)/3]^5) : exists (e0 = [(-1 + p)/3]: p >= 5 and 3e0 <= -2 + p and 3e0 >= -3 + p); 26 : p = 2; 35 : p = 3; 38 : p = 4 } real 0m1.410s user 0m1.315s sys 0m0.018s > ****** 3d1d: Barvinok ******* > cat impact/be_3d1d.in # x i j k p c 7 7 0 -1 3 4 6 0 1 1 0 1 0 0 0 -1 1 0 -1 0 0 1 4 1 0 0 1 0 0 -1 1 0 0 -1 0 0 5 1 0 0 0 1 0 -1 1 0 0 0 -3 2 0 E 3 P 1 p > time BARVI/bin/barvinok_enumerate_e = 0 35 p -4 >= 0 1 >= 0 [ ( 1 * {( 1/3 * p + 2/3 ) } + 0 ) = 0 ] * ( 7 * p + 10 ) + [ ( 1 * {( 1/3 * p + 2/3 ) } + 0 ) != 0 ] * ( ( -3 * {( 1/3 * p + 0 ) }^2 + 3 * {( 1/3 * p + 0 ) } + ( 295084/19153 * {( 1/3 * p + 1/3 ) }^3 + -352543/38306 * {( 1/3 * p + 1/3 ) }^2 + 1156969/344754 * {( 1/3 * p + 1/3 ) } + 19/3 ) ) * p + ( 21/8 * {( 1/3 * p + 0 ) }^4 + ( 1 * {( 1/3 * p + 1/3 ) } + -77/12 ) * {( 1/3 * p + 0 ) }^3 + ( -12 * {( 1/3 * p + 1/3 ) }^2 + 3/2 * {( 1/3 * p + 1/3 ) } + -115/24 ) * {( 1/3 * p + 0 ) }^2 + ( -3 * {( 1/3 * p + 1/3 ) }^3 + 23 * {( 1/3 * p + 1/3 ) }^2 + -29/6 * {( 1/3 * p + 1/3 ) } + 29/4 ) * {( 1/3 * p + 0 ) } + ( 559651/153224 * {( 1/3 * p + 1/3 ) }^4 + 12285101/229836 * {( 1/3 * p + 1/3 ) }^3 + -21126637/459672 * {( 1/3 * p + 1/3 ) }^2 + 39733657/2068524 * {( 1/3 * p + 1/3 ) } + 865/81 ) ) ) p -2 = 0 1 >= 0 26 real 0m0.155s user 0m0.143s sys 0m0.006s > ***** 3d1d: ZPolyTrans ****** > cat impact/zpt_3d1d.in 1 # i j k x p c 7 7 0 3 4 6 -1 0 1 1 1 0 0 0 0 -1 1 -1 0 0 0 1 4 1 0 1 0 0 0 -1 1 0 -1 0 0 0 5 1 0 0 1 0 0 -1 1 0 0 -3 0 2 0 3 0 3 p > time ZPolyTrans-0.04/enumerate_image = 0 1 >= 0 [ ( 1 * {( 1/3 * p + 0 ) } + 0 ) = 0 ] * ( 7 * p + 14 ) + [ ( 1 * {( 1/3 * p + 0 ) } + 0 ) != 0 ] * [ ( 1 * {( 1/3 * p + 1/3 ) } + 0 ) = 0 ] * ( 7 * p + 12 ) + [ ( 1 * {( 1/3 * p + 1/3 ) } + 0 ) != 0 ] * [ ( 1 * {( 1/3 * p + 2/3 ) } + 0 ) = 0 ] * ( 7 * p + 10 ) + [ ( 1 * {( 1/3 * p + 2/3 ) } + 0 ) != 0 ] * ( 7 * p + 7 ) real 0m0.023s user 0m0.018s sys 0m0.004s > ********** 3d1d-p0 *********** > cat impact/expl_3d1d-p0.in /* only replaced the upper bound i<=p+4 by i<=p */ for( i=1 ; i<=p ; i++ ) for( j=1; j<=5 ; j++ ) for( k=1 ; k<=2*p/3 ; k++ ) A[3*i+4*j+6*k+1] = 42; -- Which elements of array A are accessed by this loop nest? How many are there ? > ******** 3d1d-p0: ISCC ********* > cat impact/isc_3d1d-p0.in card ([p] -> { [x] : exists i, j, k : 1 <= i <= p and 1 <=j <= 5 and 3 <= 3k <= 2p and x = 3i+4j+6k+1}); > time BARVI/bin/iscc { (-2 + 7 * p) : exists (e0 = [(-1 + p)/3]: 3e0 = -1 + p and p >= 7); 35 : p = 5; ((2 + 391984391/48608040 * p - 4801969/38886432 * p^2 + 4385309/77772864 * p^3 - 68565827/155545728 * p^4 + 144240133/1555457280 * p^5) + (-51728111/16202680 + 51952009/19443216 * p - 26225699/77772864 * p^2 + 10720279/2430402 * p^3 - 384362617/311091456 * p^4) * [(p)/3] + (-89498111/12962144 + 12983617/25924288 * p - 412054341/25924288 * p^2 + 336004835/51848576 * p^3) * [(p)/3]^2 + (258465/25924288 + 154767645/6481072 * p - 862941159/51848576 * p^2) * [(p)/3]^3 + (-621048717/51848576 + 165661803/7976704 * p) * [(p)/3]^4 - 5155150203/518485760 * [(p)/3]^5) : exists (e0 = [(-1 + p)/3]: p >= 6 and 3e0 <= -2 + p and 3e0 >= -3 + p); 10 : p = 2; 23 : p = 3; 26 : p = 4 } real 0m4.597s user 0m4.531s sys 0m0.043s > ****** 3d1d-p0: Barvinok ******* > cat impact/be_3d1d-p0.in # x i j k p c 7 7 0 -1 3 4 6 0 1 1 0 1 0 0 0 -1 1 0 -1 0 0 1 0 1 0 0 1 0 0 -1 1 0 0 -1 0 0 5 1 0 0 0 1 0 -1 1 0 0 0 -3 2 0 E 3 P 1 p > time BARVI/bin/barvinok_enumerate_e = 0 23 p -7 >= 0 1 >= 0 [ ( 1 * {( 1/3 * p + 2/3 ) } + 0 ) = 0 ] * ( 7 * p + -2 ) + [ ( 1 * {( 1/3 * p + 2/3 ) } + 0 ) != 0 ] * ( ( -3 * {( 1/3 * p + 0 ) }^2 + 3 * {( 1/3 * p + 0 ) } + ( 13193331/862237 * {( 1/3 * p + 1/3 ) }^3 + -7890021/862237 * {( 1/3 * p + 1/3 ) }^2 + 8665666/2586711 * {( 1/3 * p + 1/3 ) } + 19/3 ) ) * p + ( 21/8 * {( 1/3 * p + 0 ) }^4 + ( 1 * {( 1/3 * p + 1/3 ) } + -23/4 ) * {( 1/3 * p + 0 ) }^3 + ( -12 * {( 1/3 * p + 1/3 ) }^2 + 5/2 * {( 1/3 * p + 1/3 ) } + -37/8 ) * {( 1/3 * p + 0 ) }^2 + ( -3 * {( 1/3 * p + 1/3 ) }^3 + 47/2 * {( 1/3 * p + 1/3 ) }^2 + -14/3 * {( 1/3 * p + 1/3 ) } + 251/36 ) * {( 1/3 * p + 0 ) } + ( -10819417/3448948 * {( 1/3 * p + 1/3 ) }^4 + 59052279/1724474 * {( 1/3 * p + 1/3 ) }^3 + -181125337/10346844 * {( 1/3 * p + 1/3 ) }^2 + 575895701/46560798 * {( 1/3 * p + 1/3 ) } + -38/27 ) ) ) p -4 = 0 1 >= 0 26 p -5 = 0 1 >= 0 35 p -6 = 0 1 >= 0 44 p -2 = 0 1 >= 0 10 real 0m0.585s user 0m0.568s sys 0m0.014s > ***** 3d1d-p0: ZPolyTrans ****** > cat impact/zpt_3d1d-p0.in 1 # i j k x p c 7 7 0 3 4 6 -1 0 1 1 1 0 0 0 0 -1 1 -1 0 0 0 1 0 1 0 1 0 0 0 -1 1 0 -1 0 0 0 5 1 0 0 1 0 0 -1 1 0 0 -3 0 2 0 3 0 3 p > time ZPolyTrans-0.04/enumerate_image = 0 10 p -3 >= 0 1 >= 0 [ ( 1 * {( 1/3 * p + 0 ) } + 0 ) = 0 ] * ( 7 * p + 2 ) + [ ( 1 * {( 1/3 * p + 0 ) } + 0 ) != 0 ] * [ ( 1 * {( 1/3 * p + 1/3 ) } + 0 ) = 0 ] * ( 7 * p + 0 ) + [ ( 1 * {( 1/3 * p + 1/3 ) } + 0 ) != 0 ] * [ ( 1 * {( 1/3 * p + 2/3 ) } + 0 ) = 0 ] * ( 7 * p + -2 ) + [ ( 1 * {( 1/3 * p + 2/3 ) } + 0 ) != 0 ] * ( 7 * p + -5 ) real 0m0.037s user 0m0.031s sys 0m0.004s > ********** iooss *********** > cat impact/expl_iooss.in // ... for( i=0 ; i<=n ; i++ ) for( j=i+1 ; j<=n ; j++ ) B[2*i+3*j] = fct1(i,j); for( k=1 ; k<=n ; k++ ) for( l=1 ; l ******** iooss: ISCC ********* > cat impact/isc_iooss.in card ([n] -> { [x] : exists i, j, k, l : 1 <= i <= n and i + 1 <= j <= n and 1 <= k <= n and 1 <= l <= k - 1 and x = 2i + 3j and x = k + 2l}); > time BARVI/bin/iscc { (((-14 + 8/3 * n + n^2 - 2/3 * n^3) + (1/2 - 7/2 * n + 3 * n^2) * [(n)/3] + (3 - 9/2 * n) * [(n)/3]^2 + 5/2 * [(n)/3]^3) + ((1/2 - 5/2 * n + 3 * n^2) + (9/2 - 9 * n) * [(n)/3] + 6 * [(n)/3]^2) * [(1 + n)/3] + ((3/2 - 9/2 * n) + 15/2 * [(n)/3]) * [(1 + n)/3]^2 + 2 * [(1 + n)/3]^3) : n >= 18; 37 : n = 17; ((((((-8 - 8/3 * n - 1/3 * n^3) + 1/3 * [(n)/3] + 1/2 * [(n)/3]^2 + 1/6 * [(n)/3]^3) + (-1/3 - [(n)/3] - 1/2 * [(n)/3]^2) * [(1 + n)/3] + (1/2 + 1/2 * [(n)/3]) * [(1 + n)/3]^2 - 1/6 * [(1 + n)/3]^3) + (32/3 - 6 * n + n^2) * [(2n)/5] + (5 - 2 * n) * [(2n)/5]^2 + 4/3 * [(2n)/5]^3) + ((2/3 + 6 * n + n^2) + [(2n)/5]) * [(1 + 2n)/5] + (-6 - 2 * n) * [(1 + 2n)/5]^2 + 4/3 * [(1 + 2n)/5]^3) + (((2/3 + 5 * n + n^2) + [(2n)/5]) + (-11 - 4 * n) * [(1 + 2n)/5] + 4 * [(1 + 2n)/5]^2) * [(2 + n)/5] + ((-4 - 2 * n) + 4 * [(1 + 2n)/5]) * [(2 + n)/5]^2 + 4/3 * [(2 + n)/5]^3) : n >= 8 and n <= 16; 7 : n = 7; ((13 - 7 * n + n^2) + (-10 + 9/2 * n - 1/2 * n^2) * [(4 + n)/5]) : n >= 5 and n <= 6; 1 : n = 4 } real 0m0.087s user 0m0.080s sys 0m0.004s > ****** iooss: Barvinok ******* > cat impact/be_iooss.in 10 8 # x i j k l N cte 0 -1 2 3 0 0 0 0 # x = 2i+3j 0 -1 0 0 1 2 0 0 # x = k+2l 1 0 1 0 0 0 0 -1 # i >= 1 1 0 -1 0 0 0 1 0 # i <= N 1 0 -1 1 0 0 0 -1 # j >= i+1 1 0 0 -1 0 0 1 0 # j <= N 1 0 0 0 1 0 0 -1 # k >= 1 1 0 0 0 -1 0 1 0 # k <= N 1 0 0 0 0 1 0 -1 # l >= 1 1 0 0 0 1 -1 0 -1 # l <= k-1 E 4 P 1 n > time BARVI/bin/barvinok_enumerate_e = 0 1 >= 0 ( 3 * n + -14 ) n -10 = 0 1 >= 0 16 n -6 >= 0 - n + 8 >= 0 ( ( -8/25 * {( 1/5 * n + 2/5 ) } + ( -9/50 * {( 1/5 * n + 3/5 ) } + ( 1/2 * {( 1/5 * n + 4/5 ) } + 12/125 ) ) ) * n^2 + ( ( -2/5 * {( 1/5 * n + 4/5 ) } + ( 4/5 * {( 2/5 * n + 0 ) } + 98/25 ) ) * {( 1/5 * n + 2/5 ) } + ( ( 2/5 * {( 1/5 * n + 4/5 ) } + ( -4/5 * {( 2/5 * n + 0 ) } + 109/50 ) ) * {( 1/5 * n + 3/5 ) } + ( -209/50 * {( 1/5 * n + 4/5 ) } + ( -16/25 * {( 2/5 * n + 0 ) } + 13/125 ) ) ) ) * n + ( ( ( 1 * {( 2/5 * n + 0 ) } + 2 ) * {( 1/5 * n + 4/5 ) } + ( -29/5 * {( 2/5 * n + 0 ) } + -58/5 ) ) * {( 1/5 * n + 2/5 ) } + ( ( ( -1 * {( 2/5 * n + 0 ) } + -2 ) * {( 1/5 * n + 4/5 ) } + ( 34/5 * {( 2/5 * n + 0 ) } + -37/5 ) ) * {( 1/5 * n + 3/5 ) } + ( ( -4/5 * {( 2/5 * n + 0 ) } + 42/5 ) * {( 1/5 * n + 4/5 ) } + ( 1 * {( 2/5 * n + 0 ) }^2 + 101/25 * {( 2/5 * n + 0 ) } + 17/25 ) ) ) ) ) n -5 = 0 1 >= 0 3 n -9 = 0 1 >= 0 13 n -4 = 0 1 >= 0 1 real 0m0.041s user 0m0.035s sys 0m0.004s > ***** iooss: ZPolyTrans ****** > cat impact/zpt_iooss.in 1 10 8 # i j k l x N cte 0 2 3 0 0 -1 0 0 # x = 2i+3j 0 0 0 1 2 -1 0 0 # x = k+2l 1 1 0 0 0 0 0 -1 # i >= 1 1 -1 0 0 0 0 1 0 # i <= N 1 -1 1 0 0 0 0 -1 # j >= i+1 1 0 -1 0 0 0 1 0 # j <= N 1 0 0 1 0 0 0 -1 # k >= 1 1 0 0 -1 0 0 1 0 # k <= N 1 0 0 0 1 0 0 -1 # l >= 1 1 0 0 1 -1 0 0 -1 # l <= k-1 4 0 3 n > time ZPolyTrans-0.04/enumerate_image = 0 5 n -5 = 0 1 >= 0 3 n -4 = 0 1 >= 0 1 n -7 >= 0 1 >= 0 ( 3 * n + -14 ) real 0m0.008s user 0m0.004s sys 0m0.003s > ********** un2poly *********** > cat impact/expl_un2poly.in for( i=1 ; i<=n ; i++ ) for( j=1 ; j<=n ; j++ ) if( ji ) A[2*i+3*j] = 42; -- What elements of array A are set? > ******** un2poly: ISCC ********* > cat impact/isc_un2poly.in card ([n] -> { [x] : exists i,j : 1 <= i <= n and i + 1 <= j <= n and x = 2i+3j} + [n] -> { [x] : exists k,l : 1 <= k <= n and 1 <= l <= k-1 and x = k + 2l }); > time BARVI/bin/iscc { ((((((-6 + 5/3 * n + 1/3 * n^3) + (4/3 + 3/2 * n - 3 * n^2) * [(n)/3] + (-1 + 9/2 * n) * [(n)/3]^2 - 7/3 * [(n)/3]^3) + ((-1/3 + 7/2 * n - 3 * n^2) + (-7/2 + 9 * n) * [(n)/3] - 13/2 * [(n)/3]^2) * [(1 + n)/3] + ((-7/2 + 9/2 * n) - 7 * [(n)/3]) * [(1 + n)/3]^2 - 13/6 * [(1 + n)/3]^3) + ((11/3 + n + n^2) + [(n)/3]) * [(1 + n)/5] + (-2 - 2 * n) * [(1 + n)/5]^2 + 4/3 * [(1 + n)/5]^3) + ((16/3 - 4 * n + 2 * n^2) + (-2 - 4 * n) * [(1 + n)/5] + 4 * [(1 + n)/5]^2) * [(1 + 2n)/5] + ((4 - 4 * n) + 4 * [(1 + n)/5]) * [(1 + 2n)/5]^2 + 8/3 * [(1 + 2n)/5]^3) + (n - [(1 + n)/5]) * [(3 + 2n)/5] - [(3 + 2n)/5]^2) : n <= 13 and n >= 7; 22 : n = 6; 63 : n = 14; (-7 + 5 * n) : n >= 15; 6 : n = 3; (-129 + 79 * n - 15 * n^2 + n^3) : n >= 4 and n <= 5; 2 : n = 2 } real 0m0.095s user 0m0.089s sys 0m0.005s > ****** un2poly: Barvinok ******* > cat impact/be_un2poly.in 0 2 E 0 P 0 n > time BARVI/bin/barvinok_enumerate_e = 0 1 real 0m0.005s user 0m0.001s sys 0m0.002s > ***** un2poly: ZPolyTrans ****** > cat impact/zpt_un2poly.in 2 5 6 0 2 3 -1 0 0 1 1 0 0 0 -1 1 -1 0 0 1 0 1 -1 1 0 0 -1 1 0 -1 0 1 0 2 5 6 0 1 2 -1 0 0 1 1 0 0 0 -1 1 -1 0 0 1 0 1 0 1 0 0 -1 1 1 -1 0 0 -1 2 0 3 n > time ZPolyTrans-0.04/enumerate_image = 0 16 n -6 = 0 1 >= 0 22 n -4 = 0 1 >= 0 11 n -3 = 0 1 >= 0 6 n -2 = 0 1 >= 0 2 n -7 >= 0 1 >= 0 ( 5 * n + -7 ) real 0m0.016s user 0m0.012s sys 0m0.003s >