anchors.py
To run it: save anchors.py, with flush.py, gaps.py, hull.py, induct.py, ostrowski.py, tie.py beside it; standard library only.
"""
anchors.py -- the ends of the window's bad offsets as integer keys, and
whether c_inf is read off the four keys nearest them.
QUESTION. gaps.py prints that one length test on the bad offsets B(t, f,
c) stops short of c_inf at 14 of 48 cells; where the keys of the hull
set H(c) (hull.py) fall is the next thing to read. Each end of a
component C = (a, b) of B is y(P) for one integer key P, its ANCHOR, and
the keys of H(c) in C are the STRIP points P_a + v, 0 < y(v) < l (an end
joining when it is bad), with Z in W = [Z_lo, Z_hi](t, f). Is c_inf the
least c at which no component's four-candidate set (each anchor when it
is a strip point, and each anchor's first return up and down in G) has a
key with Z in W?
DESIGN (frozen before the engine). y = H - G r_t, Z = G + kappa_t y. An
anchor is read off the field: x = y(G, H) gives G = -x.b / r.b, H = x.a
+ G r.a. A strip point: a valid key (G, H) with a <= y <= b and y bad (a
reply with no valid move, gaps.py's Bad), so an end joins only when it
is bad. The first return from an anchor in direction s = +-1: the least
|G'| with a strip point at G_anchor + G'. T4 hit at (t, f, c): a
candidate with Z in W, exact. c_T4 = the least c with the pinned moves
and no T4 hit (gaps.py's convention); T4's hits are strip points, so
c_T4 <= c_enum. PREDICTION: c_T4 = c_inf at all 48 cells. KILL: "c_T4 <
c_inf at n of 48 cells", n > 0. c_T4 > c_enum is an instrument fault,
printed apart. CONTROLS (read before the verdict): (a) every end of
every component read is y of an integer key, exactly: 0 failures; (b)
golden x2, c = 2, t 0 reduced, component (0.0557, 0.2918): candidates
(3, 2) and (11, 7), the hit (3, 2) (by hand); (c) every first return's
|G'| a convergent or intermediate denominator of r_t, 0 failures (KNOWN:
one-sided best approximations, Lagrange); (d) c_enum = c_inf at 48; (e)
THE PLANT, in the kill's direction: candidates the up returns only must
print c < c_inf at some cell, or the kill's power is unshown. SIDE
PRINTS (no kill): at c_inf - 1 which candidate hits; anchors whose Z is
exactly Z_lo or Z_hi.
FINDINGS (the --wide run, copied from its prints).
KILL MISSED. c_T4 < c_inf at 0 of 48 cells; c_T4 > c_enum at 0. It
reads at the 39 live cells; at the other 9 no c below c_inf has
the pinned moves and every test reads c_inf by construction. The
test is the cell's, not each component's: at c_inf - 1, 76 of the
184 components whose strip holds a key in W have all four
candidates outside W, both anchors' Z above Z_hi at 76 of the 76,
the nearer by 6.266 to 680.031 (silver x4, c 2, t 0 full: P_a
(111, 46) Z 111.008, W [-2.914, 19.899], strip keys (7, 3), (12,
5) in W). Components missing independently at that rate, 0.413,
would fail 4.39 of the 39 cells (1 to 13 such components a cell);
0 fail. The statistic is post hoc, fitted on the same cells, and
the components are not independent (one component can sit on
both flags): suggestive, not a law.
WHICH CANDIDATE. At c_inf - 1 the cells whose hits include a's first
return down: 33, b's down: 29, P_a itself: 3, P_b itself: 6; an up
return at none.
ANCHORS AT THE EDGES. 79 anchor occurrences, summed over every (t, f,
c) read and over the 48 cells, have Z exactly Z_hi; 0 have Z
exactly Z_lo.
CONTROLS. (a) 0 of 688 ends fail to be y of an integer key. (b) golden
x2, c = 2: candidates (3, 2), (11, 7), in W (3, 2), as by hand. (c)
0 of 1376 first returns off the convergent and intermediate
denominators (10 land on the other anchor). (d) c_enum = c_inf at
48 of 48. (e) up returns only: c < c_inf at 39 of 48 cells: the
kill can fire.
SECOND QUESTION, TOP (frozen after the first verdict, before its
engine). Z_hi(t, f) is an anchor's Z at 79 anchor occurrences. If P has
Z(P) = Z_hi, its down return w lands in W iff -G'(w) - kappa_t y(w) <= L
= Z_hi - Z_lo, the upper half G' + kappa_t y(w) <= 0 holding since 0 <
kappa_t < 1, |y(w)| < 1 and G' <= -1: a length statement at one anchor,
the first-return denominator against L. T_TOP hit at (t, f, c): an
anchor with Z exactly Z_hi that is a strip point in W, or whose first
return down is in W. c_top = the least c with the pinned moves and no
T_TOP hit; T_TOP's candidates are T4's, so c_top <= c_T4. LIVE cells:
some c < c_inf has the pinned moves (elsewhere every test reads c_inf by
construction). PREDICTION: c_top = c_inf at every live cell. KILL:
"c_top < c_inf at n of N live cells", n > 0. CONTROLS: (a) golden x2, c
= 2: P_b = (6, 4) has Z = Z_hi and its down return (3, 2) is in W (by
hand: G' = -3, kappa y(w) = -0.065, L = 4.236); (b) THE PLANT, in the
kill's direction: the top anchors themselves only, no returns, must
print c_top < c_inf at some live cell, or the kill's power is unshown.
SIDE PRINT: at c_inf - 1, the top hits' -G' - kappa y(w) against L.
TOP, KILL FIRED, mostly by construction. c_top < c_inf at 17 of 39
live cells, but at 14 of the 17 no anchor has Z exactly Z_hi at
c_top, so T_TOP has no candidate there; 35 live cells have an
anchor at Z_hi at some c read. The length statement at one anchor
is read and fails at 3 cells. Where a top anchor's down return
hits at c_inf - 1 (38 hits), L - (-G' - kappa y(w)) runs 0.000 (a
tie) to 362.066, -G' from 3 to 198. CONTROLS. (a) golden x2, c =
2: P_b (6, 4), its down return (3, 2), -G' - kappa y(w) = 3.0652,
L = 4.2361, as by hand. (b) the top anchors themselves only:
c_top < c_inf at 39 of 39 live cells, by construction wherever no
top anchor exists: its power is unshown.
RUN RECORD. Bare 1.0 s (KILL 0 of 24, the same shape); --wide 2.5 s,
peak commit 9.0 MB. With TOP's engine, after the first verdict: the
live-cell count and the component miss count (the 12 printed were the
cap of a longer list); after TOP's verdict, the chance line. The first
question's prints unchanged. TOP --wide 2.6 s, 9.9 MB. After both
verdicts, on an audit: the count of the TOP kill's cells with no anchor
at Z_hi, the live cells with one, and the missed components' anchors
above Z_hi; the verdicts' prints unchanged; the DESIGN's known result
named (Lagrange); in the frozen text, QUESTION's "an end joining when
it is bad", TOP's upper half and its "anchor occurrences".
Usage: python anchors.py [--wide] (--wide adds m = 6 .. 9)
"""
import math
import os
import sys
import time
os.environ.setdefault("OPENBLAS_NUM_THREADS", "1")
from flush import PERIODIC # noqa: E402
from induct import Field, Window, least, QF, le # noqa: E402
from hull import Coords, hull, hull_set # noqa: E402
from gaps import Bad, cmp # noqa: E402
WIDE = "--wide" in sys.argv
def anchor(F, t, x):
"""The integer key (G, H) with y = x, or None."""
r = F.r[t]
G = -x.b / r.b
H = x.a + G * r.a
if G.denominator != 1 or H.denominator != 1:
return None
G, H = int(G), int(H)
if cmp(QF(H) - r * G, x) != 0:
return None
return G, H
DENOMS = {}
def denoms(F, t, cap=10 ** 7):
"""Denominators of the convergents and intermediate fractions of r_t."""
key = (F.per, t)
if key in DENOMS:
return DENOMS[key]
out = {1}
q2, q1, k = 0, 1, 1
while q1 < cap:
a = F.a(t + k)
for j in range(a + 1):
out.add(q2 + j * q1)
q2, q1, k = q1, a * q1 + q2, k + 1
DENOMS[key] = out
return out
class Strip:
"""The strip points of one component at (t, f)."""
def __init__(self, win, B, t, f, comp):
self.win, self.B, self.t, self.f = win, B, t, f
self.a, self.b = comp
def at(self, G):
"""The strip point at G, or None."""
r = self.win.F.r[self.t]
base = r * G
for H in range(math.floor((self.a + base).f) - 1,
math.ceil((self.b + base).f) + 2):
if not self.win.ok(G, H, self.f, self.t):
continue
y = self.win.y(G, H, self.t)
if le(self.a, y) and le(y, self.b) and \
self.B.bad(y, self.t, self.f):
return (G, H)
return None
def ret(self, P, s, limit=200000):
"""The first return from anchor P in direction s: (G', key)."""
for n in range(1, limit):
k = self.at(P[0] + s * n)
if k is not None:
return s * n, k
raise RuntimeError("no return")
def main():
t0 = time.time()
maps = (2, 3, 4, 5) + ((6, 7, 8, 9) if WIDE else ())
kill = fault = cells = plant = 0
a_fail = a_ends = 0
c_fail = c_rets = 0
d_bad = 0
on_other = 0
ctrl_b = None
hit_kind = {}
at_edge = {}
diag = []
comp_true = comp_miss = 0
cell_n = []
live = top_kill = top_fault = tself = 0
top_empty = tops_live = miss_above = 0
miss_gap = []
top_need, ctrl_top = [], None
for name, per in PERIODIC:
F = Field(per)
p = F.p
for m in maps:
c_inf = least(F, m, "pin")
c_t4 = c_up = c_enum = c_top = c_tself = None
tops_at = {}
live_c = c_inf
for c in range(c_inf + 1):
win = Window(F, m, c)
st, miss = win.pin_starts()
if miss:
continue
co = Coords(F, m, c)
zhi, _ = hull(win, co, st)
zlo, _ = hull(win, co, st, low=True)
Hs = hull_set(win, co, zlo, zhi)
B = Bad(win)
any_in_B = any(B.bad(win.y(G, H, t), t, f)
for G, H, f, t in Hs)
if c_enum is None and not any_in_B:
c_enum = c
live_c = min(live_c, c)
ct0 = comp_true
hit = hit_up = hit_top = hit_top_self = False
has_top = False
kinds = set()
for t in range(p):
for f in (True, False):
z0, z1 = zlo[(t, f)], zhi[(t, f)]
for comp in B.components(t, f):
a_ends += 2
Pa = anchor(F, t, comp[0])
Pb = anchor(F, t, comp[1])
if Pa is None or Pb is None:
a_fail += 1
continue
S = Strip(win, B, t, f, comp)
cands = []
for nm, P in (("a", Pa), ("b", Pb)):
Zp = co.Z(P[0], P[1], t)
kind = ("lo" if cmp(Zp, z0) == 0 else
"hi" if cmp(Zp, z1) == 0 else None)
if kind:
at_edge[kind] = at_edge.get(kind, 0) + 1
has_top |= kind == "hi"
self_in = S.at(P[0]) == P
if self_in:
cands.append((nm, P, False))
if kind == "hi":
hit_top = hit_top_self = True
for s in (1, -1):
g, k = S.ret(P, s)
c_rets += 1
c_fail += abs(g) not in denoms(F, t)
other = Pb if nm == "a" else Pa
on_other += k == other
cands.append(
(nm + ("up" if s > 0 else "down"),
k, s > 0))
if kind == "hi" and s < 0:
w = (k[0] - P[0], k[1] - P[1])
need = (QF(-w[0]) - co.kap[t] *
win.y(w[0], w[1], t))
L = z1 - z0
if le(need, L):
hit_top = True
if c == c_inf - 1:
top_need.append(
(need.f, L.f, -w[0]))
if (name.startswith("golden") and
m == 2 and c == 2 and
t == 0 and not f):
ctrl_top = (P, k, need.f, L.f)
ins = [(nm, k, up) for nm, k, up in cands
if le(z0, co.Z(k[0], k[1], t)) and
le(co.Z(k[0], k[1], t), z1)]
hit |= bool(ins)
hit_up |= any(up for _, _, up in ins)
kinds |= {nm for nm, _, _ in ins}
if (name.startswith("golden") and m == 2 and
c == 2 and t == 0 and not f):
ctrl_b = (sorted({k for _, k, _ in cands}),
sorted({k for _, k, _ in ins}))
if c == c_inf - 1 and any_in_B:
tru = [k for k in Hs if k[2] == f and
k[3] == t and
le(comp[0], win.y(k[0], k[1], t)) and
le(win.y(k[0], k[1], t), comp[1]) and
B.bad(win.y(k[0], k[1], t), t, f)]
comp_true += bool(tru)
comp_miss += bool(tru) and not ins
if tru and not ins:
za = co.Z(Pa[0], Pa[1], t)
zb = co.Z(Pb[0], Pb[1], t)
up2 = ((za - z1).sign() > 0 and
(zb - z1).sign() > 0)
miss_above += up2
if up2:
miss_gap.append(
min(za.f, zb.f) - z1.f)
if tru and not ins and len(diag) < 12:
diag.append(
f"{name} x{m} c {c} t {t} "
f"{'F' if f else 'R'}: comp "
f"({comp[0].f:.4f}, {comp[1].f:.4f})"
f" P_a {Pa} Z "
f"{co.Z(Pa[0], Pa[1], t).f:.3f}, P_b "
f"{Pb} Z {co.Z(Pb[0], Pb[1], t).f:.3f}"
f"; W [{z0.f:.3f}, {z1.f:.3f}]; "
f"strip keys in W "
f"{[k[:2] for k in sorted(tru)][:4]}")
if c == c_inf - 1:
cell_n.append(comp_true - ct0)
for k in kinds:
hit_kind[k] = hit_kind.get(k, 0) + 1
tops_at[c] = has_top
if c_t4 is None and not hit:
c_t4 = c
if c_up is None and not hit_up:
c_up = c
if c_top is None and not hit_top:
c_top = c
if c_tself is None and not hit_top_self:
c_tself = c
cells += 1
is_live = live_c < c_inf
live += is_live
d_bad += c_enum != c_inf
if c_t4 is None or c_enum is None or c_t4 > c_enum:
fault += 1
elif c_t4 < c_inf:
kill += 1
plant += c_up is not None and c_up < c_inf
top_fault += c_top is None or c_top > c_t4
top_kill += is_live and c_top is not None and c_top < c_inf
if is_live and c_top is not None and c_top < c_inf:
top_empty += not tops_at[c_top]
tops_live += is_live and any(tops_at.values())
tself += is_live and c_tself is not None and c_tself < c_inf
print(f" {name:20s} x{m} c_inf {c_inf} c_T4 {c_t4} "
f"(up only {c_up}) c_enum {c_enum} c_top {c_top} "
f"(self only {c_tself}) live {is_live}", flush=True)
print("== ANCHORS: c_inf from the four keys nearest B's ends")
print(f" (a) ends not y of an integer key: {a_fail} of {a_ends}")
print(f" (b) golden x2, c = 2, t 0 reduced: candidates "
f"{ctrl_b[0] if ctrl_b else None}, in W "
f"{ctrl_b[1] if ctrl_b else None}")
print(f" (c) first returns whose |G'| is no convergent or intermediate "
f"denominator: {c_fail} of {c_rets} (landing on the other "
f"anchor: {on_other})")
print(f" (d) c_enum != c_inf at {d_bad} of {cells}")
print(f" (e) THE PLANT (up returns only): c < c_inf at {plant} of "
f"{cells} cells")
print(f" at c_inf - 1, cells whose hits include each candidate: "
f"{dict(sorted(hit_kind.items()))}")
print(f" anchors with Z exactly Z_lo / Z_hi (every c read): "
f"{at_edge.get('lo', 0)} / {at_edge.get('hi', 0)}")
print(f" at c_inf - 1, components with a strip key in W: {comp_true}, "
f"their four candidates all outside W: {comp_miss}; of these, "
f"both anchors' Z above Z_hi: {miss_above}, the nearer by "
f"{min(miss_gap):.3f} to {max(miss_gap):.3f}")
rho = comp_miss / comp_true
exp = sum(rho ** n for n in cell_n)
print(f" the cell's test against chance: components missing "
f"independently at {rho:.3f} would fail {exp:.2f}"
f" of {len(cell_n)} cells read at c_inf - 1 (their components with "
f"a strip key in W: {min(cell_n)} to {max(cell_n)})")
for x in diag:
print(" T4 miss: " + x)
print(f" c_T4 > c_enum (instrument fault): {fault} cells")
print(f" live cells (some c < c_inf has the pinned moves): {live} of "
f"{cells}")
print(f" KILL: c_T4 < c_inf at {kill} of {cells} cells")
print("== TOP: the anchors at Z_hi alone")
print(f" (a) golden x2, c = 2, t 0 reduced: top anchor, its down "
f"return, -G' - kappa y(w), L: {ctrl_top}")
print(f" (b) THE PLANT (top anchors themselves only): c_top < c_inf at "
f"{tself} of {live} live cells")
if top_need:
sl = sorted(L - nd for nd, L, _ in top_need)
print(f" at c_inf - 1, top hits by a down return: {len(top_need)}, "
f"L - (-G' - kappa y(w)) from {sl[0]:.3f} to {sl[-1]:.3f}, "
f"G' in {sorted({g for _, _, g in top_need})}")
print(f" c_top > c_T4 or unset (instrument fault): {top_fault} cells")
print(f" of the kill's cells, no anchor at Z_hi at c_top (fired by "
f"construction): {top_empty}; live cells with an anchor at Z_hi "
f"at some c read: {tops_live}")
print(f" KILL: c_top < c_inf at {top_kill} of {live} live cells")
print(f" {time.time() - t0:.1f} s")
if __name__ == "__main__":
main()