Moving a list of integers between stacks (expression-controlled count)
ProvedNLogN.FW.spec_mvListLet be distinct registers below 55 ( different from ), let stack start with the integer list , and let be a clean linear expression, defined in , with value and bit size bounded by , where every entry of has bit length . Then the straight-line program mvList i j c n moves reversed onto stack (using as counter), with cost at most .
Formalization Note. The machine layer: IState HS is a state with stacks of items (Item = integer or mark), an input position and an output; RM programs (straight-line register code RS, loops rep, conditionals, calls of the multiplication procedure through a MulSpec giving its domain and cost) have a functional semantics p.run s, a definedness predicate p.ok M s and a cost p.cost M s; Spec M p s s' c abbreviates p.ok M s ∧ p.run s = s' ∧ p.cost M s ≤ c. ints L / gints U push an integer list / a list of pairs as items (head = top); zsz z is the bit length of . MulBnd M m Φ says the multiplication procedure accepts all pairs of integers of bit length at cost . Register names (GU, CR, KB, XN, …) are fixed stack indices.
-- Harvey–van der Hoeven multitape-TM development (NLogN), generated by skeleton subtraction. import Definitions.Def_IntMul_HvdH_M_Defs4 set_option autoImplicit false set_option relaxedAutoImplicit false set_option maxHeartbeats 1000000 set_option linter.unusedSimpArgs false set_option linter.unusedVariables false open NLogN open NLogN.FW open IntMul NLogN
theorem NLogN.FW.spec_mvList (M : MulSpec) (i j c : Fin HS) (n : Ex HS) (s : IState HS) (l : List ℤ)
(Ri : List Item) (hij : i ≠ j) (hci : c ≠ i) (hcj : c ≠ j) (hi : s.G i = ints l ++ Ri)
(hn : n.eval s = l.length) (hi55 : i.val < 55) (hj55 : j.val < 55) (hc55 : c.val < 55)
(hnc : n.Clean) (hno : n.ok s) (B : ℕ) (hl : n.Lin) (hnB : n.Bnd s B)
(hB : ∀ x ∈ l, zsz x ≤ B) :
Spec M (RM.rs (mvList i j c n)) s ((s.upd i Ri).upd j (ints l.reverse ++ s.G j))
((n.size + 1) * 2000 * (B + 2) + l.length * (14000 * (B + 2) + 30) + 32) := by sorry