evenbit.py

"""evenbit.py -- the element machine without multiply answers every
newest modulus M = 2^t in 4t + 2 unit ops whatever the deep moduli are,
by keeping [C' even] in its finite control.

QUESTION. coprime.py's machine: registers over windows, add, sub, copy,
clear, GROW naming its register, a zero-test per register, no multiply,
no nonzero constant. A fixed program reads, after each grow, whether the
newest modulus M is coprime to the deep moduli (C' their lcm, B their
largest). coprime.py's Reader waits O(B(B + M)), touching every d <= B.
Must any correct reader's wait grow with B (a floor in B alone)? And
does the deep side set a floor near log2 of the part of C' coprime to M
when every deep window holds one integer?

THE CONSTRUCTION (written before the engine). The PARITY READER is
coprime.py's Reader with one finite-control bit EVEN = [C' even] and a
lockstep before its d loop. After the grow and ONES := ONES + F:
  D := F, S := 0; then per step j = 1, 2, ...:
    D := D + D; if zero(D): answer [not EVEN], stop the trip;
    S := S + F; if zero(S): leave the lockstep, run the plain d loop.
  F, D and S are 0 on every deep window, and on the newest D = 2^j,
  S = j (mod M). So zero(D) at step j iff M | 2^j, iff M = 2^t and
  j >= t; zero(S) at step j iff M | j. D is tested first, so for
  M = 2^t (t < M at every M >= 2) the lockstep stops at j = t, and at
  any other M at j = M with D never zero. Then gcd(2^t, C') = 1 iff C'
  is odd, so [not EVEN] is the answer. The bit: M is even in the power
  branch, and in the other branch M's parity is j's at exit, a toggle
  per step; after the answer EVEN := EVEN or [M even], which makes it
  [C' even] for the next trip, whose deep moduli are these and M. A
  change from the first plan, named: the plan read M's parity in the
  upkeep while it measures M; reading it in the lockstep costs no op and
  leaves coprime.py's upkeep untouched. The upkeep runs after either
  branch as coprime.py's (it needs F, ONES, DEEP, BC only).
THE COUNT (by hand, read off the construction).
  Power branch, M = 2^t: grow 1, ONES 1, D and S 2, t - 1 full steps of
  4, the last step's add and test 2:  wait = 4t + 2.
  full = 1 + wait + upkeep = 4t + 3 + 3M + 3B + 5 max(B, M).
  Other M: the lockstep 2 + 4M, then the plain reader's ops after its
  grow and ONES:  wait = coprime.counted(B, M)[0] + 4M + 2, and
  full = coprime.counted(B, M)[1] + 4M + 2.
  Registers: coprime.py's 14 and D, 15.
THE DEEP SIDE. In the power branch every register the wait touches
(DEEP, F, ONES, D, S) holds 0 or 1 on every deep window, and the wait
4t + 2 does not see C'. On odd deep moduli 3 .. B the part of C' coprime to 2^t is
C' itself, lcm of the odd numbers to B, log2 47.25 at B = 39, against
a wait of 6 at M = 2.

PREDICTIONS (frozen before the engine).
  P1 the parity reader's answer equals [gcd(M, C') = 1] at every trip of
     coprime.py's three runs: m_g = g + 1 and the primes, g = 1 .. 30,
     and section_random's 40 draws (seed 1668, moduli 2 .. 40, g = 1 ..
     25).
  P2 THE SWEEP. Deep moduli E_B = 2 .. B (C' even) and O_B = the odd
     numbers 3 .. B (C' odd), B in {3, 5, 9, 17, 33, 39}, then M = 2^t,
     t = 1 .. 10: the wait is 4t + 2 in every cell, the same at every B;
     the answer is False on E_B and True on O_B. Beside it, the plain
     reader's wait on the same cells, which grows with B (a print).
  P3 at every trip of P1 the wait and the full cycle equal THE COUNT's
     closed forms, power branch or not; 15 registers.
  P4 (a print) at every sweep cell the wait is at least the proved
     floor 2 + ceil(log2 M) = t + 2; log2 C' printed per B, and at t = 1
     (wait 6) on O_B the wait sits below log2 C' from B = 9 on (log2 C'
     by hand: 1.58, 3.91, 8.30, 19.55, 42.04, 47.25).
CONTROLS, read before any verdict.
  C1 coprime.py's Reader on section_random's draws: every answer the
     gcd's and every wait and full cycle coprime.counted's, the engine
     and the count convention this script leans on.
  C2 the sweep's supplies through the plain Reader: answers False on
     E_B, True on O_B at every t.
PLANT, must break P1: (a) EVEN frozen at False (never set): on m_g = g
  + 1 at g = 2 (M = 4, deep 2, 3) it answers True where the gcd says
  False. (b) the D test removed: the answers stay right and P2's wait
  breaks at every cell (a plant on the wait check).
KILL (frozen). Printed: per t, the parity waits across the twelve deep
  supplies. Fires if any answer of P1 or P2 differs from the gcd, if at
  any t the twelve waits are not all 4t + 2, or if plant (a) breaks no
  answer or plant (b) leaves any P2 wait at 4t + 2.

FINDINGS (entered after the run, from its printed output).
  C1 coprime.Reader on the draws: 1000 trips, 0 answers off, 0 counts
     off. C2 the sweep through it: 0 off of 120.
  P1 1060 trips, 134 through the power branch, 0 answers off.
  P3 every wait and full cycle is THE COUNT's, 0 off; 15 registers.
  P2 0 sweep answers off; at every t = 1 .. 10 the twelve waits are all
     4t + 2 (6, 10, ..., 42). The plain reader on the same cells: at
     t = 1, 54, 93, 189, 453, 1269, 1674 for B = 3 .. 39 (E and O the
     same, counted(B, M) seeing only B and M); at t = 10, 7719 to 83193.
  P4 no wait below t + 2; log2 C' on O_B 1.58, 3.91, 8.30, 19.55, 42.04,
     47.25, so the wait 6 at t = 1 is below it at B = 9, 17, 33, 39.
  B  (a) EVEN frozen: 131 answers off, first (g + 1, g = 2, M = 4),
     (g + 1, 6, 8), (g + 1, 14, 16). (b) the D test removed: 0 sweep waits at
     4t + 2, 0 answers off.
  K  KILL MISSES.
READING. A floor in B alone is false: at M = 2 the wait is 6 at every
B. The front's last clause owes a hypothesis: the wait tests only D and
S, 0 on every deep window (registers the wait does not touch keep
earlier trips' residues there), and at t = 1 it sits below log2 C', the
part coprime to M, at B = 9, 17, 33, 39 of the grid; the
bit that answers was carried in the finite control from earlier trips,
so a floor of that shape owes a hypothesis on what the control keeps.

RUN RECORD. 12 checks, 14.1 s, peak commit 6.9 MB under a memory cap.
"""

import os
import random
import sys
from math import log2

sys.path.insert(0, os.path.dirname(os.path.abspath(__file__)))
import coprime  # noqa: E402
from coprime import Reader, truth, counted, lcm_all  # noqa: E402
from supply import PRIMES, check, section, CHECKS  # noqa: E402

REGS = coprime.REGS | {"D"}
BS = (3, 5, 9, 17, 33, 39)
TS = range(1, 11)


class Parity(Reader):
    """coprime.py's Reader with EVEN = [C' even] in finite control and
    the doubling lockstep before its d loop."""

    def __init__(self, supply, plant=None):
        super().__init__(supply)
        self.even = False
        self.pplant = plant
        self.branch = None

    def trip(self):
        E = self.E
        begin = E.units
        E.copy("DEEP", "ONES")
        start = E.units
        E.grow("F")
        E.add("ONES", "ONES", "F")
        E.copy("D", "F")
        E.clear("S")
        odd_steps = False                  # finite control: j mod 2
        while True:
            E.add("D", "D", "D")
            if self.pplant != "b" and E.zero("D"):
                answer = not self.even
                wait = E.units - start
                if self.pplant != "a":
                    self.even = True       # M = 2^t is even
                self.branch = "pow"
                self.upkeep()
                return answer, wait, E.units - begin
            E.add("S", "S", "F")
            odd_steps = not odd_steps
            if E.zero("S"):
                break
        if self.pplant != "a" and not odd_steps:   # M = j, j even
            self.even = True
        self.branch = "plain"
        answer = self.plain_loop()
        wait = E.units - start
        self.upkeep()
        return answer, wait, E.units - begin

    def plain_loop(self):
        """coprime.py's Reader.trip after its grow and ONES, its plant
        branches cut."""
        E = self.E
        E.copy("X", "DEEP")
        E.clear("DC")
        E.copy("W", "F")
        stop = "BC"
        while True:
            E.clear("V")
            E.clear("S")
            while True:
                E.add("V", "V", "W")
                E.add("S", "S", "F")
                if E.zero("V"):
                    break
            if E.zero("S"):
                E.copy("Y", "X")
                E.copy("TC", "DC")
                while not E.zero("TC"):
                    E.add("Y", "Y", "X")
                    E.sub("TC", "TC", "DEEP")
                E.copy("X", "Y")
            E.sub("T", "DC", stop)
            if E.zero("T"):
                break
            E.add("DC", "DC", "DEEP")
            E.add("W", "W", "F")
        return E.zero("X")


def power(M):
    """t if M = 2^t, t >= 1, else None."""
    t = M.bit_length() - 1
    return t if M >= 2 and M == 1 << t else None


def predicted(B, M):
    """THE COUNT: (wait, full) of the parity reader."""
    t = power(M)
    if t is not None:
        w = 4 * t + 2
        return w, 1 + w + 3 * M + 3 * B + 5 * max(B, M)
    w, f = counted(B, M)
    return w + 4 * M + 2, f + 4 * M + 2


def run(cls, ms, plant=None):
    """Every trip on the supply ms (a tail of 2s past it, never grown):
    (g, prefix, answer, wait, full, branch) for g = 1 .. len(ms) - 1."""
    sup = (lambda i: ms[i] if i < len(ms) else 2)
    R = cls(sup, plant) if plant else cls(sup)
    R.trip()
    out = []
    for g in range(1, len(ms)):
        ans, wait, full = R.trip()
        out.append((g, ms[:g + 1], ans, wait, full,
                    getattr(R, "branch", None)))
    return out, R.E.names


def draws():
    """coprime.py::section_random's 40 draws, the same generator."""
    rng = random.Random(1668)
    return [[rng.randint(2, 40) for _ in range(26)] for _ in range(40)]


def p1_supplies():
    return ([("g + 1", [g + 2 for g in range(31)]),
             ("primes", [PRIMES[g] for g in range(31)])]
            + [(f"draw {i}", ms) for i, ms in enumerate(draws())])


def deep(kind, B):
    return list(range(2, B + 1)) if kind == "E" else list(range(3, B + 1, 2))


def section_controls():
    section("C  controls: the plain reader on the draws and the sweep")
    off = miss = n = 0
    for ms in draws():
        out, _ = run(Reader, ms)
        for g, mm, ans, wait, full, _ in out:
            M, B = mm[-1], max(mm[:-1])
            off += ans != truth(mm)
            miss += (wait, full) != counted(B, M)
            n += 1
    check("C1 coprime.Reader on the draws: answers the gcd's, waits and "
          "full cycles coprime.counted's", off == 0 and miss == 0,
          f"{n} trips, {off} answers off, {miss} counts off")
    bad = 0
    for kind in "EO":
        for B in BS:
            for t in TS:
                out, _ = run(Reader, deep(kind, B) + [2 ** t])
                bad += out[-1][2] != (kind == "O")
    check("C2 the sweep through the plain reader: False on E_B, True on "
          "O_B", bad == 0, f"{bad} off of {2 * len(BS) * len(TS)}")


def p1(plant=None):
    off = miss = n = npow = 0
    first = []
    names = set()
    for name, ms in p1_supplies():
        out, nm = run(Parity, ms, plant)
        names |= nm
        for g, mm, ans, wait, full, br in out:
            M, B = mm[-1], max(mm[:-1])
            if ans != truth(mm):
                off += 1
                if len(first) < 3:
                    first.append((name, g, M))
            miss += (wait, full) != predicted(B, M)
            npow += br == "pow"
            n += 1
    return off, miss, n, npow, first, names


def section_answers():
    section("P1, P3  the parity reader on coprime.py's three runs")
    off, miss, n, npow, first, names = p1()
    print(f"  {n} trips, {npow} through the power branch")
    check("P1 every answer is the gcd's", off == 0, f"{off} off {first}")
    check("P3 every wait and full cycle is THE COUNT's", miss == 0,
          f"{miss} off")
    check("P3 the 15 registers", names == REGS,
          f"{len(names)} used: {sorted(names - REGS)} extra, "
          f"{sorted(REGS - names)} missing")
    return off


def sweep(plant=None):
    """{(kind, B, t): (answer, parity wait, plain wait)}."""
    cells = {}
    for kind in "EO":
        for B in BS:
            for t in TS:
                ms = deep(kind, B) + [2 ** t]
                pout, _ = run(Parity, ms, plant)
                cout, _ = run(Reader, ms)
                cells[kind, B, t] = (pout[-1][2], pout[-1][3], cout[-1][3])
    return cells


COLS = [(k, B) for k in "EO" for B in BS]


def section_sweep():
    section("P2, P4  the sweep: deep E_B = 2..B, O_B = odd 3..B; M = 2^t")
    cells = sweep()
    print("  parity wait by t (columns E_3 .. E_39, then O_3 .. O_39):")
    for t in TS:
        print(f"  t={t:>2} 4t+2={4 * t + 2:>3}  " + " ".join(
            f"{cells[k, B, t][1]:>3}" for k, B in COLS))
    print("  the plain reader's wait on the same cells, t = 1 and t = 10:")
    for t in (1, 10):
        print(f"  t={t:>2}  " + " ".join(
            f"{cells[k, B, t][2]:>6}" for k, B in COLS))
    print("  log2 C' on O_B: " + ", ".join(
        f"B={B} {log2(lcm_all(deep('O', B))):.2f}" for B in BS))
    ans_off = sum(cells[k, B, t][0] != (k == "O") for k, B in COLS
                  for t in TS)
    flat = [t for t in TS
            if {cells[k, B, t][1] for k, B in COLS} != {4 * t + 2}]
    under = sum(cells[k, B, t][1] < t + 2 for k, B in COLS for t in TS)
    below = [B for B in BS if cells["O", B, 1][1] < log2(lcm_all(deep("O", B)))]
    check("P2 every sweep answer: False on E_B, True on O_B", ans_off == 0,
          f"{ans_off} off")
    check("P2 at every t the twelve waits are all 4t + 2", flat == [],
          f"t off: {flat}")
    check("P4 every wait >= 2 + ceil(log2 M) = t + 2", under == 0,
          f"{under} under")
    check("P4 at t = 1 the wait is below log2 C' on O_B from B = 9 on",
          below == [9, 17, 33, 39], f"below at {below}")
    return ans_off, flat


def section_plants():
    section("B  plants")
    off, _, _, _, first, _ = p1("a")
    print(f"  (a) EVEN frozen at False: {off} answers off, first {first}")
    check("Ba the frozen bit breaks P1", off > 0, f"{off} off")
    cells = sweep("b")
    held = sum(cells[k, B, t][1] == 4 * t + 2 for k, B in COLS for t in TS)
    aoff = sum(cells[k, B, t][0] != (k == "O") for k, B in COLS for t in TS)
    print(f"  (b) the D test removed: {held} sweep waits still 4t + 2, "
          f"{aoff} answers off")
    check("Bb the removed test breaks every P2 wait", held == 0,
          f"{held} held")
    return off, held


def main():
    section_controls()
    if not all(CHECKS):
        print("\ncontrols fail: no verdict")
        return 1
    p1_off = section_answers()
    ans_off, flat = section_sweep()
    a_off, held = section_plants()
    fired = p1_off > 0 or ans_off > 0 or flat != [] or a_off == 0 \
        or held > 0
    print(f"\n  KILL {'FIRES' if fired else 'MISSES'}")
    check("K the kill misses", not fired)
    print(f"\n{sum(CHECKS)}/{len(CHECKS)} checks pass")
    return 0 if all(CHECKS) else 1


if __name__ == "__main__":
    sys.exit(main())