coprime.py
Checks: SUPPLY: Without multiply the element machine reads coprimality in O(B(B + M)) unit ops theorem.
Cited on: SUPPLY.
To run it: save coprime.py, with supply.py beside it; standard library only.
"""coprime.py -- the element machine without multiply reads whether its
newest modulus is coprime to the earlier ones in O(B(B + M)) unit ops,
where the clock machine with one read over every register waits of
the order of their lcm.
QUESTION. supply.py's Machine: registers over windows, ops add, sub,
copy, clear and GROW (the named register becomes the new window's
singleton), a zero-test per register, no multiply and no constant. A
fixed program grows one window at a time; after the grow of the newest
window, modulus M, it reads whether M is coprime to every deep modulus
m_1 ... m_g, C' their lcm and B their maximum. The WAIT is the unit ops
from the grow to the read that answers, both ends counted, a grow and a
zero-test one op each; the FULL CYCLE adds the one op before the grow
and the upkeep after the read that keeps B for the next trip. The clock
machine's prime reader waits a pass of the order of C'
(clocks.py::section_prime, ::section_lcm_wait). Does the element machine
beat it, with no deep window addressed, and what is its floor?
THE ARGUMENT (written before the engine).
(1) WHAT A DEEP WINDOW HOLDS. With no multiply every op is one integer
linear map at every window, so after the grow at time s a deep
window tau holds Phi(t, s) w_tau mod m_tau, one integer matrix Phi
for all windows: a zero-test reads the deep pool only through the
subgroup the registers generate in the sum of the Z/m_tau, and no
window need be addressed. The clock machine's floor rests on each
deep integer moving by unit steps, |X_b| < C' for fewer than C'
ops; Y := Y + X in a counted loop multiplies every window by the
count, so one deep integer passes C' in few ops.
(2) THE READER. X := DEEP (1 at every deep window, 0 at the newest);
for d = 1 ... B with gcd(d, M) = 1, X := d X by d - 1 adds of X
into a copy, counted down by a counter. Every deep window then
holds N = prod of the d <= B coprime to M, and zero(X) holds iff
every m_tau | N: if every deep modulus is coprime to M each is a
factor d; if a prime q divides M and m_tau it divides no factor.
The unit test of d lives on the newest window: W = d F, V += W and
S += F in lockstep, V first zero at k = M / gcd(d, M), where S is
zero iff gcd(d, M) = 1. Counters are ALIGNED, value c at every
window of a set: d - 1 and B - 1 on the deep windows (capacity
C' > B - 1), M - 1 and the new maximum on every window (capacity
lcm(C', M) > max(B, M) - 1). After the read B is kept for the next
trip: M - 1 measured, B - 1 realigned onto the new window, the
maximum taken by one counter climbing past both.
(3) THE FLOOR. After the grow every newest-window integer starts at 0
or 1; an add or sub at most doubles the largest absolute value,
copy, clear and a zero-test do not raise it. So t ops after the
grow every newest-window integer has |x| <= 2^t, and while
2^t < M a zero there is an exact 0, the same read under any
modulus above 2^t. The run before the grow and the deep windows
do not see M, later grows read the supply past it. Two supplies
differing only in M and M' > M with different answers run alike
while 2^t < M: M' = Mq with q a prime of C' where M is coprime,
else a prime M' above C' and M. So a reader correct on both waits
at least 2 + ceil(log2 M) wherever C' > 1, the grow and the read
counted.
(4) THE COUNT, read off the code. Before the d loop, grow, ONES, X,
DC, W: 5 ops. Per d: the unit test 3M/gcd(d, M) + 3 (two clears,
three ops a step, the test of S), the compare and advance 4, the
last d's advance absent; per unit d the multiply 3(d - 1) + 4
(two copies, three ops a step, the last test, the copy back).
The read 1. So
wait = 4 + sum_{d<=B} (3M/gcd(d, M) + 7)
+ sum_{d<=B, gcd(d, M) = 1} (3d + 1).
The upkeep: M - 1 measured in 3M, B - 1 realigned in 3B - 1,
the climb of K to max(B, M) - 1 in 5 max(B, M) with its
clear, the copy back 1: 3M + 3B + 5 max(B, M). With the copy of
DEEP before the grow, full = 1 + wait + 3M + 3B + 5 max(B, M),
at most 3BM + (3/2)B^2 + 17.5B + 8M + 5, inside
3BM + 2B^2 + 20(B + M).
PREDICTIONS (frozen before the engine).
P1 the reader's answer equals [gcd(M, C') = 1] at every g on
m_g = g + 1 and on the primes, g = 1 ... 30, and on 40 random
supplies with moduli 2 ... 40 in any order, g = 1 ... 25.
P2 its full cycle (wait and upkeep) is at most 3BM + 2B^2 + 20(B + M)
unit ops at every g of P1.
P3 on m_g = g + 1 the clock prime reader's wait passes the element
full cycle by g ~ 5, on the primes by g ~ 3; at g = 30 it is
about 10^14 or more.
P4 the wait is at least the floor of (3) at every g (a print; the
floor is the proof in (3)).
R the registers ONES DEEP F X Y DC BC TC W V S T MC K, 14 (the frozen
count read 13, a slip over this list).
P5 (added with (4), after the first run) the wait and the full cycle
equal (4)'s closed forms at every trip of P1.
CONTROLS. The clock prime reader run on this engine with only
TICK (B := B + ONES) and PULSE (B := B + F), g = 1 ... 8 on g + 1 and
1 ... 5 on the primes: its exit read and wait equal the closed form,
second read at pass C((-C^-1) mod M) when gcd(C, M) = 1, else first
read at pass lcm(C, M), wait 1 + 5(k - 1) + 4 or + 2. It is a third
arm only loosely: a reader whose deep windows move by unit steps alone
(one register, adds of ONES and F), a different program, not the
element reader less one op.
Planted breaks, each must miss P1: (a) multiply by every d; (b) stop
the d loop at B - 1.
KILL (frozen). Printed per g: the element full cycle and the clock wait
on g + 1 and on the primes, g = 1 ... 30. Fires if on either supply the
element full cycle is not the smaller at every g from some g <= 12
through 30, or if any answer of P1 differs from the gcd.
FINDINGS (entered after the run, from its printed output).
C1 the clock prime reader on this engine exits where its closed form
says: g + 1, passes 2b 12a 24b 60a 300b 840a 2520a 2520a at g = 1..8
(b its second read); primes, 2b 24b 90b 2100b 23100b at g = 1..5.
P1 every answer is the gcd's: 30 of 30 on g + 1, 30 of 30 on the
primes, 1000 random trips (169 coprime, 831 not), 0 off.
P2 the full cycle sits inside 3BM + 2B^2 + 20(B + M) at every trip;
at g = 30, 3401 against 6158 on g + 1 (M = 32, B = 31) and 64640
against 73391 on the primes (M = 127, B = 113).
P3 the clock is passed from g = 4 on g + 1 (predicted about 5) and
from g = 3 on the primes (predicted about 3); at g = 30 its wait is
7.220e14 and 2.213e48.
P4 the wait clears 2 + ceil(log2 M) everywhere: 47 against 4 at
g = 1, 63284 against 9 at g = 30 on the primes.
P5 the wait and the full cycle equal (4)'s closed forms at all 1060
trips.
B both plants miss: (a) 7 wrong answers by g = 12, (b) 14.
K KILL MISSES. The clock is the smaller only at g = 1, 2, 3 on g + 1
(10 against 78 at g = 1) and g = 1, 2 on the primes; from g = 4 and
g = 3 on the element full cycle is smaller at every g through 30,
at g = 30 3401 against 7.220e14 on g + 1 and 64640 against
2.213e48 on the primes.
R 14 registers, the list's.
RUN RECORD. 17 checks, 2.3 s, 6.8 MB.
"""
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 Machine, PRIMES, check, section, CHECKS # noqa: E402
REGS = {"ONES", "DEEP", "F", "X", "Y", "DC", "BC", "TC", "W", "V", "S",
"T", "MC", "K"}
class Counted(Machine):
"""supply.py's Machine, one unit per op, grow and zero-test."""
def __init__(self, supply):
super().__init__(supply)
self.units = 0
self.names = set()
def grow(self, into):
self.units += 1
self.names.add(into)
super().grow(into)
def op(self, d, a, b, sign):
self.units += 1
self.names.update((d, a, b))
super().op(d, a, b, sign)
def copy(self, d, a):
self.units += 1
self.names.update((d, a))
super().copy(d, a)
def clear(self, d):
self.units += 1
self.names.add(d)
super().clear(d)
def zero(self, r):
self.units += 1
self.names.add(r)
return super().zero(r)
class Reader:
"""The fixed program: one trip per grow, B kept from trip to trip."""
def __init__(self, supply, plant=None):
self.E = Counted(supply)
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.copy("X", "DEEP")
E.clear("DC")
E.copy("W", "F")
stop = "BC"
if self.plant == "b":
E.sub("BC2", "BC", "DEEP")
stop = "BC2"
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") or self.plant == "a":
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")
answer = E.zero("X")
wait = E.units - start
self.upkeep()
return answer, wait, E.units - begin
def upkeep(self):
E = self.E
E.clear("MC")
E.copy("S", "F")
while not E.zero("S"):
E.add("MC", "MC", "ONES")
E.add("S", "S", "F")
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 truth(ms):
"""[gcd(M, C') = 1] for the last modulus against the earlier ones."""
return all(gcd(ms[-1], m) == 1 for m in ms[:-1])
def counted(B, M):
"""The argument's (4): the wait and the full cycle in closed form."""
wait = 4 + sum(3 * M // gcd(d, M) + 7 for d in range(1, B + 1)) \
+ sum(3 * d + 1 for d in range(1, B + 1) if gcd(d, M) == 1)
return wait, 1 + wait + 3 * M + 3 * B + 5 * max(B, M)
def bound(B, M):
return 3 * B * M + 2 * B * B + 20 * (B + M)
def lcm_all(ms):
c = 1
for m in ms:
c = c * m // gcd(c, m)
return c
def clock_closed(deep, M):
"""The clock prime reader's exit: (second read?, pass, wait)."""
C = lcm_all(deep)
if gcd(C, M) == 1:
k = C * (-pow(C, -1, M) % M)
return True, k, 1 + 5 * (k - 1) + 4
k = C * M // gcd(C, M)
return False, k, 1 + 5 * (k - 1) + 2
def clock_engine(supply, g):
"""The clock prime reader on the Machine: TICK and PULSE only."""
E = Counted(supply)
E.clear("ONES")
for _ in range(g):
E.grow("F")
E.add("ONES", "ONES", "F")
E.clear("B")
E.units = 0
E.grow("F")
E.add("ONES", "ONES", "F")
E.units -= 1
k = 0
while True:
k += 1
E.add("B", "B", "ONES")
if E.zero("B"):
return False, k, E.units
E.add("B", "B", "F")
if E.zero("B"):
return True, k, E.units
E.sub("B", "B", "F")
SUPPLIES = [("g + 1", lambda i: i + 2), ("primes", lambda i: PRIMES[i])]
def section_control():
section("C the clock prime reader on the element engine, against "
"its closed form")
for name, sup, top in (("g + 1", SUPPLIES[0][1], 8),
("primes", SUPPLIES[1][1], 5)):
off, rows = 0, []
for g in range(1, top + 1):
ms = [sup(i) for i in range(g + 1)]
got = clock_engine(sup, g)
want = clock_closed(ms[:-1], ms[-1])
off += got != want
rows.append(f"{g}:{got[1]}{'b' if got[0] else 'a'}")
print(f" {name}: pass and read by g " + " ".join(rows))
check(f"C1 {name}: engine exit = closed form, g = 1..{top}",
off == 0, f"{off} off")
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()
ms = [sup(i) for i in range(g + 1)]
out.append((g, ms, ans, wait, full))
return out, R.E.names
def section_reader():
section("E the element reader: answers, waits, upkeep, the clock")
tables = {}
for name, sup in SUPPLIES:
out, names = run_supply(sup, 30)
tables[name] = out
print(f" {name}: registers {len(names)} {sorted(names)}")
print(f" {'g':>3} {'M':>4} {'B':>4} {'ans':>4} {'wait':>6} "
f"{'full':>6} {'bound':>7} {'floor':>5} clock wait")
off = over = under = miss = 0
for g, ms, ans, wait, full in out:
M, B = ms[-1], max(ms[:-1])
floor = 2 + ceil(log2(M))
clk = clock_closed(ms[:-1], M)[2]
off += ans != truth(ms)
over += full > bound(B, M)
under += wait < floor
miss += (wait, full) != counted(B, M)
print(f" {g:>3} {M:>4} {B:>4} {str(ans)[0]:>4} {wait:>6} "
f"{full:>6} {bound(B, M):>7} {floor:>5} {clk:.3e}")
check(f"P1 {name}: every answer is the gcd's, g = 1..30",
off == 0, f"{off} off")
check(f"P2 {name}: full cycle <= 3BM + 2B^2 + 20(B + M)",
over == 0, f"{over} over")
check(f"P4 {name}: wait >= 2 + ceil(log2 M)", under == 0,
f"{under} under")
check(f"P5 {name}: wait and full cycle = the closed forms",
miss == 0, f"{miss} off")
check(f"R {name}: the frozen {len(REGS)} registers",
names == REGS, f"{len(names)} used")
return tables
def section_random():
section("P1 40 random supplies, moduli 2..40 in any order, g = 1..25")
rng = random.Random(1668)
off = over = miss = n = 0
both = [0, 0]
for _ in range(40):
ms = [rng.randint(2, 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)
over += full > bound(B, M)
miss += (wait, full) != counted(B, M)
both[truth(mm)] += 1
n += 1
print(f" {n} trips, {both[1]} coprime, {both[0]} not")
check("P1 random: every answer is the gcd's", off == 0, f"{off} off")
check("P2 random: full cycle within the bound", over == 0,
f"{over} over")
check("P5 random: wait and full cycle = the closed forms", miss == 0,
f"{miss} off")
def section_plants():
section("B planted breaks must miss P1")
for plant, what in (("a", "multiply by every d"),
("b", "stop the d loop at B - 1")):
bad = []
for name, sup in SUPPLIES:
out, _ = run_supply(sup, 12, plant)
bad += [(name, g) for g, ms, ans, _, _ in out
if ans != truth(ms)]
print(f" ({plant}) {what}: first misses {bad[:4]}")
check(f"B{plant} the plant misses P1", bad != [],
f"{len(bad)} wrong answers")
def section_kill(tables):
section("K the kill: the element full cycle against the clock wait")
fired = False
for name, out in tables.items():
lose = [g for g, ms, _, _, full in out
if full >= clock_closed(ms[:-1], ms[-1])[2]]
last = max(lose) if lose else 0
print(f" {name}: element not smaller at g = {lose}; smaller at "
f"every g from {last + 1} through 30")
fired |= last + 1 > 12
print(f" KILL {'FIRES' if fired else 'MISSES'}")
def main():
section_control()
tables = section_reader()
section_random()
section_plants()
section_kill(tables)
print()
print(f"{sum(CHECKS)}/{len(CHECKS)} checks pass")
return 0 if all(CHECKS) else 1
if __name__ == "__main__":
sys.exit(main())