The field-width loop (round six, `gloopQ`)
ProvedIntMul.Kappa.R6.IL3H.gloopQcomplexity-theoryinteger-multiplicationkappa-improvement
The field-width loop.
The following holds (Lean statement, in the scope of module Solutions.R6IL3Top1):
theorem IntMul.Kappa.R6.IL3H.gloopQ {cz : ℕ} (hcz : 1 ≤ cz) {jG : Fin Pp} {cont : IStmt HS Pp}
(hj : tbl jG = gloopC cz jG cont) {P K D S ρ r w Z Mb Bz : ℕ} (hMb : zsz (Mb : ℤ) ≤ Bz)
(hM : 2 * gBnd cz Z + Gv cz Z + 2 ≤ Mb)
{f g : Fin HS → List ℤ} (hf : Clean0 f) (hg : Clean0 g) {cc : ℕ}
(Cont : ∀ σ, DescR σ P K D S ρ r w → σ vG = some (Z : ℤ) → σ 11 = some (Gv cz Z : ℤ) →
RunQ Isym tbl σ cont f g cc) :
∀ n σ, (DescR σ P K D S ρ r w ∧ σ vG = some (Z : ℤ) ∧ ∃ j : ℕ, σ 11 = some (j : ℤ) ∧
σ 12 = some ((2 ^ j : ℕ) : ℤ) ∧ j + n = Gv cz Z) →
RunQ Isym tbl σ (.call jG) f g (cc + (n + 1) * cLoopS 15 2 Bz)
Context. Round six, item language (I3): the entry loops of the uniform Proposition 14
loopQ: a generic continuation-passing loop (testC 16 cond (push step; call j) cont) from an invariant indexed by the number of remaining iterations.gloopC cz: withZonvG = 24, findsG = clog₂ (4 (Z + cz) (Z + cz + 2))on11(gloopQ; the compact-controls field width).dloopC c: withDon22, findsd = dep m Don12andW^don13(dloopQ).
Formalization Note. Part of the Lean formalization of the round-six κ-improvement (integer-multiplication-kappa campaign, target IntMul.Kappa.jain_round6_framework). The statement is copied verbatim from the Lean development; the platform node carries the same declaration name. Definitions it mentions live in the IntMul_Kappa_R6_Defs* bundles (on top of the published κ bundles IntMul_Kappa_K_Defs*).
Preamble
-- Round-six κ development (integer-multiplication-kappa), generated by skeleton subtraction.
import Definitions.Def_IntMul_Kappa_R6_Defs22
set_option autoImplicit false
set_option relaxedAutoImplicit false
set_option maxHeartbeats 1000000
open IntMul IntMul.Kappa IntMul.Kappa.R6 IntMul.Kappa.R6.IL3H
open IntMul NLogN NLogN.KIL NLogN.KFD NLogN.KFB NLogN.KFG NLogN.KFH NLogN.KFN NLogN.KFW Complex P8Lift Butterfly IntMul.Kappa.R6.Cx
variable {Pp : ℕ} {Isym : List Sym} {tbl : Fin Pp → IStmt HS Pp}
Formal statement
theorem IntMul.Kappa.R6.IL3H.gloopQ {cz : ℕ} (hcz : 1 ≤ cz) {jG : Fin Pp} {cont : IStmt HS Pp}
(hj : tbl jG = gloopC cz jG cont) {P K D S ρ r w Z Mb Bz : ℕ} (hMb : zsz (Mb : ℤ) ≤ Bz)
(hM : 2 * gBnd cz Z + Gv cz Z + 2 ≤ Mb)
{f g : Fin HS → List ℤ} (hf : Clean0 f) (hg : Clean0 g) {cc : ℕ}
(Cont : ∀ σ, DescR σ P K D S ρ r w → σ vG = some (Z : ℤ) → σ 11 = some (Gv cz Z : ℤ) →
RunQ Isym tbl σ cont f g cc) :
∀ n σ, (DescR σ P K D S ρ r w ∧ σ vG = some (Z : ℤ) ∧ ∃ j : ℕ, σ 11 = some (j : ℤ) ∧
σ 12 = some ((2 ^ j : ℕ) : ℤ) ∧ j + n = Gv cz Z) →
RunQ Isym tbl σ (.call jG) f g (cc + (n + 1) * cLoopS 15 2 Bz) := by sorrySource
S. Jain, round-six networks for the integer-multiplication κ-improvement campaign (https://github.com/Swapnil-jain/integer-mult-kappa, commit 5868dc7) and D. Colkitt, integer-mult-bounds (https://github.com/CrocSwap/integer-mult-bounds); target `IntMul.Kappa.jain_round6_framework`. Lean declaration `IntMul.Kappa.R6.IL3H.gloopQ`, Solutions/R6IL3Top1.lean (lines 173–268) of the round-six development.