""" graphs.py -- what a tree of on-line product units pays: the narrowed reader's programme carried from a chain to a tree. QUESTION. chains.py prices units in series: a consumer below its floor spends its producer's leftover inset, the least total over delay assignments read by a pass along the chain. A graph adds fan-in, a unit reading two produced streams, each through its own hull. On small trees at one cell, does the programme read below NAIVE (below) where no chain does, (a) by the new pairs of input magnitudes a tree carries, or (b) by slack: an input that arrives early may sit one delay above its floor at no cost to the latency, handing its consumer a far larger inset? THE SETTING. One slack-1 representable cell, a+- <= b - 2 (M^ < 1), as chains.py. A stream is FRESH (largest magnitude M^, read through no hull) or PRODUCED by a unit (largest magnitude tau, read through a hull of its box inset by eta). A product unit reading U and V has Lam = tau_U + tau_V, and over hulls of widths h_U, h_V its image is at most tau_V h_U + tau_U h_V wide in its level's units (|u|, |v| bounded at every point: no cross term), so at delay L it is alive where v(L) = (w - 1) - (Lam w - tau_V eta_U - tau_U eta_V)/b^L >= 0, and hands on min(v(L), its room), chains.py::leftover at a fresh input. A head x y is the unit over two fresh streams; its leftover is chains.py's budget_xy, capped by its room. Cost: the LATENCY, the longest path's sum of delays (a unit reading two streams waits for the later). Its floor L* is the least L alive at zero insets; NAIVE is the latency at every unit's floor. THE PASS (the tree programme). Per unit and per latency t, B(t) is the best leftover its subtree hands at latency <= t: the max over L of v(L) on the inputs' B(t - L), each inset capped at w - 1, a fresh input handing 0 at every t >= 0. v rises in L and in each inset, so B rises in t and the pass is exact for the programme. LEAST is the least t with the root alive. Delays searched: 0 .. L* + 3 per unit, a superset of the frozen L* - 1 .. L* + 2; the pass is exact within it. The w - 1 cap on insets never binds here (v < w - 1). A HELD unit is searched at its floor alone. SHAPES. C = (x y) z, the chain's two units; P = (x y)(x' y'), a pair of heads; S = ((x y) z)(x' y'), the bare head x' y' early by the consumer's delay; S_hold, S with x' y' held at its floor; Q = ((x y) z)((x' y') z'). PREDICTIONS (frozen before this code). P gains where 2 M^2 - 1 lies in (0, 2 M^2 S/w], disjoint from C's cells, (8, 3, 5) among them at least 3 against naive 4. S gains on a window about tau_U/b wide around M^3 + M^2 = 1, more cells than S_hold. Q thin. CONTROLS, read before any shape. GA: C's least is chains.py::two_unit(cell, xy_head)'s least at every cell. GB: P at (8, 3, 5) reads 3 against 4, the hand value. GC (replacing the frozen one, which held by construction): at (4, 2, 2), where the threshold-miss law's z (x y) reads one below its floor and S's root (floor 1, dead at 0 at any inset) cannot, S with its consumer (x y) z held reads naive, and with its bare head x' y' held reads naive - 1. GE (added after the run, its hand values printed): T(n) the balanced product tree of n fresh leaves, T(1) fresh, T(n) = (T(ceil(n/2)), T(floor(n/2))); at (8, 3, 5) the unit (T(6), T(16)) reads naive 7, least 5, its four (2, 2) units at delay 1 (from floor 2) and its root, Lam = M^6 + M^16 = 0.1374 just above 1/b, at 0 (from floor 1) on T(6)'s leftover 0.0499 and T(16)'s 0.1247, v = +0.0026: two gains on one path. TRACE names the units below their floors in one least assignment, the B(t) argmax at each unit. THE CHAIN BASELINE. A cell counts as outside the chains when no chain of 2 to 12 units behind a product head gains there (sum heads not read) (chains.py::two_unit and chains.py::programme_all). KILL. Per shape, the count of cells with least < naive and how many lie outside C's set (the baseline as frozen; the chain baseline was added after the run). (a) dies if P and Q print 0 outside C's set; (b) dies if S's count equals S_hold's. FINDINGS (every number a print of the run below). Controls: GA 441 cells, 0 off; GB naive 4, least 3; GC (5, 5) and (5, 4). A planted break (hold ignoring its path), run on a scratch copy and not part of this run, fails GC at (5, 4), (5, 4). GE naive 7, least 5, the four (2, 2) units at 1 and the root at 0; a plant forbidding a floor-1 unit delay 0 fails GE alone, least 6. C gains at 17 cells, the threshold-miss law's 17 with their mirrors. P gains at 12, all outside C's, 10 outside every chain to 12 units: (8, 3, 5) (15, 5, 10) (19, 6, 13) (22, 7, 15) (25, 8, 17) (26, 8, 18) (29, 9, 20) (32, 10, 22) (36, 11, 25) (39, 12, 27); chains reach (5, 2, 3) and (12, 4, 8), where the four-unit chain's last link, Lam = M^ + M^4 just above 1, reads one below its floor (by hand, not printed here). (a) survives: a tree reads below NAIVE at cells where no chain of up to 12 units behind a product head does. Q gains at 26, 9 outside C's, 2 outside every chain ((35, 8, 27), (40, 9, 31)); its two inner chains gain at C's 17 in parallel, one digit. S gains at 26, 9 outside C's, none outside those chains; S_hold at 25, 8 outside C's. (b) survives against its frozen kill by one cell, (6, 2, 4), which a chain reaches too: over these cells and shapes, slack bought no cell those chains do not. The frozen premise behind the predicted widening, that a head hands O(1/b^2) at its floor, was wrong: its budget (w - 1) - 2 M^ w/b^L1* is already a large part of w - 1. No shape of the five gains 2 or more; GE's tree does. RUN RECORD. 441 cells, 4/4 checks, 8.1 s, peak commit 8.6 MB under a memory guard. """ import sys import time from fractions import Fraction as Fr import chains CHECKS = [] FRESH = "z" def check(name, ok, detail=""): CHECKS.append(bool(ok)) tail = f" ({detail})" if detail else "" print(f" {'PASS' if ok else 'FAIL'} {name}{tail}") def head(): return (FRESH, FRESH) SHAPES = { "C": (head(), FRESH), "P": (head(), head()), "S": ((head(), FRESH), head()), "Q": ((head(), FRESH), (head(), FRESH)), } def cells(): for cell in chains.cells(3, 40, slack=1): if chains.representable(cell) and cell.Mh < 1: yield cell def iprod(r, s): c = [x * y for x in r for y in s] return (min(c), max(c)) def v(cell, lam, L, tu, tv, eu, ev): return cell.w - 1 - (lam * cell.w - tv * eu - tu * ev) / Fr(cell.b) ** L def step(cell, kids, t, Ls_range, room): """(leftover, L) of the best delay in Ls_range at latency t over children kids = (tu, tv, bu, bv), (None, None) where dead.""" tu, tv, bu, bv = kids best = (None, None) for L in Ls_range: if t - L < 0 or bu[t - L] is None or bv[t - L] is None: continue eu, ev = (min(x, cell.w - 1) for x in (bu[t - L], bv[t - L])) r = v(cell, tu + tv, L, tu, tv, eu, ev) if r >= 0: r = min(r, room) if best[0] is None or r > best[0]: best = (r, L) return best def floor(cell, tu, tv): Ls = 0 while v(cell, tu + tv, Ls, tu, tv, 0, 0) < 0: Ls += 1 return Ls def build(cell, node, hold, tmax, path=(), memo=None): """(tau, range, B, naive) of a node; B a list over t = 0..tmax of the best leftover at latency <= t, None where dead. hold: True to search every unit at its floor alone, or the path (child indices from the root) of one unit. memo, a dict, caches nodes (hold None only).""" if memo is not None and node in memo: return memo[node] if node == FRESH: out = (cell.Mh, (-cell.Mm, cell.Mp), [Fr(0)] * (tmax + 1), 0) if memo is not None: memo[node] = out return out assert memo is None or hold is None U, V = node tu, ru, bu, nu = build(cell, U, hold, tmax, path + (0,), memo) tv, rv, bv, nv = build(cell, V, hold, tmax, path + (1,), memo) rng = iprod(ru, rv) room = chains.room(cell, rng) assert cell.Mm + rng[0] >= 0 and cell.Mp - rng[1] >= 0 Ls = floor(cell, tu, tv) held = hold is True or hold == path Ls_range = [Ls] if held else range(0, Ls + 4) B = [step(cell, (tu, tv, bu, bv), t, Ls_range, room)[0] for t in range(tmax + 1)] out = (tu * tv, rng, B, Ls + max(nu, nv)) if memo is not None: memo[node] = out return out def tree(n): """T(n), the balanced product tree of n fresh leaves.""" return FRESH if n == 1 else (tree((n + 1) // 2), tree(n // 2)) def leaves(node): return 1 if node == FRESH else leaves(node[0]) + leaves(node[1]) def trace(cell, node, t, memo, out): """Append (d_U, d_V, L, L*) for each unit below its floor in one least assignment of node at latency t, the B(t) argmax at each unit; memo as build left it.""" if node == FRESH: return U, V = node assert U in memo and V in memo, "trace reads build's memo" tu, ru, bu, _ = build(cell, U, None, 0, memo=memo) tv, rv, bv, _ = build(cell, V, None, 0, memo=memo) Ls = floor(cell, tu, tv) room = chains.room(cell, iprod(ru, rv)) r, L = step(cell, (tu, tv, bu, bv), t, range(0, Ls + 4), room) assert r is not None if L < Ls: out.append((leaves(U), leaves(V), L, Ls)) trace(cell, U, t - L, memo, out) trace(cell, V, t - L, memo, out) def price(cell, shape, hold=None, tmax=24): _, _, B, naive = build(cell, shape, hold, tmax) least = next((t for t, x in enumerate(B) if x is not None), None) return naive, least def controls(cs): print("GA..GE the controls") off = 0 for cell in cs: n, lst = price(cell, SHAPES["C"]) nn, ll, _, _ = chains.two_unit(cell, chains.xy_head) off += (n, lst) != (nn, ll) check("GA C is two_unit's (naive, least) at every cell", off == 0, f"{len(cs)} cells, {off} off") n, lst = price(chains.ms.Cell(8, 3, 5), SHAPES["P"]) check("GB P at (8, 3, 5) reads 3 against 4", (n, lst) == (4, 3), f"naive {n}, least {lst}") cell = chains.ms.Cell(4, 2, 2) n0, l0 = price(cell, SHAPES["S"], hold=(0,)) n1, l1 = price(cell, SHAPES["S"], hold=(1,)) check("GC S at (4, 2, 2): consumer held naive, bare head held " "naive - 1", (l0, l1) == (n0, n1 - 1), f"({n0}, {l0}), ({n1}, {l1})") cell, root, memo = chains.ms.Cell(8, 3, 5), (tree(6), tree(16)), {} _, _, B, naive = build(cell, root, None, 24, memo=memo) least = next(t for t, x in enumerate(B) if x is not None) low = [] trace(cell, root, least, memo, low) left = [memo[tree(k)][2][least] for k in (6, 16)] show = [("-" if x is None else f"{float(x):.4f}") for x in left] pairs = sorted((u, w_) for u, w_, _, _ in low) check("GE (T(6), T(16)) at (8, 3, 5): 5 against 7, the four (2, 2) " "units and the root gaining", (naive, least, pairs) == (7, 5, [(2, 2)] * 4 + [(6, 16)]) and price(cell, root) == (naive, least), f"naive {naive}, least {least}, low {low}; root Lam " f"{float(cell.Mh ** 6 + cell.Mh ** 16):.4f}, leftovers at " f"latency {least} {show[0]} and {show[1]}, root " f"{float(B[least]):+.4f}") def chain_gains(cell): naive, least, _, _ = chains.two_unit(cell, chains.xy_head) return least < naive or any( r[2] < r[0] for r in chains.programme_all(cell, chains.xy_head, 12).values()) def name(cell): return f"({cell.b}, {cell.am}, {cell.ap})" def main(): t0 = time.time() cs = list(cells()) controls(cs) if not all(CHECKS): print("\nCONTROL FAILED: nothing below is read.") raise SystemExit(1) gains = {} for key, shape in SHAPES.items(): gains[key] = {name(c): price(c, shape) for c in cs} vhold = (1,) gains["S_hold"] = {name(c): price(c, SHAPES["S"], hold=vhold) for c in cs} base = {k for k, (n, l) in gains["C"].items() if l < n} chained = {name(c) for c in cs if chain_gains(c)} print(f"\nGD gains over {len(cs)} cells, radices 3 to 40") for key, g in gains.items(): won = sorted((k for k, (n, l) in g.items() if l < n), key=lambda s: tuple(map(int, s[1:-1].split(",")))) out = [k for k in won if k not in base] far = [k for k in won if k not in chained] deep = [k for k in won if g[k][0] - g[k][1] > 1] print(f" {key:6s} {len(won):3d} gain, {len(out):3d} outside C's," f" {len(far):3d} outside every chain, {len(deep)} by 2") print(f" chains reach: " f"{' '.join(k for k in out if k in chained) or '-'}") print(f" {' '.join(won)}") print(f"\n{sum(CHECKS)}/{len(CHECKS)} checks passed, " f"{time.time() - t0:.1f} s") raise SystemExit(0 if all(CHECKS) else 1) if __name__ == "__main__": main()