Documentation

Complexity.Algorithms.WordRAM.ExactTriangle.RecordProduct.Flat

Initialized flat native producer and product runs #

The original four scalar headers and three signed weight arrays initialize one fixed native program. Prefix Runs, the charged final halt, exact answer words and the caller frame all refer to the same actual final data. The initialized client selects the first actual record; the caller interface exec_of_output supports every occupied ordinal.

Fixed register count, instruction bound including halt, and physical-width independence.

theorem Cslib.Algorithms.WordRAM.ExactTriangle.RecordProduct.runs_input {W m n g p A : ℕ} (values : List ℤ) (hlen : values.length = 3 * (n * n)) (hD : 16 ≤ MatrixMultiplication.Schonhage.D m) (hg : 1 ≤ g) (hp : 0 < p) (hN : MatrixMultiplication.Schonhage.D m ^ 18 ≤ n) (hv : ∀ z ∈ values, z.natAbs ≤ A) (hW : admissionWidth n (MatrixMultiplication.Schonhage.D m) g p A ≤ W) :
WordRAM.InputFits W (PreparationInput.input n (MatrixMultiplication.Schonhage.D m) g p values) ∧ have hn := ⋯; ∃ (a : WordRAM.Data 64) (idx : ExactTriangle.InstanceIndex p), WordRAM.ExecWithin W Instances.program (WordRAM.Data.init (PreparationInput.input n (MatrixMultiplication.Schonhage.D m) g p values)) a (preparationTime n (MatrixMultiplication.Schonhage.D m) g p values - 1) ∧ idx ∈ ExactTriangle.instanceIndices (fun (a b : Fin n) => values.getD (Matrix.pairIndex (a, b)) 0) (MatrixMultiplication.Schonhage.D m) g p ∧ recordOrdinal n (MatrixMultiplication.Schonhage.D m) g p (fun (q : ℕ) => values.getD q 0) idx = 0 ∧ have qs := decodedQueries hn a.mem (recordQueries n (MatrixMultiplication.Schonhage.D m) p idx) (recordQueryCount n (MatrixMultiplication.Schonhage.D m) p (fun (q : ℕ) => values.getD q 0) idx); ∃ (y : WordRAM.Data 320) (t : ℕ), t + 1 ≤ preparationTime n (MatrixMultiplication.Schonhage.D m) g p values + timeBound qs + 1 ∧ WordRAM.Runs W (entryProgram.program Reg.result) (WordRAM.State.init (PreparationInput.input n (MatrixMultiplication.Schonhage.D m) g p values)) { pc := entryProgram.size, data := y } t ∧ WordRAM.Executes W (entryProgram.program Reg.result) (WordRAM.State.init (PreparationInput.input n (MatrixMultiplication.Schonhage.D m) g p values)) (a.regs Instances.heap + MatrixMultiplication.Schonhage.QueriedProduct.outputBase (19 * m) m n qs.length) (t + 1) ∧ WordRAM.Data.Bounded W y ∧ y.regs Reg.result = a.regs Instances.heap + MatrixMultiplication.Schonhage.QueriedProduct.outputBase (19 * m) m n qs.length ∧ (∀ (j : Fin qs.length), y.mem (a.regs Instances.heap + (MatrixMultiplication.Schonhage.QueriedProduct.outputBase (19 * m) m n qs.length + ↑j)) = WordRAM.Signed.encode ((leftMatrix m n g p (fun (q : ℕ) => values.getD q 0) idx * rightMatrix m n g p (fun (q : ℕ) => values.getD q 0) idx) (qs.get j).1 (qs.get j).2)) ∧ (∀ (u : ℕ), u < a.regs Instances.heap ∨ a.regs Instances.heap + MatrixMultiplication.Schonhage.CallableProduct.windowSize n qs.length ≤ u → y.mem u = a.mem u) ∧ (∀ (j : Fin 64), y.regs (producerBank j) = a.regs j) ∧ qs.length * 2 ^ m ≤ n ^ 2

Every sufficiently wide physical execution starts from the actual original input and returns the first prepared record's exact requested product values. There is no supplied layout, run, time, sparse-count or solver certificate. Source prime selection and the outer instance loop are separate; this theorem alone is not an aggregate ExactTriangle bound.

Every native prefix is physically word-bounded from the actual admitted original input. In particular this includes dirty loads before the callable compiler's remainder instruction.