HvdH machine lemma roundE_bnd (`piBits` and `log2Bits` as register programs)
ProvedNLogN.roundE_bndThe following holds (Lean statement, in the scope of module NLogN.HNumPi):
theorem NLogN.roundE_bnd (c₁ c₂ : ℤ) (hc₁ : |c₁| ≤ 16) (hc₂ : |c₂| ≤ 16) (n M B : ℕ) (L3 : List Item)
(hnM : n + 9 ≤ M) (hMB : 2 * M + 12 ≤ B) :
∀ t : IState HS, ∀ a b : ℤ, ∀ La Lb : List Item, t.G 3 = .int n :: L3 →
t.G 46 = .int a :: La → t.G 47 = .int b :: Lb → |a| ≤ 2 ^ (2 * M + 6) - 1 →
|b| ≤ 2 ^ (2 * M + 6) - 1 → (roundE c₁ c₂).Bnd t (B + 2)
Context. The lemma belongs to the part piBits and log2Bits as register programs: Input n on register 3; the result is pushed on register 4.
Uses registers 0, 1, 2, 40 … 47.
Formalization Note. This is a lemma of the Lean development NLogN, a multitape-Turing-machine implementation of the Harvey–van der Hoeven integer multiplication algorithm, used in the proof of NLogN.FIN.theorem_1_1_nlogn : IntMul.MulTimeBound fun n => n * Real.log n. All names refer to the definition bundles IntMul_HvdH_M_Defs1–IntMul_HvdH_M_Defs8 (namespace NLogN), built on the platform model Def_IntMul_MultitapeModel and the published reference Def_IntMul_HvdH_MachineRef. The machine layer: IState HS is a state of 64 item stacks; RM programs have a semantics p.run s, a definedness predicate p.ok M s and a cost p.cost M s relative to a multiplication spec M : MulSpec; zsz z is the bit length of .
-- Harvey–van der Hoeven multitape-TM development (NLogN), generated by skeleton subtraction. import Definitions.Def_IntMul_HvdH_M_Defs8 set_option autoImplicit false set_option relaxedAutoImplicit false set_option maxHeartbeats 1000000 set_option linter.unusedSimpArgs false open NLogN open IntMul RS
theorem NLogN.roundE_bnd (c₁ c₂ : ℤ) (hc₁ : |c₁| ≤ 16) (hc₂ : |c₂| ≤ 16) (n M B : ℕ) (L3 : List Item)
(hnM : n + 9 ≤ M) (hMB : 2 * M + 12 ≤ B) :
∀ t : IState HS, ∀ a b : ℤ, ∀ La Lb : List Item, t.G 3 = .int n :: L3 →
t.G 46 = .int a :: La → t.G 47 = .int b :: Lb → |a| ≤ 2 ^ (2 * M + 6) - 1 →
|b| ≤ 2 ^ (2 * M + 6) - 1 → (roundE c₁ c₂).Bnd t (B + 2) := by sorry