"""coprime_mul.py -- the element machine with multiply reads whether its newest modulus is coprime to the earlier ones in O(B + M) unit ops. QUESTION. supply.py's Machine with a multiply, window by window, GROW naming its register, a zero-test per register, no constant written. After the grow of the newest window, modulus M, a fixed program reads whether M is coprime to every deep modulus, C' their lcm and B their largest. coprime.py's reader, with no multiply, waits O(B(B + M)): a BM term from unit tests on the newest window and a B^2 term from multiplying by a count. With multiply, is the wait O(B + M), what is its floor, and what would a reader below M hand over? THE ARGUMENT (written before the engine). (1) THE READER. Measure M - 1 aligned on every window (S := F counted up on the newest window until it is 0, MC := MC + ONES in lockstep), X := MC + ONES, which is M at every window and 0 on the newest. P := X, N := DEEP, then B - 1 rounds of N := N (P - ONES), P := P X, counted down from BC = B - 1 aligned on the deep windows. Every deep window then holds N = prod_{i=1}^{B-1} (M^i - 1) and the newest holds 0, so zero(N) reads the deep windows alone. A deep m >= 2 coprime to M has ord_m(M) <= lambda(m) <= m - 1 <= B - 1, so one factor is 0 mod m; m = 1 divides every N, and B = 1 runs no round, N = DEEP = 0 there; a prime p dividing M and m makes every factor -1 mod p. So zero(N) iff gcd(M, C') = 1, on every supply (supply.py's moduli >= 2, and on moduli 1, outside that object, where the grow writes 0). (2) THE COUNT, read off the code. Grow and ONES 2; the measurement 3M (two setup ops, M tests, M - 1 rounds of two adds); X 1; P and N 2; TC 1; the rounds 5(B - 1) + 1; the read 1: wait = 3M + 5B + 3. The upkeep is coprime.py's less its measurement, which MC already holds: B - 1 realigned onto the newest window 3B - 1, the climb of K to max(B, M) - 1 with its clear 5 max(B, M), the copy back 1. With the copy of DEEP before the grow, full = 3M + 8B + 5 max(B, M) + 4 <= 13(B + M) + 4. (3) THE FLOOR. c* = max(2, |constants|), 2 here. After the grow every newest integer is 0 or 1 and one value op raises the largest |x| from a to at most max(c*, 2a, a^2), so after s value ops |x| <= c*^(2^(s - 1)). coprime.py's companion supplies (M and M' > M, the other answer) run alike while every newest integer is below M in size, so a reader correct on every supply reads at op t >= 3 + max(0, ceil(log2 log_{c*} M)), M > 1, wherever C' > 1 (at C' = 1 zero(DEEP) answers at op 2). (4) THE REDUCTION. Deep supply (2), newest M in {p, 2p}, p an odd prime. G, the run that answers false every test of a deep-zero register whose newest integer is nonzero, is one straight-line sequence x_1, x_2, ... from {0, 1}; the run on M follows G until the first test of a deep-zero register whose newest x_i has M | x_i != 0. The runs on p and 2p answer differently, so by the read some nonzero x_i is divisible by p. So the nonzero x_i up to T, the largest wait over M <= 2N, multiply to a nonzero multiple of every odd prime up to N; doubled, of N#; squared ceil(log2 N) times, of N!, since N! divides (N#)^N (Cheng, Theoret. Comput. Sci. 326 (2004), Lemma 1). So tau'(N!) <= 2T + ceil(log2 N) + O(1), tau' the least straight-line cost of a nonzero multiple (the ultimate complexity). G is Shub and Smale's canonical path (Duke Math. J. 81 (1995), section 4) read on this machine. PREDICTIONS (frozen before the engine). C1 coprime.py's Reader on this engine gives coprime.counted's wait and full at every trip, g = 1 .. 12 on g + 1 and on the primes. C2 multiply equals the per-window product mod m on 200 random pairs. P1 the answer equals [gcd(M, C') = 1] at g = 1 .. 30 on g + 1 and on the primes, and on 40 random supplies, moduli 1 .. 40 in any order, g = 1 .. 25. P2 wait = 3M + 5B + 3 and full = 3M + 8B + 5 max(B, M) + 4 at every trip of P1. P3 at g = 30 full is 508 on g + 1 (M = 32, B = 31), against coprime.py's 3401, and 1924 on the primes (M = 127, B = 113), against 64640. P4 wait >= 3 + ceil(log2 log2 M) at every trip with M > 1. P5 for every odd prime p <= 50, supplies (2, p) and (2, 2p) first differ at a zero-test whose newest integer is an odd multiple of p: the S test at S = p, the p-th test after the grow. R the registers ONES DEEP F MC S X P N T TC BC K, 12. Planted breaks, each must miss P1: (a) J = B - 2 rounds; (b) N := ONES in place of DEEP. KILL (frozen). Printed per trip: the answer against the gcd, the wait and full against P2's closed forms, over g + 1, the primes and the random supplies. Fires if any answer differs or any count is off its closed form; C1 and C2 read first, a red control voids the run. FINDINGS (entered after the run, from its printed output). C both controls green: coprime.py's reader counts as coprime.counted at g = 1..12 on both supplies (0 off); multiply equals the per-window product on 200 pairs (0 off). P1 every answer is the gcd's: 30 of 30 on g + 1, 30 of 30 on the primes, 1000 random trips (194 coprime, 806 not; M = 1 at 41, B = 1 at 1), 0 off. P2 wait and full equal the closed forms at every trip, 0 off. P3 at g = 30 full 508 against 3401 without multiply on g + 1, 1924 against 64640 on the primes, as predicted. P4 the wait clears 3 + ceil(log2 log2 M) at every trip on g + 1 and the primes (P4 runs on those two alone): 22 against 4 at g = 1, 949 against 6 at g = 30 on the primes. P5 for every odd prime p <= 47 the runs on (2, p) and (2, 2p) first differ at the S test number p, S's newest integer p. B both plants miss: (a) 6 wrong answers by g = 12, (b) 17. K KILL MISSES: 0 answers off, 0 counts off. R 12 registers, the list's. The random trips reach modulus 1, the zero ring, where the grow writes 0; supply.py's own supplies never reach it. RUN RECORD. 16 checks, 0.6 s. """ import os import random import sys from math import ceil, gcd, log2 sys.path.insert(0, os.path.dirname(os.path.abspath(__file__))) from supply import PRIMES, check, section, CHECKS # noqa: E402 import coprime # noqa: E402 from coprime import Counted, truth, lcm_all # noqa: E402 REGS = {"ONES", "DEEP", "F", "MC", "S", "X", "P", "N", "T", "TC", "BC", "K"} class Mul(Counted): """coprime.py's counted engine with a multiply, one unit an op. With `shadow` it keeps the true integer of every register on the newest window, which the reduction's check reads.""" def __init__(self, supply, shadow=False): super().__init__(supply) self.shadow = {} if shadow else None self.tests = [] def grow(self, into): super().grow(into) if self.shadow is not None: self.shadow = {into: 1} self.tests = [] def _z(self, r): return self.shadow.get(r, 0) def op(self, d, a, b, sign): if self.shadow is not None: self.shadow[d] = self._z(a) + sign * self._z(b) super().op(d, a, b, sign) def mul(self, d, a, b): self.units += 1 self.names.update((d, a, b)) if self.shadow is not None: self.shadow[d] = self._z(a) * self._z(b) A, Bb, out = self.reg(a), self.reg(b), {} for w in set(A) & set(Bb): x = A[w] * Bb[w] % self.m[w] if x: out[w] = x self.R[d] = out def copy(self, d, a): if self.shadow is not None: self.shadow[d] = self._z(a) super().copy(d, a) def clear(self, d): if self.shadow is not None: self.shadow[d] = 0 super().clear(d) def zero(self, r): ans = super().zero(r) if self.shadow is not None: self.tests.append((r, self._z(r), ans)) return ans class Reader: """The fixed program with multiply: one trip per grow.""" def __init__(self, supply, plant=None, shadow=False): self.E = Mul(supply, shadow) self.plant = plant 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.clear("MC") E.copy("S", "F") while not E.zero("S"): E.add("MC", "MC", "ONES") E.add("S", "S", "F") E.add("X", "MC", "ONES") E.copy("P", "X") E.copy("N", "ONES" if self.plant == "b" else "DEEP") if self.plant == "a": E.sub("TC", "BC", "DEEP") else: E.copy("TC", "BC") while not E.zero("TC"): E.sub("T", "P", "ONES") E.mul("N", "N", "T") E.mul("P", "P", "X") E.sub("TC", "TC", "DEEP") answer = E.zero("N") wait = E.units - start self.upkeep() return answer, wait, E.units - begin def upkeep(self): E = self.E E.copy("TC", "BC") while not E.zero("TC"): E.sub("TC", "TC", "DEEP") E.add("BC", "BC", "F") E.clear("K") seen_b = seen_m = False while True: E.sub("T", "K", "BC") seen_b |= E.zero("T") E.sub("T", "K", "MC") seen_m |= E.zero("T") if seen_b and seen_m: break E.add("K", "K", "ONES") E.copy("BC", "K") def counted(B, M): """The argument's (2): the wait and the full cycle in closed form.""" wait = 3 * M + 5 * B + 3 return wait, 1 + wait + 3 * B + 5 * max(B, M) def floor_mul(M): """The argument's (3) at c* = 2: 3 + ceil(log2 log2 M), M > 1.""" return 3 + max(0, ceil(log2(log2(M)))) if M > 2 else 3 SUPPLIES = coprime.SUPPLIES def run_supply(sup, top, plant=None): R = Reader(sup, plant) R.trip() out = [] for g in range(1, top + 1): ans, wait, full = R.trip() out.append((g, [sup(i) for i in range(g + 1)], ans, wait, full)) return out, R.E.names def section_control(): section("C controls: the old reader on this engine; multiply") for name, sup in SUPPLIES: R = coprime.Reader(sup) R.E = Mul(sup) R.trip() off = 0 for g in range(1, 13): _, wait, full = R.trip() ms = [sup(i) for i in range(g + 1)] off += (wait, full) != coprime.counted(max(ms[:-1]), ms[-1]) check(f"C1 {name}: coprime.py's reader counts as coprime.counted, " "g = 1..12", off == 0, f"{off} off") rng = random.Random(1670) ms = [rng.randint(1, 40) for _ in range(12)] E = Mul(lambda i: ms[i]) for _ in ms: E.grow("F") off = 0 for _ in range(200): a = {w: rng.randrange(ms[w]) for w in range(12) if rng.random() < .8} b = {w: rng.randrange(ms[w]) for w in range(12) if rng.random() < .8} E.R["A"] = {w: x for w, x in a.items() if x} E.R["B"] = {w: x for w, x in b.items() if x} E.mul("C", "A", "B") want = {w: a.get(w, 0) * b.get(w, 0) % ms[w] for w in range(12)} off += {w: x for w, x in want.items() if x} != E.R["C"] check("C2 multiply = the per-window product mod m, 200 pairs", off == 0, f"{off} off") return off == 0 def section_reader(): section("E the multiply reader: answers, waits, the full cycle") off = miss = under = 0 for name, sup in SUPPLIES: out, names = run_supply(sup, 30) print(f" {name}: registers {len(names)} {sorted(names)}") print(f" {'g':>3} {'M':>4} {'B':>4} {'ans':>4} {'wait':>5} " f"{'full':>5} {'floor':>5} {'no-mul full':>11}") o = m = u = 0 for g, ms, ans, wait, full in out: M, B = ms[-1], max(ms[:-1]) old = coprime.counted(B, M)[1] o += ans != truth(ms) m += (wait, full) != counted(B, M) u += M > 1 and wait < floor_mul(M) if g <= 5 or g % 5 == 0: print(f" {g:>3} {M:>4} {B:>4} {str(ans)[0]:>4} {wait:>5} " f"{full:>5} {floor_mul(M):>5} {old:>11}") off, miss, under = off + o, miss + m, under + u check(f"P1 {name}: every answer is the gcd's, g = 1..30", o == 0, f"{o} off") check(f"P2 {name}: wait and full = the closed forms", m == 0, f"{m} off") check(f"P4 {name}: wait >= 3 + ceil(log2 log2 M)", u == 0, f"{u} under") check(f"R {name}: the frozen {len(REGS)} registers", names == REGS, f"{len(names)} used") g, ms, _, _, full = out[-1] print(f" P3 {name} at g = 30: full {full} against " f"{coprime.counted(max(ms[:-1]), ms[-1])[1]} without " "multiply") return off, miss def section_random(): section("P1 40 random supplies, moduli 1..40 in any order, g = 1..25") rng = random.Random(1670) off = miss = n = ones_m = ones_b = 0 both = [0, 0] for _ in range(40): ms = [rng.randint(1, 40) for _ in range(26)] out, _ = run_supply(lambda i, ms=ms: ms[i], 25) 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) both[truth(mm)] += 1 ones_m += M == 1 ones_b += B == 1 n += 1 print(f" {n} trips, {both[1]} coprime, {both[0]} not; M = 1 at " f"{ones_m}, B = 1 at {ones_b}") check("P1 random: every answer is the gcd's", off == 0, f"{off} off") check("P2 random: wait and full = the closed forms", miss == 0, f"{miss} off") return off, miss def section_reduction(): section("P5 the reduction's lemma: (2, p) against (2, 2p)") rows, bad = [], 0 for p in [q for q in PRIMES if 2 < q <= 50]: runs = [] for M in (p, 2 * p): R = Reader(lambda i, M=M: (2, M)[i], shadow=True) R.trip() R.E.shadow = {} R.E.tests = [] R.trip() runs.append(R.E.tests) i = next(j for j, (a, b) in enumerate(zip(*runs)) if a != b) r, x, _ = runs[0][i] ok = x != 0 and x % p == 0 and x % 2 == 1 and runs[1][i][1] == x bad += not ok rows.append(f"{p}:{r}@{i + 1}={x}") print(" p: register@test = newest integer " + " ".join(rows)) check("P5 first difference at an odd multiple of p, p <= 50", bad == 0, f"{bad} off") def section_plants(): section("B planted breaks must miss P1") for plant, what in (("a", "J = B - 2 rounds"), ("b", "N := ONES in place of DEEP")): wrong = [] for name, sup in SUPPLIES: out, _ = run_supply(sup, 12, plant) wrong += [(name, g) for g, ms, ans, _, _ in out if ans != truth(ms)] print(f" ({plant}) {what}: first misses {wrong[:4]}") check(f"B{plant} the plant misses P1", wrong != [], f"{len(wrong)} wrong answers") def main(): if not section_control(): print(" a red control voids the run") return 1 off, miss = section_reader() o2, m2 = section_random() section_reduction() section_plants() section("K the kill") fired = off + o2 + miss + m2 > 0 print(f" answers off {off + o2}, counts off {miss + m2}: KILL " f"{'FIRES' if fired else 'MISSES'}") print() print(f"{sum(CHECKS)}/{len(CHECKS)} checks pass") return 0 if all(CHECKS) else 1 if __name__ == "__main__": sys.exit(main())