#!/usr/bin/env python3 """tailmem5.py -- exact enumeration of the closed trails of length at most 20 (the first row of Table tab:tail). Hexagon accepts only scripts and data files of a few types as ancillary files, so the C program tailmem5.c is stored in this file verbatim, as the string C_SOURCE below. Its sha256 digest is 4946f4c78703e82e76f7a3bd01d56c3853508dcabc0855b9a42500aba282380a This script writes tailmem5.c to a directory, compiles it with gcc -O2 -frounding-math -ffp-contract=off tailmem5.c -lm -o tailmem5 runs the program with the arguments given, and passes its standard output and standard error through unchanged. It computes, for one pair type X and one first direction d0, the weighted sums m(T^{X,d0}_n) of the closed trails of length n <= L by depth-first search, sorting per-trail ordering keys in binary64 and evaluating each result with upward rounding (lines "E n value" of the output and their sum, the line "# EXACT"). The paper uses only these lines. With the recorded arguments the program also runs a walk on a periodic quotient of the lattice for 22 <= n <= 109 (lines "D n value" and "# TAIL"), which needs 3.1 GB of memory; Table tab:tail does not use these lines. Usage: python3 tailmem5.py --print-source print tailmem5.c to standard output and exit python3 tailmem5.py --write-source DIR write DIR/tailmem5.c and exit python3 tailmem5.py [--workdir DIR] [--cc CC] [--compile-only] [--verbose] [--] X m L K T AT NEX cs ct a b hB hC D0 --workdir DIR build in DIR and keep tailmem5.c and the binary there (default: a temporary directory that is removed at the end) --cc CC the C compiler (default gcc; the flags above are always used) --compile-only compile and exit --verbose print the compiler command and the compiler's messages to standard error The compiler and floating-point environment must honor directed rounding. Keep -frounding-math and -ffp-contract=off when compiling with GCC. Example (the recorded run, see jobs.yaml): python3 tailmem5.py B 10 20 28 109 109 22 0.961 0.935 0.16666666666666667 0.36 1 1.25 1 > short_trails_B_1.log 2>&1 """ import hashlib, os, shutil, subprocess, sys, tempfile NAME = 'tailmem5' CFLAGS = ['-O2', '-frounding-math', '-ffp-contract=off'] LIBS = ['-lm'] SHA256 = '4946f4c78703e82e76f7a3bd01d56c3853508dcabc0855b9a42500aba282380a' C_SOURCE = r'''/* The depth-first search enumerates closed trails of length at most L. It uses the per-trail order from Appendix C, ascending in (x_i - 1)/(x_i kappa_h(i)), to evaluate each h-weighted contribution. The optional argument D0 selects the first direction of a trail, with -1 selecting all four classes. The dynamic program uses a walk with memory m on the quotient of Z^2 by <(K,K),(K,-K)>, which has 2K^2 sites and shortest nonzero period of L1 length 2K. Through step AT, it excludes c and stops at v. It treats u as already visited and, for a specified first direction, also treats u+D0 as visited and the bond (u, u+D0) as used. A passage through one of these sites is a revisit, and another visit detected by the history excludes the passage. This walk uses the straight-before-turn enumeration of Appendix C with pair weights h = (h_B, h_C). Per trail w and first-visit passage j the term is 3^{-n}(3/5)^{rev} kappa_h(j) times j straight: x_s^{#straight FV passages i <= j} j turn: x_s^{#straight FV passages in w} * x_t^{#turn FV passages i <= j} Four phases: A: before a turn response, weights (straight x_s/3, turn x_t/3); C: after it, (x_s/3, 1/3); B: before a straight response, (x_s/3, 1/3); D: after it, (1/3, 1/3); revisit 1/5 in all phases; A -> C at a turn passage with x_t kappa/3; B -> D at a straight passage with x_s kappa/3. The dynamic program stores upper bounds in float, and the depth-first search uses double. The recorded runs stop at T = AT = 4K - 3 and report the sum over NEX < n <= T. With T > AT the program also computes a remainder bound using left sub-eigenvectors and directed rounding. */ #include #include #include #include #include #pragma STDC FENV_ACCESS ON static void set_rounding(int mode) { if (fesetround(mode) != 0) { fprintf(stderr, "could not set floating-point rounding mode %d\n", mode); exit(EXIT_FAILURE); } } static int m, L, K, T, NEX, AT; static double xs, xt, ca, cb, hB, hC, third, fifth; static const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1}; static int nw = 0, *wcode, *lut; static int (*tgt)[4]; static unsigned char (*kind)[4]; static float *V[4], *Nv[4]; /* phases A, B, C, D */ static int ux, uy, vx, vy, cx, cy; static void wpos(const int *dirs, int len, int *px, int *py) { px[0] = 0; py[0] = 0; for (int i = 0; i < len; i++) { px[i+1] = px[i] + dx[dirs[i]]; py[i+1] = py[i] + dy[dirs[i]]; } } static int is_trail(const int *dirs, int len) { int px[64], py[64]; wpos(dirs, len, px, py); for (int i = 0; i < len; i++) for (int j = i + 1; j < len; j++) { if (px[i] == px[j] && py[i] == py[j] && px[i+1] == px[j+1] && py[i+1] == py[j+1]) return 0; if (px[i] == px[j+1] && py[i] == py[j+1] && px[i+1] == px[j] && py[i+1] == py[j]) return 0; } return 1; } static int cap = 0; static void gen(int *dirs, int len) { if (len == m) { if (nw == cap) { cap = cap ? 2 * cap : 1024; wcode = realloc(wcode, cap * sizeof(int)); } int c = 0; for (int i = 0; i < m; i++) c = c * 4 + dirs[i]; wcode[nw++] = c; return; } for (int d = 0; d < 4; d++) { if (len > 0 && d == (dirs[len-1] + 2) % 4) continue; dirs[len] = d; if (!is_trail(dirs, len + 1)) continue; gen(dirs, len + 1); } } static void decode(int c, int *dirs) { for (int i = m - 1; i >= 0; i--) { dirs[i] = c & 3; c >>= 2; } } static void build_windows(void) { int dirs[64]; gen(dirs, 0); lut = malloc(sizeof(int) << (2 * m)); for (long i = 0; i < (1L << (2 * m)); i++) lut[i] = -1; for (int i = 0; i < nw; i++) lut[wcode[i]] = i; tgt = malloc(nw * sizeof *tgt); kind = malloc(nw * sizeof *kind); for (int w = 0; w < nw; w++) { int px[64], py[64]; decode(wcode[w], dirs); wpos(dirs, m, px, py); int rev = 0; for (int i = 0; i < m; i++) if (px[i] == px[m] && py[i] == py[m]) rev = 1; for (int d = 0; d < 4; d++) { tgt[w][d] = -1; kind[w][d] = rev ? 2 : (d == dirs[m-1] ? 0 : 1); if (d == (dirs[m-1] + 2) % 4) continue; int nx = px[m] + dx[d], ny = py[m] + dy[d], bad = 0; for (int i = 0; i < m; i++) { if (px[i] == px[m] && py[i] == py[m] && px[i+1] == nx && py[i+1] == ny) bad = 1; if (px[i+1] == px[m] && py[i+1] == py[m] && px[i] == nx && py[i] == ny) bad = 1; } if (bad) continue; int nc = ((wcode[w] << 2) | d) & ((1 << (2 * m)) - 1); tgt[w][d] = lut[nc]; if (tgt[w][d] < 0) { fprintf(stderr, "window lookup failed\n"); exit(1); } } } } static int modK(int z) { return ((z % K) + K) % K; } static int NSITE, *nbr[4], *repx, *repy, ic, iu, id0 = -1, D0 = -1; static unsigned char *nearc; static int sidx(int x, int y) { int P2 = 2 * K; int p = ((x + y) % P2 + P2) % P2, q = ((x - y) % P2 + P2) % P2; return p * K + (q - (p & 1)) / 2; } static void build_sites(void) { NSITE = 2 * K * K; repx = malloc(NSITE * sizeof(int)); repy = malloc(NSITE * sizeof(int)); nearc = calloc(NSITE, 1); for (int d = 0; d < 4; d++) nbr[d] = malloc(NSITE * sizeof(int)); for (int p = 0; p < 2 * K; p++) for (int r = 0; r < K; r++) { int q = 2 * r + (p & 1), x = (p + q) / 2, y = (p - q) / 2, s = p * K + r; if (sidx(x, y) != s) { fprintf(stderr, "site map error\n"); exit(1); } repx[s] = x; repy[s] = y; } ic = sidx(0, 0); for (int s = 0; s < NSITE; s++) { for (int d = 0; d < 4; d++) nbr[d][s] = sidx(repx[s] + dx[d], repy[s] + dy[d]); for (int a = -2; a <= 2; a++) for (int b = -2; b <= 2; b++) if (abs(a) + abs(b) <= 2 && sidx(repx[s] + a, repy[s] + b) == ic) nearc[s] = 1; } } /* h-weighted response of a first-visit passage at (x,y) with in-direction ain and out-direction out; with killc, pairs containing the torus site of c are dead */ static double kappa(int x, int y, int ain, int out, int killc) { int back = (ain + 2) % 4, fx[2], fy[2], nf = 0; for (int k = 0; k < 4; k++) if (k != back && k != out) { fx[nf] = x + dx[k]; fy[nf] = y + dy[k]; nf++; } int ox = x + dx[out], oy = y + dy[out]; int Ax[3] = {fx[0], fx[0], fx[1]}, Ay[3] = {fy[0], fy[0], fy[1]}, Bx[3] = {fx[1], ox, ox}, By[3] = {fy[1], oy, oy}; double s = 0; for (int q = 0; q < 3; q++) { if (killc && (sidx(Ax[q], Ay[q]) == ic || sidx(Bx[q], By[q]) == ic)) continue; int isB = (Ax[q] == Bx[q] || Ay[q] == By[q]); s += (q == 0 ? ca : cb) * (isB ? hB : hC); } return s; } /* ---------------- exact prefix by DFS ---------------- */ #define GG 112 #define OFF 56 static unsigned char hbd[GG][GG], vbd[GG][GG]; static int V1[GG][GG], V2[GG][GG]; static int pd_[128]; static int zvx, zvy, zcx = OFF, zcy = OFF; static double closedK[256]; static int usedb(int x, int y, int k) { if (k == 0) return hbd[x][y]; if (k == 2) return hbd[x-1][y]; if (k == 1) return vbd[x][y]; return vbd[x][y-1]; } static void setb(int x, int y, int k, int v) { if (k == 0) hbd[x][y] = v; else if (k == 2) hbd[x-1][y] = v; else if (k == 1) vbd[x][y] = v; else vbd[x][y-1] = v; } static int pb(int x, int y, int j) { return (V1[x][y] < j) + (V2[x][y] < j); } /* Value of a closed trail of length n (directions pd_[0..n-1] from u) in the order from Appendix C, ascending in (x_i - 1)/w_i, w_i = x_i kappa_h(i); exact dead pairs (c, or a site passed twice before i). */ static int cmpd(const void *a, const void *b) { double d = ((const double *)a)[0] - ((const double *)b)[0]; return d < 0 ? -1 : d > 0; } static double sorted_value(int n) { int qx[130], qy[130]; qx[0] = OFF - 1; qy[0] = OFF; for (int i = 0; i < n; i++) { qx[i+1] = qx[i] + dx[pd_[i]]; qy[i+1] = qy[i] + dy[pd_[i]]; } double item[130][3]; int ni = 0, nrev = 0; for (int j = 0; j < n; j++) { int seen = 0; for (int i = 0; i < j; i++) if (qx[i] == qx[j] && qy[i] == qy[j]) seen++; if (seen) { nrev++; continue; } int ain = (j == 0) ? 2 : pd_[j-1], out = pd_[j]; double xx = (out == ain) ? xs : xt; int back = (ain + 2) % 4, fx[2], fy[2], nf = 0; for (int k = 0; k < 4; k++) if (k != back && k != out) { fx[nf] = qx[j] + dx[k]; fy[nf] = qy[j] + dy[k]; nf++; } int ox = qx[j+1], oy = qy[j+1]; int Ax[3] = {fx[0], fx[0], fx[1]}, Ay[3] = {fy[0], fy[0], fy[1]}, Bx[3] = {fx[1], ox, ox}, By[3] = {fy[1], oy, oy}; double kap = 0; for (int q = 0; q < 3; q++) { int sx[2] = {Ax[q], Bx[q]}, sy[2] = {Ay[q], By[q]}, dead = 0; for (int t = 0; t < 2; t++) { if (sx[t] == zcx && sy[t] == zcy) dead = 1; int cnt = 0; for (int i = 0; i < j; i++) if (qx[i] == sx[t] && qy[i] == sy[t]) cnt++; if (cnt >= 2) dead = 1; } if (dead) continue; int isB = (Ax[q] == Bx[q] || Ay[q] == By[q]); kap += (q == 0 ? ca : cb) * (isB ? hB : hC); } double w = xx * kap; item[ni][0] = (w > 0) ? (xx - 1) / w : 1e300; item[ni][1] = xx; item[ni][2] = w; ni++; } qsort(item, ni, sizeof item[0], cmpd); double tot = 0, pre = 1; for (int k = 0; k < ni; k++) { tot += item[k][2] * pre; pre *= item[k][1]; } double base = 1; for (int i = 0; i < n; i++) base *= third; for (int i = 0; i < nrev; i++) base *= fifth * 3.0; return tot * base; } static void dfs(int x, int y, int n, double PA, double PB, double QC, double QD, int code) { if (x == zvx && y == zvy && n > 0) { closedK[n] += sorted_value(n); return; } if (n == L) { int w = lut[code & ((1 << (2 * m)) - 1)]; if (w < 0) { fprintf(stderr, "prefix window not found\n"); exit(1); } long s = (long)w * NSITE + sidx(x - OFF, y - OFF); V[0][s] += (float)PA; V[1][s] += (float)PB; V[2][s] += (float)QC; V[3][s] += (float)QD; return; } int *slot = (V1[x][y] == 100000) ? &V1[x][y] : &V2[x][y]; int prior = pb(x, y, n); *slot = n; for (int k = 0; k < 4; k++) { int nx = x + dx[k], ny = y + dy[k]; if (n == 0 && D0 >= 0 && k != D0) continue; if (nx == zcx && ny == zcy) continue; if (usedb(x, y, k)) continue; double A2, B2, C2, D2; if (prior > 0) { A2 = PA * fifth; B2 = PB * fifth; C2 = QC * fifth; D2 = QD * fifth; } else { int ain = (n == 0) ? 2 : pd_[n-1]; int back = (ain + 2) % 4, fx[2], fy[2], nf = 0; for (int kk = 0; kk < 4; kk++) if (kk != back && kk != k) { fx[nf] = x + dx[kk]; fy[nf] = y + dy[kk]; nf++; } int Ax[3] = {fx[0], fx[0], fx[1]}, Ay[3] = {fy[0], fy[0], fy[1]}, Bx[3] = {fx[1], nx, nx}, By[3] = {fy[1], ny, ny}; double kap = 0; for (int q = 0; q < 3; q++) { if ((Ax[q] == zcx && Ay[q] == zcy) || (Bx[q] == zcx && By[q] == zcy)) continue; if (pb(Ax[q], Ay[q], n) >= 2 || pb(Bx[q], By[q], n) >= 2) continue; int isB = (Ax[q] == Bx[q] || Ay[q] == By[q]); kap += (q == 0 ? ca : cb) * (isB ? hB : hC); } if (k == ain) { /* straight */ double ws = xs * third; A2 = PA * ws; B2 = PB * ws; C2 = QC * ws; D2 = QD * third + B2 * kap; } else { /* turn */ double wt = xt * third; A2 = PA * wt; B2 = PB * third; C2 = QC * third + A2 * kap; D2 = QD * third; } } pd_[n] = k; setb(x, y, k, 1); dfs(nx, ny, n + 1, A2, B2, C2, D2, (int)((((unsigned)code << 2) | (unsigned)k) & ((1u << (2 * m)) - 1))); setb(x, y, k, 0); } *slot = 100000; } /* ---------------- one DP step on the torus ---------------- */ static void step(int exact) { long KK = NSITE; for (int p = 0; p < 4; p++) memset(Nv[p], 0, nw * KK * sizeof(float)); float f5 = (float)fifth, f3 = (float)third, fs = (float)(xs * third), ft = (float)(xt * third); for (int w = 0; w < nw; w++) { int ain = wcode[w] & 3; for (int d = 0; d < 4; d++) { int t = tgt[w][d]; if (t < 0) continue; float *sA = V[0] + (long)w * KK, *sB = V[1] + (long)w * KK, *sC = V[2] + (long)w * KK, *sD = V[3] + (long)w * KK; float *tA = Nv[0] + (long)t * KK, *tB = Nv[1] + (long)t * KK, *tC = Nv[2] + (long)t * KK, *tD = Nv[3] + (long)t * KK; int k = kind[w][d]; float kg = (float)kappa(0, 0, ain, d, 0); const int *nb = nbr[d]; { for (long s = 0; s < NSITE; s++) { long s2 = nb[s]; if (exact && (s == iu || s == id0)) { if (k == 2) continue; /* third visit */ if (D0 >= 0 && ((s == iu && d == D0) || (s == id0 && d == (D0 + 2) % 4))) continue; /* used bond */ tA[s2] += sA[s] * f5; tB[s2] += sB[s] * f5; tC[s2] += sC[s] * f5; tD[s2] += sD[s] * f5; continue; } if (k == 2) { tA[s2] += sA[s] * f5; tB[s2] += sB[s] * f5; tC[s2] += sC[s] * f5; tD[s2] += sD[s] * f5; } else { float kk = kg; if (exact && nearc[s]) kk = (float)kappa(repx[s], repy[s], ain, d, 1); if (k == 0) { float b2 = sB[s] * fs; tA[s2] += sA[s] * fs; tB[s2] += b2; tC[s2] += sC[s] * fs; tD[s2] += sD[s] * f3 + b2 * kk; } else { float a2 = sA[s] * ft; tA[s2] += a2; tB[s2] += sB[s] * f3; tC[s2] += sC[s] * f3 + a2 * kk; tD[s2] += sD[s] * f3; } } } } } } for (int p = 0; p < 4; p++) { float *s = V[p]; V[p] = Nv[p]; Nv[p] = s; } } /* left Perron-type vector: z <- (z T_phase)/max, weights (ws, wt, 1/5) */ static double perron(double *z, double ws, double wt) { double *tmp = malloc(nw * sizeof(double)), lam = 0; for (int w = 0; w < nw; w++) z[w] = 1; for (int it = 0; it < 40000; it++) { memset(tmp, 0, nw * sizeof(double)); for (int w = 0; w < nw; w++) for (int d = 0; d < 4; d++) { int t = tgt[w][d]; if (t < 0) continue; tmp[t] += z[w] * (kind[w][d] == 2 ? fifth : (kind[w][d] == 0 ? ws : wt)); } double mx = 0; for (int w = 0; w < nw; w++) if (tmp[w] > mx) mx = tmp[w]; double dl = 0; for (int w = 0; w < nw; w++) { double nv = tmp[w] / mx; dl = fmax(dl, fabs(nv - z[w])); z[w] = nv; } lam = mx; if (dl < 1e-15 && it > 200) break; } free(tmp); return lam; } /* fixed point zq = (zsrc Ksrc + zq Tq)/lt; response passes of type 'resp' (0 straight, 1 turn) with source weights */ static void postvec(double *zq, const double *zsrc, int resp, double srcw, double qs, double qt, double lt) { double *tmp = malloc(nw * sizeof(double)); for (int w = 0; w < nw; w++) zq[w] = 0; for (int it = 0; it < 40000; it++) { memset(tmp, 0, nw * sizeof(double)); for (int w = 0; w < nw; w++) { int ain = wcode[w] & 3; for (int d = 0; d < 4; d++) { int t = tgt[w][d]; if (t < 0) continue; int k = kind[w][d]; if (k == 2) { tmp[t] += zq[w] * fifth; continue; } tmp[t] += zq[w] * (k == 0 ? qs : qt); if (k == resp) tmp[t] += zsrc[w] * srcw * kappa(0, 0, ain, d, 0); } } double dl = 0; for (int w = 0; w < nw; w++) { double nv = tmp[w] / lt; dl = fmax(dl, fabs(nv - zq[w]) / (nv + 1e-300)); zq[w] = nv; } if (dl < 1e-14 && it > 200) break; } free(tmp); } int main(int argc, char **argv) { if (argc < 14) { fprintf(stderr, "usage\n"); return 1; } char X = argv[1][0]; m = atoi(argv[2]); L = atoi(argv[3]); K = atoi(argv[4]); T = atoi(argv[5]); AT = atoi(argv[6]); NEX = atoi(argv[7]); double cs = atof(argv[8]), ct = atof(argv[9]); ca = atof(argv[10]); cb = atof(argv[11]); hB = atof(argv[12]); hC = atof(argv[13]); /* the decimal constants are lower (c) / upper (a, b) bounds: move one ulp in the safe direction */ cs = nextafter(cs, 0.0); ct = nextafter(ct, 0.0); ca = nextafter(ca, INFINITY); cb = nextafter(cb, INFINITY); if (!((AT == 4 * K - 3 && T == AT) || (AT <= 2 * K - 3 && NEX >= 4 * K - 3 && T > AT))) { fprintf(stderr, "invalid (AT,T,NEX)\n"); return 1; } if (L < m || K < m + 3 || L > AT) { fprintf(stderr, "need m <= L <= AT, K >= m+3\n"); return 1; } set_rounding(FE_UPWARD); volatile double one = 1.0, three = 3.0, five = 5.0; xs = one / (cs < 1 ? cs : 1); xt = one / (ct < 1 ? ct : 1); third = one / three; fifth = one / five; build_windows(); build_sites(); long KK = NSITE; fprintf(stderr, "m=%d windows=%d K=%d states/phase=%ld mem=%.2f GB\n", m, nw, K, nw * KK, 8.0 * nw * KK * 4 / 1e9); for (int p = 0; p < 4; p++) { V[p] = calloc(nw * KK, sizeof(float)); Nv[p] = calloc(nw * KK, sizeof(float)); if (!V[p] || !Nv[p]) { fprintf(stderr, "alloc failed\n"); return 1; } } for (int i = 0; i < GG; i++) for (int j = 0; j < GG; j++) { V1[i][j] = 100000; V2[i][j] = 100000; } int zux = OFF - 1, zuy = OFF; if (X == 'B') { zvx = OFF + 1; zvy = OFF; } else { zvx = OFF; zvy = OFF + 1; } cx = 0; cy = 0; iu = sidx(zux - OFF, zuy - OFF); if (argc > 14) D0 = atoi(argv[14]); if (D0 >= 0) id0 = sidx(zux - OFF + dx[D0], zuy - OFF + dy[D0]); dfs(zux, zuy, 0, 1.0, 1.0, 0.0, 0.0, 0); printf("# tailmem5 (straights-first order, diagonal quotient, u-revisit, sorted closed DFS, first-direction split) D0=%d X=%c m=%d L=%d K=%d T=%d AT=%d NEX=%d cs=%.6f ct=%.6f a=%.6f b=%.6f h=(%.6f,%.6f)\n", D0, X, m, L, K, T, AT, NEX, cs, ct, ca, cb, hB, hC); printf("# E = exact (DFS), D = DP with c killed / v absorbing, F = free torus; values h-weighted upper bounds\n"); double ex = 0; for (int n = 1; n <= L; n++) if (closedK[n] > 0) { printf("E %d %.12e\n", n, closedK[n]); if (n <= NEX) ex += closedK[n]; } printf("# EXACT(n<=min(L,NEX)) = %.12e\n", ex); double tail = 0; long sv = sidx(zvx - OFF, zvy - OFF), sc = ic; for (int n = L + 1; n <= L && n <= NEX; n++) ; for (int n = NEX + 1; n <= L; n++) tail += closedK[n]; for (int t = L; t < T; t++) { int exact = (t + 1 <= AT); step(exact); double arr = 0; for (int w = 0; w < nw; w++) arr += (double)V[2][(long)w * KK + sv] + (double)V[3][(long)w * KK + sv]; if (exact) for (int p = 0; p < 4; p++) for (int w = 0; w < nw; w++) { V[p][(long)w * KK + sv] = 0; V[p][(long)w * KK + sc] = 0; } if (t + 1 > NEX) tail += arr; if (arr > 0) printf("%c %d %.10e\n", exact ? 'D' : 'F', t + 1, arr); fflush(stdout); } if (T == AT) { printf("# TAIL(%d r) ok = 0; if (l[p][w] / r > worst) worst = l[p][w] / r; } set_rounding(FE_UPWARD); double alpha = 0; for (int p = 0; p < 4; p++) for (int w = 0; w < nw; w++) for (long s = 0; s < KK; s++) { double a = (double)V[p][(long)w * KK + s] / z[p][w]; if (a > alpha) alpha = a; } double zsum = 0; for (int w = 0; w < nw; w++) zsum += z[2][w] + z[3][w]; set_rounding(FE_DOWNWARD); double den = 1.0 - lcheck; set_rounding(FE_UPWARD); double rem = alpha * zsum * lcheck / den; printf("# remainder: lamA=%.9f lamB=%.9f lcheck=%.9f check=%s (max ratio %.12f) alpha=%.6e |zC+zD|=%.6e remainder<=%.6e\n", lamA, lamB, lcheck, ok ? "OK" : "FAILED", worst, alpha, zsum, rem); printf("# TAIL(n>%d) <= %.9e (sum over t<=%d: %.9e + remainder %.6e) %s\n", NEX, tail + rem, T, tail, rem, ok ? "" : "CHECK FAILED - NOT RIGOROUS"); return 0; } ''' def main(argv): workdir, cc, compile_only, verbose = None, 'gcc', False, False i = 0 while i < len(argv): a = argv[i] if a == '--print-source': sys.stdout.write(C_SOURCE) return 0 if a == '--write-source': os.makedirs(argv[i + 1], exist_ok=True) with open(os.path.join(argv[i + 1], NAME + '.c'), 'w') as f: f.write(C_SOURCE) return 0 if a == '--workdir': workdir = argv[i + 1]; i += 2; continue if a == '--cc': cc = argv[i + 1]; i += 2; continue if a == '--compile-only': compile_only = True; i += 1; continue if a == '--verbose': verbose = True; i += 1; continue if a == '--': i += 1 break args = argv[i:] if not compile_only and not args: sys.stderr.write(__doc__) return 1 tmp = workdir is None d = tempfile.mkdtemp(prefix=NAME + '-') if tmp else os.path.abspath(workdir) os.makedirs(d, exist_ok=True) try: with open(os.path.join(d, NAME + '.c'), 'w') as f: f.write(C_SOURCE) cmd = [cc] + CFLAGS + [NAME + '.c'] + LIBS + ['-o', NAME] r = subprocess.run(cmd, cwd=d, stdout=subprocess.PIPE, stderr=subprocess.STDOUT, universal_newlines=True) if verbose or r.returncode != 0: sys.stderr.write('cd %s && %s\n%s' % (d, ' '.join(cmd), r.stdout)) if r.returncode != 0: sys.stderr.write('%s.py: compilation failed\n' % NAME) return 1 if compile_only: return 0 sys.stdout.flush() return subprocess.run([os.path.join(d, NAME)] + args).returncode finally: if tmp: shutil.rmtree(d, ignore_errors=True) if __name__ == '__main__': if hashlib.sha256(C_SOURCE.encode('ascii')).hexdigest() != SHA256: sys.exit('%s.py: the stored C source does not match its sha256 digest' % NAME) sys.exit(main(sys.argv[1:]))