coprime_mul.py
Checks: SUPPLY: The element machine reads coprimality in 3M + 5B + 3 unit ops with multiply and O(B(B + M)) without theorem.
Cited on: SUPPLY.
To run it: save coprime_mul.py, with coprime.py, supply.py beside it; standard library only.
"""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())