nx_mulchain_deep.nx

nx_mulchain_deep.nx -- the DEEPENED chain search (the team's answer to its own escalation: "constants exceed imul cost -- author imul or deepen the search?"). THEORY (researched, not hand-waved): finding the shortest op-chain for c*x is computing a length-/time-BOUNDED KOLMOGOROV COMPLEXITY of that function over our instruction set. The unbounded version is uncomputable (Berry/halting); we only escape that because our ops are loop-free + total + length-capped. The principled search order is LEVIN's universal search: shortest-first, bounding by length AND cost (Kt = |program| + log time). Our iterative deepening over op-count IS Levin shortest-first; the `+log time` term is the cost cap below. Two prunes keep it tractable: (1) REACHABILITY (the THURBER bound, generalized): an addition-chain element at most DOUBLES per step (prune when 2^m * a_i < n); our op set grows faster (SHL by maxsh, LEA +3 bits), so we use maxmag << (G*rem) < |C| with G = max(maxsh,4). COMPLETE (never prunes a reachable target), collapses the dead subtrees that hung the prime case. (2) COST CAP (Levin's +log time): a serial chain of N 1-cycle ops ~ N cycles latency vs imul ~3 cycles, so searching past the cost-competitive depth is pointless -> cap maxL. NB: the classic Hamming-weight lower bounds (Schonhage log2 n + log2 v(n)) DON'T transfer here -- SHL/LEA do many doublings in one op, so our minimal chains are shorter and those bounds under-count us. The reach bound + cost cap are what actually apply to our op set. Refs: Kolmogorov complexity (uncomputable); Levin universal search / Kt; Thurber 1999 (addition-chain branch-and-bound). license_tier: ORIGINAL