twolinks.py
Checks: LATENCY: The matching law rule.
Cited on: LATENCY.
To run it: save twolinks.py, with chains.py, hulls.py, manystream.py, poles.py, redundant.py beside it; needs numpy.
"""
twolinks.py -- a tree of hulls at a consumer's link: can consumer j >= 3
of a product-fed chain read one below its floor, through consumer j - 1's
output stream, where the budget (the matching law's flag) says dead?
THE INHERITED BEAT (property, by hand). A consumer at its floor reads
its producer at inset 0 (its threshold Lam w - Mh eta <= b^L (w - 1)
holds at eta = 0 by the floor's definition, and a hull of inset 0 is the
producer string's box), so it lives behind any producer. At (20, 8, 12)
and its mirror Lam_3 <= 1: with the two-unit certificate putting
consumer 2 at 1, the n-unit chain reads naive - 1 at every n >= 2, where
chains.programme's least is the naive sum.
THE QUESTION, one level down. On the budget floor-1 consumers never
gain (L = 0 needs 1 + Mh^(j-1) < 3/b, the inset at most w - 1); a tree
hands narrower hulls, so T2 reads them at L = 0 on the grid. The probe
reads the floor-2 run, Lam_j = Mh + Mh^j > 1, which at j >= 3 needs
Mh > 0.6823.
THE TRANSFER (re-derived). hulls.Grid reads its producer through d (a
bound on every image's width at the next level), the producer's range
and the box. Consumer j - 1 at delay L reads z (box w, |z| <= Mh) and
its producer through a hull F wide (|u| <= tau_(j-2) = Mh^(j-1)); its
image is a product of two intervals, an interval at most
(Mh F + tau_(j-2) w)/b^L wide. So Grid with that d, tau = Mh^j in
eta_max, and the range times_z^(j-2)(head range) certifies life at link
j; rounding stays conservative (d up, eta down, range outward).
ARMS, per link (j - 1, j), 3 <= j <= run_units, L_j* = 2, consumer j at
L = 1. A: the budget (chains.links: floor chain / pairwise). B0: the
tree, producer j - 1 at its floor reading inset 0. Bv: the same reading
the floor chain's leftover v. C (j = 3): the head's own tree feeding
consumer 2, F = min(eta*_1, w - v).
PREDICTIONS (frozen). P1: every A gain is live under Bv. P2: tree gains
past A are rare, a handful of links, at the run's last unit. P3: C adds
at most what Bv adds.
KILL (frozen). The script prints "tree gains past the matching: B0 N0,
Bv Nv, C Nc"; killed iff all three are 0.
CONTROLS, read first. (1) hulls.section_tree: (20, 8, 12) and its mirror
live at eta_max, 0 faults. (2) Identity: the link grid built with the
head's d, tau and range is hulls.Grid (live at eta_max, eta*) at every
cell of radices 3..12. (3) P1. (4) One certificate child moved past its
box at a live link is a fault.
USAGE: python twolinks.py [K [bmax]], K = 40 and bmax = 12 bare; the
record run is python twolinks.py 200 40.
FINDINGS (entered after the run; every number is a print, K = 200,
radices 3..40).
- The controls read first: (20, 8, 12) and its mirror live at eta_max
1085/1083, 0 faults; the link grid at the head's parameters is Grid
at every cell of radices 3..12; P1 held (727 budget gains, every one
live under Bv); a child moved past its box makes 2 faults.
- THE KILL MISSED. 228 cells carry a floor-2 consumer past 2, 4207
links. Tree gains past the matching: B0 17, Bv 18, C 1, at 18
cells, 0 checker faults. B0 and Bv agree but at (7, 2, 5), j = 7,
live on the floor chain's leftover alone; C adds nothing to Bv
(live at 10 of the 228 links at j = 3, past the budget only at
(8, 3, 5), where Bv is too).
- THE EDGE. The budget's gains are a suffix of the floor-2 run at all
228 cells, and every tree gain past them sits one link upstream of
the suffix's first (0 off), or at the run's last unit where the suffix
is empty ((8, 3, 5), j = 3 of a 4-unit chain). P2 as frozen ("at
the run's last unit") was wrong at 17 of 18: where the grid
certifies a gain past the budget, at 18 of 228 cells, it moves the
budget's threshold by one link upstream.
- THE CHAIN. With nu' the matching over the pairwise flags (budget at
inset 0, or B0; at the head's link the budget or Grid), naive - nu'
is below chains.programme's least at 98 of the 935 prefixes read at
the 17 cells with a B0 gain, by 1 at every one, e.g. at (8, 3, 5)
n = 3 (5 against 6), (12, 3, 9) and (17, 4, 13) n = 7 (13 against
14), (10, 2, 8) n = 14 (27 against 28).
- T2. The first floor-1 unit past each run, 441
links (the chain of run_units holds one): eta_max(0) < 0 at 440,
dead behind any producer (the generic multiplier); 0.0002 at the
other, (14, 2, 12) j = 33, below its d, so the grid never runs.
Units further down are not read.
RUN RECORD: K = 40, radices 3..12, 0.5 s (the rehearsal); K = 200,
radices 3..20, 6.0 s, 24.6 MB; K = 200, radices 3..40, 92.0 s, peak
38.7 MB under a memory guard. With T2: 6/6, 92.0 s, peak 38.9 MB.
"""
import math
import os
import sys
import time
from fractions import Fraction as Fr
os.environ.setdefault("OPENBLAS_NUM_THREADS", "1")
import chains # noqa: E402
import hulls # noqa: E402
import manystream as ms # noqa: E402
CHECKS = hulls.CHECKS
check = hulls.check
def make_grid(cell, d_fr, tau, rng, K, L=1):
"""hulls.Grid with its producer's d, the consumer's tau and the
producer's range set; the consumer at delay L."""
g = hulls.Grid(cell, 2, L, K)
g.d_fr = d_fr
g.eta_fr = (Fr(cell.b) ** L * (cell.w - 1) - tau * cell.w) / cell.Mh
g.d = math.ceil(d_fr * g.G)
g.eta_max = math.floor(g.eta_fr * g.G)
g.lo, g.hi = math.floor(rng[0] * g.G), math.ceil(rng[1] * g.G)
return g
def verdict(g):
"""(live at eta_max, checker faults or None)."""
if g.eta_max < g.d:
return False, None
lv, F, _ = g.live(g.eta_max)
return lv, (g.check(F, g.certificate(F), g.eta_max) if lv else None)
def head_rng(cell):
return chains.xy_head(cell)[3]
def chain(cell, n):
"""Per consumer j = 2..n: (Lam_j, floor, the leftover v it reads on
the floor chain, its producer's range)."""
L1s, S, lams, rooms = chains.chain_units(cell, chains.xy_head, n)
v, rng, out = S(L1s), head_rng(cell), []
for lam, rm in zip(lams, rooms):
Ls = chains.unit_floor(cell, lam)
out.append((lam, Ls, v, rng))
v = min(chains.leftover(cell, lam, Ls, min(v, cell.w - 1)), rm)
rng = chains.times_z(cell, rng)
return out
def link_grid(cell, units, j, F, K):
"""Link (j - 1, j): producer consumer j - 1 at its floor reading a
hull F wide."""
lam_p, Lp, _, rng_p = units[j - 3]
tau_in = cell.Mh ** (j - 1)
d_fr = (tau_in * cell.w + cell.Mh * F) / Fr(cell.b) ** Lp
return make_grid(cell, d_fr, cell.Mh ** j, chains.times_z(cell, rng_p),
K)
def section_control(K):
print("T0 controls")
hulls.section_tree()
off = []
for cell in hulls.cells1(3, 12):
L1 = chains.floor_xy(cell)
lam2 = cell.Mh ** 2 + cell.Mh
L2 = 1 if lam2 > 1 else 0
g0 = hulls.Grid(cell, L1, L2, K)
g1 = make_grid(cell, 2 * cell.Mh * cell.w / Fr(cell.b) ** L1,
cell.Mh ** 2, head_rng(cell), K, L2)
a = (g0.d, g0.eta_max, g0.lo, g0.hi)
b = (g1.d, g1.eta_max, g1.lo, g1.hi)
cap = min(g0.G + g0.d + 2 * g0.G, g0.Mm + g0.Mp)
same = a == b and (g0.eta_max < g0.d or
g0.live(g0.eta_max)[0] == g1.live(g1.eta_max)[0])
same = same and g0.eta_star(cap) == g1.eta_star(cap)
if not same:
off.append((cell.b, cell.am, cell.ap))
check("T0 the link grid at the head's d, tau, range is Grid, radices "
"3..12", not off, f"off at {off[:4]}")
def eta_star_head(cell, K):
L1 = chains.floor_xy(cell)
g = hulls.Grid(cell, L1, 1, K)
return g.eta_star(min(g.G + g.d + 2 * g.G, g.Mm + g.Mp)), g.G
def section_links(K, bmax):
print(f"T1 the consumer links, radices 3..{bmax}, K {K}")
t0 = time.time()
rows, p1_off, planted, cells_run = [], [], None, 0
for b in range(3, bmax + 1):
for cell in hulls.cells1(b, b):
A1, L1s, S, _ = chains.xy_head(cell)
if S(L1s) < 0:
continue
n = chains.run_units(cell, A1)
units = chain(cell, n)
ls = chains.links(cell, chains.xy_head, n)
js = [j for j in range(3, n + 1) if units[j - 2][1] == 2]
if not js:
continue
cells_run += 1
for j in js:
_, gainA, pairA = ls[j - 2]
v = units[j - 3][2]
gv = link_grid(cell, units, j, cell.w - min(v, cell.w - 1), K)
g0 = link_grid(cell, units, j, cell.w, K)
lv, fv = verdict(gv)
l0, f0 = verdict(g0)
lc = fc = None
if j == 3:
es, G = eta_star_head(cell, K)
F = cell.w - min(v, cell.w - 1)
if es is not None:
F = min(F, Fr(es, G))
lc, fc = verdict(link_grid(cell, units, j, F, K))
if gainA and not lv:
p1_off.append((b, cell.am, cell.ap, j))
if planted is None and lv:
F_, _ = gv.fixpoint(gv.eta_max)
cert = gv.certificate(F_)
s = next((s for s, k in enumerate(cert)
if len(k) >= 2 and F_[s] >= gv.d), None)
if s is not None:
planted = gv.check(F_, cert, gv.eta_max,
plant=(s, cert[s][0][0]))
lam = units[j - 2][0]
rows.append(dict(cell=(b, cell.am, cell.ap), j=j, n=n,
lam=lam, A=gainA, A0=pairA, B0=l0, Bv=lv,
C=lc, faults=(f0, fv, fc)))
print(f" {cells_run} cells with a floor-2 consumer past 2, "
f"{len(rows)} links, {time.time() - t0:.1f} s")
faults = [r for r in rows if any(f not in (None, 0) for f in r["faults"])]
check("T1 0 checker faults at every live link", not faults,
f"{faults[:3]}")
check("T1 P1: every budget gain is live under Bv", not p1_off,
f"off at {p1_off[:4]}")
check("T1 a child moved past its box is a fault",
planted is not None and planted > 0, f"planted {planted}")
pastB0 = [r for r in rows if r["B0"] and not r["A"]]
pastBv = [r for r in rows if r["Bv"] and not r["A"]]
pastC = [r for r in rows if r["C"] and not r["A"]]
print(f" budget gains {sum(r['A'] for r in rows)}, live: B0 "
f"{sum(r['B0'] for r in rows)}, Bv {sum(r['Bv'] for r in rows)},"
f" C {sum(bool(r['C']) for r in rows)} (of "
f"{sum(r['j'] == 3 for r in rows)} links at j = 3)")
print(f" tree gains past the matching: B0 {len(pastB0)}, Bv "
f"{len(pastBv)}, C {len(pastC)} at "
f"{sorted({(r['cell'], r['j']) for r in pastB0 + pastBv + pastC})}")
edge_off, not_suffix = [], []
for c in sorted({r["cell"] for r in rows}):
run = sorted(r["j"] for r in rows if r["cell"] == c)
ga = [r["j"] for r in rows if r["cell"] == c and r["A"]]
if ga and ga != list(range(ga[0], run[-1] + 1)):
not_suffix.append(c)
for r in rows:
if r["cell"] == c and (r["B0"] or r["Bv"]) and not r["A"]:
edge = ga[0] - 1 if ga else run[-1]
if r["j"] != edge:
edge_off.append((c, r["j"], edge))
print(f" budget gains not a suffix of the floor-2 run at "
f"{len(not_suffix)} cells {not_suffix[:4]}")
print(f" tree gains off the edge (one link upstream of the budget's "
f"first "
f"gain, or the run's last unit where it has none): {edge_off}")
seen = set()
for r in pastB0 + pastBv + pastC:
if (r["cell"], r["j"]) in seen:
continue
seen.add((r["cell"], r["j"]))
cell = ms.Cell(*r["cell"])
naive, match, least, *_ = chains.programme(cell, chains.xy_head,
r["j"])
last = r["j"] == r["n"] or chains.unit_floor(
cell, cell.Mh + cell.Mh ** (r["j"] + 1)) < 2
gains = [q["j"] for q in rows if q["cell"] == r["cell"] and q["A"]]
print(f" {r['cell']} j {r['j']} of run {r['n']}: Lam_j - 1 "
f"{float(r['lam'] - 1):.5f}, B0 {r['B0']} Bv {r['Bv']} C "
f"{r['C']}; at n = j naive {naive}, matching {match}, "
f"least {least}, the run's last floor-2 unit {last}; budget "
f"gains at j = {gains[:3]}{'...' if len(gains) > 3 else ''}")
section_totals(rows, K)
return rows
def section_totals(rows, K):
"""Every prefix n of each cell with a B0 gain past the matching: the
total naive - nu', nu' the matching over the pairwise flags (the
budget's at inset 0, or the tree's B0; at the head's link the
budget's or hulls.Grid's), against chains.programme's least."""
beats, read = [], 0
for c in sorted({r["cell"] for r in rows if r["B0"] and not r["A"]}):
cell = ms.Cell(*c)
A1, L1s, S, _ = chains.xy_head(cell)
n = chains.run_units(cell, A1)
ls = chains.links(cell, chains.xy_head, n)
tree = {r["j"]: r["B0"] for r in rows if r["cell"] == c}
head = False
if ls[0][0] == 2:
g = hulls.Grid(cell, L1s, 1, K)
head = g.eta_max >= g.d and g.live(g.eta_max)[0]
flags = [ls[0][2] or head] + [ls[j - 2][2] or tree.get(j, False)
for j in range(3, n + 1)]
nu = chains.matchings(flags)
for m, (naive, match, least, *_) in chains.programme_all(
cell, chains.xy_head, n).items():
read += 1
if naive - nu[m - 2] < least:
beats.append((c, m, naive - nu[m - 2], least))
print(f" chains below the programme's least: {len(beats)} of {read} "
f"prefixes read, by {sorted({b[3] - b[2] for b in beats})}, at "
f"{sorted({b[0] for b in beats})}")
print(f" first per cell: "
f"{[b for i, b in enumerate(beats)
if i == 0 or beats[i - 1][0] != b[0]]}")
def section_floor1(K, bmax):
"""T2: each floor-1 consumer j >= 3 of the chain of run_units at
L = 0, its producer at its floor reading inset 0."""
print(f"T2 floor-1 consumers at L = 0, radices 3..{bmax}, K {K}")
read, live, top, neg = 0, [], None, 0
for b in range(3, bmax + 1):
for cell in hulls.cells1(b, b):
A1, L1s, S, _ = chains.xy_head(cell)
if S(L1s) < 0:
continue
n = chains.run_units(cell, A1)
units = chain(cell, n)
for j in range(3, n + 1):
if units[j - 2][1] != 1:
continue
g = link_grid(cell, units, j, cell.w, K)
g0 = make_grid(cell, g.d_fr, cell.Mh ** j,
(g.lo / Fr(g.G), g.hi / Fr(g.G)), K, L=0)
read += 1
top = g0.eta_fr if top is None else max(top, g0.eta_fr)
neg += g0.eta_fr < 0
if verdict(g0)[0]:
live.append((b, cell.am, cell.ap, j))
print(f" {read} floor-1 links, eta_max(0) at most "
f"{float(top):.4f}, below 0 (dead behind any producer, the "
f"generic multiplier) at {neg}; live at L = 0: {live}")
return read, live
def main():
K = int(sys.argv[1]) if len(sys.argv) > 1 else 40
bmax = int(sys.argv[2]) if len(sys.argv) > 2 else 12
t0 = time.time()
section_control(K)
if not all(CHECKS):
print("CONTROL FAILED; nothing below is read")
raise SystemExit(1)
section_links(K, bmax)
section_floor1(K, bmax)
print(f"{sum(CHECKS)}/{len(CHECKS)} checks passed, "
f"{time.time() - t0:.1f} s")
raise SystemExit(0 if all(CHECKS) else 1)
if __name__ == "__main__":
main()