Value and heap-effect specifications for Strassen matrix multiplication
DefinitionCLRS_Chapter4_Algo2LeanExamples_MatrixStrassenThis bundle supplies the mathematical value functions, allocation and heap-effect transformers, exact counter vectors, and local invariants used to analyze Strassen matrix multiplication. It retains the source-facing generated call relations. Substantial execution, matrix-correctness and runtime proofs are separate theorem nodes. Inputs contain arbitrary unbounded integers and may share row references; specific separation hypotheses are stated by the lemmas that need them. The measured cost is explicit source ticks, excluding uncharged allocation, bookkeeping and integer bit complexity.
Formalization Note. This content is transcribed from Algo2Lean development snapshot fd33cf959b39f9e4a9fcfda4ef31d5a36b784d41, with explicit platform import and namespace adaptation. It is not attributed to public compiler v0.1.4. The submitted definition bundle must be checked without unfinished-proof assumptions.
import Definitions.Def_CLRS_Chapter4_Algo2Lean
import Definitions.Def_CLRS_Chapter4_Algo2LeanExamples_MatrixStrassenGenerated
import Definitions.Def_CLRS_Chapter4_Algo2LeanExamples_MatrixStrassenPoints
import Definitions.Def_CLRS_Chapter4_Algo2LeanLib_MatrixHeap
import Std
set_option autoImplicit false
set_option backward.isDefEq.respectTransparency false
set_option backward.defeqAttrib.useBackward true
namespace CLRS
open MatrixStrassenLibrary MatrixStrassenLibrary.Algo2LeanGenerated
/-! Generated by scripts/build_chapter4_analysis.py.
Edit the corresponding source modules in proofs/chapter4, then rebuild.
This bundle is checked against the actual generated algorithm and can
be loaded directly into the editor's Lean analysis pane. -/
/-! Source: proofs/chapter4/MatrixMath.lean -/
section
/-!
Finite integer-matrix algebra and arithmetic-operation recurrences for CLRS 4.
These are mathematical lemmas. An application to an Algo2Lean source program
must additionally prove that the generated execution relation implements these
operations and charges these recurrences; this file alone makes no such claim.
Matrices are unbounded mathematical functions; `mul n` reads the first n inner
coordinates. In applications n is the finite matrix dimension.
-/
namespace Chapter4Math
abbrev Vector := Nat → Int
def dot : Nat → Vector → Vector → Int
| 0, _, _ => 0
| n + 1, a, b => dot n a b + a n * b n
end Chapter4Math
namespace Chapter4Math
abbrev Matrix := Nat → Nat → Int
def add (a b : Matrix) : Matrix := fun i j => a i j + b i j
def sub (a b : Matrix) : Matrix := fun i j => a i j - b i j
def mul (n : Nat) (a b : Matrix) : Matrix :=
fun i j => dot n (a i) (fun k => b k j)
/-- A block is a view; it does not copy or mutate its source matrix. -/
def block (a : Matrix) (row col : Nat) : Matrix := fun i j => a (row + i) (col + j)
structure Blocks where
nw : Matrix
ne : Matrix
sw : Matrix
se : Matrix
/-- The four equal-sized square blocks of a matrix with dimension `2*n`. -/
def quadrants (n : Nat) (a : Matrix) : Blocks :=
⟨block a 0 0, block a 0 n, block a n 0, block a n n⟩
/-- Ordinary multiplication written with eight block products. -/
def blockMul (n : Nat) (a b : Blocks) : Blocks :=
⟨add (mul n a.nw b.nw) (mul n a.ne b.sw),
add (mul n a.nw b.ne) (mul n a.ne b.se),
add (mul n a.sw b.nw) (mul n a.se b.sw),
add (mul n a.sw b.ne) (mul n a.se b.se)⟩
/-- The seven products and eight combining additions/subtractions in CLRS. -/
def strassen (n : Nat) (a b : Blocks) : Blocks :=
let p1 := mul n a.nw (sub b.ne b.se)
let p2 := mul n (add a.nw a.ne) b.se
let p3 := mul n (add a.sw a.se) b.nw
let p4 := mul n a.se (sub b.sw b.nw)
let p5 := mul n (add a.nw a.se) (add b.nw b.se)
let p6 := mul n (sub a.ne a.se) (add b.sw b.se)
let p7 := mul n (sub a.nw a.sw) (add b.nw b.ne)
⟨add (sub (add p5 p4) p2) p6, add p1 p2,
add p3 p4, sub (sub (add p5 p1) p3) p7⟩
end Chapter4Math
namespace Chapter4Math
/-- The sum of squared half-dimensions over the Strassen recursion tree. -/
def strassenOverhead : Nat → Nat
| 0 => 0
| k + 1 => 7 * strassenOverhead k + 4^k
/-- Number of nodes (including leaves) in an arity-ary full recursion tree. -/
def calls (arity : Nat) : Nat → Nat
| 0 => 1
| k+1 => 1 + arity * calls arity k
end Chapter4Math
namespace Chapter4Math
end Chapter4Math
end
/-! Source: proofs/chapter4/StrassenValue.lean -/
section
open Chapter4Math
namespace StrassenValues
abbrev Seq := Int → Int → Int
/-- Pointwise addition/subtraction on a finite square of nested rows. -/
def linearValues (count : Nat) (sign : Int) (a b : Seq) : Seq := fun row col =>
if 0 ≤ row ∧ row < (count : Int) ∧ 0 ≤ col ∧ col < (count : Int)
then a row col + sign * b row col else 0
/-- Copy a square block into fresh rows. The stride argument is retained in the
source interface, but nested indexing does not need a stride. -/
def quadrantValues (_n h row col : Int) (a : Seq) : Seq := fun i j =>
if 0 ≤ i ∧ i < h ∧ 0 ≤ j ∧ j < h then a (row+i) (col+j) else 0
/-- Place four nested blocks into the corresponding quadrants. -/
def joinValues (h : Int) (a b c d : Seq) : Seq := fun row col =>
if 0 ≤ row ∧ row < 2*h ∧ 0 ≤ col ∧ col < 2*h then
if row < h then
if col < h then a row col else b row (col-h)
else
if col < h then c (row-h) col else d (row-h) (col-h)
else 0
/-- Finite matrix entries represented by the first n entries of the first n rows. -/
def Rep (n : Nat) (a : Seq) (A : Matrix) : Prop :=
∀ i j, i < n → j < n → a (i : Int) (j : Int) = A i j
/-- Pure value returned by the seven recursive products in the source. -/
def strassenValue : Nat → Seq → Seq → Seq
| 0, a, b => fun row col => if row = 0 ∧ col = 0 then a 0 0 * b 0 0 else 0
| depth+1, a, b =>
let h : Nat := 2^depth
let n : Int := 2*h
let a11 := quadrantValues n h 0 0 a
let a12 := quadrantValues n h 0 h a
let a21 := quadrantValues n h h 0 a
let a22 := quadrantValues n h h h a
let b11 := quadrantValues n h 0 0 b
let b12 := quadrantValues n h 0 h b
let b21 := quadrantValues n h h 0 b
let b22 := quadrantValues n h h h b
let p1 := strassenValue depth a11 (linearValues h (-1) b12 b22)
let p2 := strassenValue depth (linearValues h 1 a11 a12) b22
let p3 := strassenValue depth (linearValues h 1 a21 a22) b11
let p4 := strassenValue depth a22 (linearValues h (-1) b21 b11)
let p5 := strassenValue depth (linearValues h 1 a11 a22) (linearValues h 1 b11 b22)
let p6 := strassenValue depth (linearValues h (-1) a12 a22) (linearValues h 1 b21 b22)
let p7 := strassenValue depth (linearValues h (-1) a11 a21) (linearValues h 1 b11 b12)
let c11 := linearValues h 1 (linearValues h (-1) (linearValues h 1 p5 p4) p2) p6
let c12 := linearValues h 1 p1 p2
let c21 := linearValues h 1 p3 p4
let c22 := linearValues h (-1) (linearValues h (-1) (linearValues h 1 p5 p1) p3) p7
joinValues h c11 c12 c21 c22
end StrassenValues
end
/-! Source: proofs/chapter4/StrassenLinear.lean -/
section
open Algo2LeanCore Algo2LeanGenerated
namespace MatrixStrassenAnalysis
/- The source loops first receive reusable heap summaries. Matrix algebra and
the recursive correctness argument then use these summaries as interfaces. -/
def linearStep (heap : Heap) (a b c : SeqRef) (sign index : Int) : Heap :=
(heap.write c index (heap.read a index + sign * heap.read b index)).tick "linear_cells"
def linearRun : Nat → Heap → SeqRef → SeqRef → SeqRef → Int → Int → Heap
| 0, heap, _, _, _, _, _ => heap
| count + 1, heap, a, b, c, sign, index =>
linearRun count (linearStep heap a b c sign index) a b c sign (index + 1)
def AtLinear (state : Configuration) (heap : Heap) (a b c : SeqRef)
(bound sign index : Int) : Prop :=
matrix_linear_row.At.loop state ∧ state.heap = heap ∧
matrix_linear_row.Local.a state = some a ∧ matrix_linear_row.Local.b state = some b ∧
matrix_linear_row.Local.c state = some c ∧ matrix_linear_row.Local.count state = some bound ∧
matrix_linear_row.Local.sign state = some sign ∧ matrix_linear_row.Local.i state = some index
end MatrixStrassenAnalysis
end
/-! Source: proofs/chapter4/StrassenHelpers.lean -/
section
open Algo2LeanCore Algo2LeanGenerated Algo2LeanCore.MatrixHeap
namespace MatrixStrassenHelpers
open MatrixStrassenAnalysis
def copyStep (heap : Heap) (a c : SeqRef) (column index : Int) : Heap :=
(heap.write c index (heap.read a (column+index))).tick "copied_cells"
def copyRun : Nat → Heap → SeqRef → SeqRef → Int → Int → Heap
| 0, heap, _, _, _, _ => heap
| count+1, heap, a, c, column, index =>
copyRun count (copyStep heap a c column index) a c column (index+1)
def joinStep (heap : Heap) (a b c : SeqRef) (h index : Int) : Heap :=
((heap.write c index (heap.read a index)).write c (index+h) (heap.read b index)).tick "copied_cells" 2
def joinRun : Nat → Heap → SeqRef → SeqRef → SeqRef → Int → Int → Heap
| 0, heap, _, _, _, _, _ => heap
| count+1, heap, a, b, c, h, index =>
joinRun count (joinStep heap a b c h index) a b c h (index+1)
def rowPrefix (values : Values) (count : Nat) : Values := fun i j =>
if 0 ≤ i ∧ i < (count:Int) then values i j else 0
def pairedPrefix (values : Values) (n count : Nat) : Values := fun i j =>
if (0 ≤ i ∧ i < (count:Int)) ∨ ((n:Int) ≤ i ∧ i < (n:Int)+(count:Int)) then values i j else 0
def FreshOn (before after : Heap) (matrix : CollectionRef) (domain : Nat → Prop) : Prop :=
(∀ i : Nat, domain i → ∃ row, rows.get after matrix i = some row ∧
before.nextRef ≤ row ∧ row < after.nextRef) ∧
(∀ i j : Nat, domain i → domain j → rows.get after matrix i = rows.get after matrix j → i = j)
def pairedDomain (n count : Nat) (i : Nat) : Prop :=
i < count ∨ (n ≤ i ∧ i < n + count)
end MatrixStrassenHelpers
end
/-! Source: proofs/chapter4/StrassenQuadrant.lean -/
section
/-! A square-block copy composes the verified row copier, preserving arbitrary
shared input rows while allocating the result row by row. -/
open Algo2LeanCore Algo2LeanGenerated Algo2LeanCore.MatrixHeap
namespace MatrixStrassenHelpers
def quadrantPrefix (values : Values) (count : Nat) : Values := fun i j =>
if 0 ≤ i ∧ i < (count : Int) then values i j else 0
end MatrixStrassenHelpers
end
/-! Source: proofs/chapter4/StrassenComposition.lean -/
section
/-! Composition of the recursive branch using only source-level call summaries.
Each field records one real source call in evaluation order, including nested
arguments. This lemma by itself assumes no mathematical correctness contract. -/
open Algo2LeanCore Algo2LeanGenerated
namespace MatrixStrassenComposition
/-- The returned heap and reference of one source call. -/
structure SeqResult where
heap : Heap
result : CollectionRef
/-- The 34 completed calls of a nontrivial Strassen invocation, in their actual
left-to-right evaluation order. Intermediate references are explicit. -/
structure BranchRun (startHeap : Heap) (a b : CollectionRef) (n half : Int) where
a11 : SeqResult
a12 : SeqResult
a21 : SeqResult
a22 : SeqResult
b11 : SeqResult
b12 : SeqResult
b21 : SeqResult
b22 : SeqResult
linear1 : SeqResult
p1 : SeqResult
linear2 : SeqResult
p2 : SeqResult
linear3 : SeqResult
p3 : SeqResult
linear4 : SeqResult
p4 : SeqResult
linear5 : SeqResult
linear6 : SeqResult
p5 : SeqResult
linear7 : SeqResult
linear8 : SeqResult
p6 : SeqResult
linear9 : SeqResult
linear10 : SeqResult
p7 : SeqResult
linear11 : SeqResult
linear12 : SeqResult
c11 : SeqResult
c12 : SeqResult
c21 : SeqResult
linear16 : SeqResult
linear17 : SeqResult
c22 : SeqResult
joined : SeqResult
a11_run : matrix_quadrant.Call startHeap (a, n, half, 0, 0) a11.heap a11.result
a12_run : matrix_quadrant.Call a11.heap (a, n, half, 0, half) a12.heap a12.result
a21_run : matrix_quadrant.Call a12.heap (a, n, half, half, 0) a21.heap a21.result
a22_run : matrix_quadrant.Call a21.heap (a, n, half, half, half) a22.heap a22.result
b11_run : matrix_quadrant.Call a22.heap (b, n, half, 0, 0) b11.heap b11.result
b12_run : matrix_quadrant.Call b11.heap (b, n, half, 0, half) b12.heap b12.result
b21_run : matrix_quadrant.Call b12.heap (b, n, half, half, 0) b21.heap b21.result
b22_run : matrix_quadrant.Call b21.heap (b, n, half, half, half) b22.heap b22.result
linear1_run : matrix_linear.Call b22.heap (b12.result, b22.result, half, -1) linear1.heap linear1.result
p1_run : strassen.Call linear1.heap (a11.result, linear1.result, half) p1.heap p1.result
linear2_run : matrix_linear.Call p1.heap (a11.result, a12.result, half, 1) linear2.heap linear2.result
p2_run : strassen.Call linear2.heap (linear2.result, b22.result, half) p2.heap p2.result
linear3_run : matrix_linear.Call p2.heap (a21.result, a22.result, half, 1) linear3.heap linear3.result
p3_run : strassen.Call linear3.heap (linear3.result, b11.result, half) p3.heap p3.result
linear4_run : matrix_linear.Call p3.heap (b21.result, b11.result, half, -1) linear4.heap linear4.result
p4_run : strassen.Call linear4.heap (a22.result, linear4.result, half) p4.heap p4.result
linear5_run : matrix_linear.Call p4.heap (a11.result, a22.result, half, 1) linear5.heap linear5.result
linear6_run : matrix_linear.Call linear5.heap (b11.result, b22.result, half, 1) linear6.heap linear6.result
p5_run : strassen.Call linear6.heap (linear5.result, linear6.result, half) p5.heap p5.result
linear7_run : matrix_linear.Call p5.heap (a12.result, a22.result, half, -1) linear7.heap linear7.result
linear8_run : matrix_linear.Call linear7.heap (b21.result, b22.result, half, 1) linear8.heap linear8.result
p6_run : strassen.Call linear8.heap (linear7.result, linear8.result, half) p6.heap p6.result
linear9_run : matrix_linear.Call p6.heap (a11.result, a21.result, half, -1) linear9.heap linear9.result
linear10_run : matrix_linear.Call linear9.heap (b11.result, b12.result, half, 1) linear10.heap linear10.result
p7_run : strassen.Call linear10.heap (linear9.result, linear10.result, half) p7.heap p7.result
linear11_run : matrix_linear.Call p7.heap (p5.result, p4.result, half, 1) linear11.heap linear11.result
linear12_run : matrix_linear.Call linear11.heap (linear11.result, p2.result, half, -1) linear12.heap linear12.result
c11_run : matrix_linear.Call linear12.heap (linear12.result, p6.result, half, 1) c11.heap c11.result
c12_run : matrix_linear.Call c11.heap (p1.result, p2.result, half, 1) c12.heap c12.result
c21_run : matrix_linear.Call c12.heap (p3.result, p4.result, half, 1) c21.heap c21.result
linear16_run : matrix_linear.Call c21.heap (p5.result, p1.result, half, 1) linear16.heap linear16.result
linear17_run : matrix_linear.Call linear16.heap (linear16.result, p3.result, half, -1) linear17.heap linear17.result
c22_run : matrix_linear.Call linear17.heap (linear17.result, p7.result, half, -1) c22.heap c22.result
joined_run : matrix_join.Call c22.heap (c11.result, c12.result, c21.result, c22.result, half) joined.heap joined.result
result_valid : seq_Seq_Int.valid joined.heap joined.result
abbrev BranchRun.finalHeap {heap a b n half} (plan : BranchRun heap a b n half) : Heap :=
plan.joined.heap
abbrev BranchRun.result {heap a b n half} (plan : BranchRun heap a b n half) : CollectionRef :=
plan.joined.result
end MatrixStrassenComposition
end
/-! Source: proofs/chapter4/StrassenExecution.lean -/
section
open Algo2LeanCore Algo2LeanGenerated MatrixStrassenAnalysis MatrixStrassenHelpers
open Algo2LeanCore.MatrixHeap
open MatrixStrassenComposition
namespace MatrixStrassenExecution
/-- Exact counters for the source execution, including all copying passes. -/
def costs (depth : Nat) : Clocks := fun name =>
(if name = "calls" then Chapter4Math.calls 7 depth else 0) +
(if name = "products" then 7^depth else 0) +
(if name = "linear_cells" then 18*Chapter4Math.strassenOverhead depth else 0) +
(if name = "copied_cells" then 12*Chapter4Math.strassenOverhead depth else 0)
end MatrixStrassenExecution
end
/-! Source: proofs/chapter4/StrassenDeterminism.lean -/
section
open Algo2LeanCore Algo2LeanGenerated
namespace MatrixStrassenDeterminism
set_option maxRecDepth 10000
set_option maxHeartbeats 4000000
/-- A private successor selector used only to prove determinism. Its arbitrary
value on stuck configurations is irrelevant: `step_selected` below checks
every actual generated transition against it. This avoids a quadratic
pairwise comparison of the generated instruction constructors. -/
noncomputable def selectedNext (before : Configuration) : Configuration :=
match before with
| .done _ _ => before
| .active h frame stack =>
match frame with
| .invalid => before
| .fn_matrix_linear_row pc s =>
if pc = 1 then (Algo2LeanCore.resumeConfig h (Result.fn_matrix_linear_row (s.t6)) stack) else
if pc = 2 then (.active h (Frame.fn_matrix_linear_row 1 { s with t6 := s.v4 }) stack) else
if pc = 3 then if s.t7 then (.active h (Frame.fn_matrix_linear_row 7 s) stack) else (.active h (Frame.fn_matrix_linear_row 2 s) stack) else
if pc = 4 then (.active h (Frame.fn_matrix_linear_row 3 { s with t7 := (decide ((s.v5 < s.v2))) }) stack) else
if pc = 5 then (.active h (Frame.fn_matrix_linear_row 4 { s with v5 := (s.v5 + (1 : Int)) }) stack) else
if pc = 6 then (.active (h.tick "linear_cells" 1) (Frame.fn_matrix_linear_row 5 s) stack) else
if pc = 7 then (.active (h.write s.v4 s.v5 ((h.read s.v0 s.v5) + (s.v3 * (h.read s.v1 s.v5)))) (Frame.fn_matrix_linear_row 6 s) stack) else
if pc = 8 then (.active h (Frame.fn_matrix_linear_row 4 { s with v5 := (0 : Int) }) stack) else
if pc = 9 then (.active h (Frame.fn_matrix_linear_row 8 { s with v4 := s.t8 }) stack) else
if pc = 10 then (.active (h.allocate (fun _ => s.t9)) (Frame.fn_matrix_linear_row 9 { s with t8 := h.nextRef }) stack) else
if pc = 11 then (.active h (Frame.fn_matrix_linear_row 10 { s with t9 := (0 : Int) }) stack) else
before
| .fn_matrix_linear pc s =>
if pc = 1 then (Algo2LeanCore.resumeConfig h (Result.fn_matrix_linear (s.t6)) stack) else
if pc = 2 then (.active h (Frame.fn_matrix_linear 1 { s with t6 := s.v4 }) stack) else
if pc = 3 then if s.t7 then (.active h (Frame.fn_matrix_linear 13 s) stack) else (.active h (Frame.fn_matrix_linear 2 s) stack) else
if pc = 4 then (.active h (Frame.fn_matrix_linear 3 { s with t7 := (decide ((s.v5 < s.v2))) }) stack) else
if pc = 5 then (.active h (Frame.fn_matrix_linear 4 { s with v5 := (s.v5 + (1 : Int)) }) stack) else
if pc = 6 then (.active (seq_Seq_Int.set h s.t10 s.t9 s.t8) (Frame.fn_matrix_linear 5 s) stack) else
if pc = 7 then (.active h (Frame.fn_matrix_linear 6 { s with t9 := s.v5 }) stack) else
if pc = 8 then (.active h (Frame.fn_matrix_linear 7 { s with t10 := s.v4 }) stack) else
if pc = 9 then (.active h (Frame.fn_matrix_linear_row 11 ({ v0 := s.t11, v1 := s.t12, v2 := s.t13, v3 := s.t14 } : State_matrix_linear_row)) ((fun value => match value with | .fn_matrix_linear_row result => (Frame.fn_matrix_linear 8 { s with t8 := result }) | _ => .invalid) :: stack)) else
if pc = 10 then (.active h (Frame.fn_matrix_linear 9 { s with t14 := s.v3 }) stack) else
if pc = 11 then (.active h (Frame.fn_matrix_linear 10 { s with t13 := s.v2 }) stack) else
if pc = 12 then (.active h (Frame.fn_matrix_linear 11 { s with t12 := ((seq_Seq_Int.get h s.v1 s.v5).getD 0) }) stack) else
if pc = 13 then (.active h (Frame.fn_matrix_linear 12 { s with t11 := ((seq_Seq_Int.get h s.v0 s.v5).getD 0) }) stack) else
if pc = 14 then (.active h (Frame.fn_matrix_linear 4 { s with v5 := (0 : Int) }) stack) else
if pc = 15 then (.active h (Frame.fn_matrix_linear 14 { s with v4 := s.t15 }) stack) else
if pc = 16 then (.active (seq_Seq_Int.const h s.t16).1 (Frame.fn_matrix_linear 15 { s with t15 := h.nextCollection }) stack) else
if pc = 17 then (.active (h.allocate (fun _ => s.t17)) (Frame.fn_matrix_linear 16 { s with t16 := h.nextRef }) stack) else
if pc = 18 then (.active h (Frame.fn_matrix_linear 17 { s with t17 := (0 : Int) }) stack) else
before
| .fn_matrix_quadrant_row pc s =>
if pc = 1 then (Algo2LeanCore.resumeConfig h (Result.fn_matrix_quadrant_row (s.t5)) stack) else
if pc = 2 then (.active h (Frame.fn_matrix_quadrant_row 1 { s with t5 := s.v3 }) stack) else
if pc = 3 then if s.t6 then (.active h (Frame.fn_matrix_quadrant_row 7 s) stack) else (.active h (Frame.fn_matrix_quadrant_row 2 s) stack) else
if pc = 4 then (.active h (Frame.fn_matrix_quadrant_row 3 { s with t6 := (decide ((s.v4 < s.v1))) }) stack) else
if pc = 5 then (.active h (Frame.fn_matrix_quadrant_row 4 { s with v4 := (s.v4 + (1 : Int)) }) stack) else
if pc = 6 then (.active (h.tick "copied_cells" 1) (Frame.fn_matrix_quadrant_row 5 s) stack) else
if pc = 7 then (.active (h.write s.v3 s.v4 (h.read s.v0 (s.v2 + s.v4))) (Frame.fn_matrix_quadrant_row 6 s) stack) else
if pc = 8 then (.active h (Frame.fn_matrix_quadrant_row 4 { s with v4 := (0 : Int) }) stack) else
if pc = 9 then (.active h (Frame.fn_matrix_quadrant_row 8 { s with v3 := s.t7 }) stack) else
if pc = 10 then (.active (h.allocate (fun _ => s.t8)) (Frame.fn_matrix_quadrant_row 9 { s with t7 := h.nextRef }) stack) else
if pc = 11 then (.active h (Frame.fn_matrix_quadrant_row 10 { s with t8 := (0 : Int) }) stack) else
before
| .fn_matrix_quadrant pc s =>
if pc = 1 then (Algo2LeanCore.resumeConfig h (Result.fn_matrix_quadrant (s.t7)) stack) else
if pc = 2 then (.active h (Frame.fn_matrix_quadrant 1 { s with t7 := s.v5 }) stack) else
if pc = 3 then if s.t8 then (.active h (Frame.fn_matrix_quadrant 12 s) stack) else (.active h (Frame.fn_matrix_quadrant 2 s) stack) else
if pc = 4 then (.active h (Frame.fn_matrix_quadrant 3 { s with t8 := (decide ((s.v6 < s.v2))) }) stack) else
if pc = 5 then (.active h (Frame.fn_matrix_quadrant 4 { s with v6 := (s.v6 + (1 : Int)) }) stack) else
if pc = 6 then (.active (seq_Seq_Int.set h s.t11 s.t10 s.t9) (Frame.fn_matrix_quadrant 5 s) stack) else
if pc = 7 then (.active h (Frame.fn_matrix_quadrant 6 { s with t10 := s.v6 }) stack) else
if pc = 8 then (.active h (Frame.fn_matrix_quadrant 7 { s with t11 := s.v5 }) stack) else
if pc = 9 then (.active h (Frame.fn_matrix_quadrant_row 11 ({ v0 := s.t12, v1 := s.t13, v2 := s.t14 } : State_matrix_quadrant_row)) ((fun value => match value with | .fn_matrix_quadrant_row result => (Frame.fn_matrix_quadrant 8 { s with t9 := result }) | _ => .invalid) :: stack)) else
if pc = 10 then (.active h (Frame.fn_matrix_quadrant 9 { s with t14 := s.v4 }) stack) else
if pc = 11 then (.active h (Frame.fn_matrix_quadrant 10 { s with t13 := s.v2 }) stack) else
if pc = 12 then (.active h (Frame.fn_matrix_quadrant 11 { s with t12 := ((seq_Seq_Int.get h s.v0 (s.v3 + s.v6)).getD 0) }) stack) else
if pc = 13 then (.active h (Frame.fn_matrix_quadrant 4 { s with v6 := (0 : Int) }) stack) else
if pc = 14 then (.active h (Frame.fn_matrix_quadrant 13 { s with v5 := s.t15 }) stack) else
if pc = 15 then (.active (seq_Seq_Int.const h s.t16).1 (Frame.fn_matrix_quadrant 14 { s with t15 := h.nextCollection }) stack) else
if pc = 16 then (.active (h.allocate (fun _ => s.t17)) (Frame.fn_matrix_quadrant 15 { s with t16 := h.nextRef }) stack) else
if pc = 17 then (.active h (Frame.fn_matrix_quadrant 16 { s with t17 := (0 : Int) }) stack) else
before
| .fn_matrix_join_row pc s =>
if pc = 1 then (Algo2LeanCore.resumeConfig h (Result.fn_matrix_join_row (s.t5)) stack) else
if pc = 2 then (.active h (Frame.fn_matrix_join_row 1 { s with t5 := s.v3 }) stack) else
if pc = 3 then if s.t6 then (.active h (Frame.fn_matrix_join_row 8 s) stack) else (.active h (Frame.fn_matrix_join_row 2 s) stack) else
if pc = 4 then (.active h (Frame.fn_matrix_join_row 3 { s with t6 := (decide ((s.v4 < s.v2))) }) stack) else
if pc = 5 then (.active h (Frame.fn_matrix_join_row 4 { s with v4 := (s.v4 + (1 : Int)) }) stack) else
if pc = 6 then (.active (h.tick "copied_cells" 2) (Frame.fn_matrix_join_row 5 s) stack) else
if pc = 7 then (.active (h.write s.v3 (s.v4 + s.v2) (h.read s.v1 s.v4)) (Frame.fn_matrix_join_row 6 s) stack) else
if pc = 8 then (.active (h.write s.v3 s.v4 (h.read s.v0 s.v4)) (Frame.fn_matrix_join_row 7 s) stack) else
if pc = 9 then (.active h (Frame.fn_matrix_join_row 4 { s with v4 := (0 : Int) }) stack) else
if pc = 10 then (.active h (Frame.fn_matrix_join_row 9 { s with v3 := s.t7 }) stack) else
if pc = 11 then (.active (h.allocate (fun _ => s.t8)) (Frame.fn_matrix_join_row 10 { s with t7 := h.nextRef }) stack) else
if pc = 12 then (.active h (Frame.fn_matrix_join_row 11 { s with t8 := (0 : Int) }) stack) else
before
| .fn_matrix_join pc s =>
if pc = 1 then (Algo2LeanCore.resumeConfig h (Result.fn_matrix_join (s.t7)) stack) else
if pc = 2 then (.active h (Frame.fn_matrix_join 1 { s with t7 := s.v5 }) stack) else
if pc = 3 then if s.t8 then (.active h (Frame.fn_matrix_join 19 s) stack) else (.active h (Frame.fn_matrix_join 2 s) stack) else
if pc = 4 then (.active h (Frame.fn_matrix_join 3 { s with t8 := (decide ((s.v6 < s.v4))) }) stack) else
if pc = 5 then (.active h (Frame.fn_matrix_join 4 { s with v6 := (s.v6 + (1 : Int)) }) stack) else
if pc = 6 then (.active (seq_Seq_Int.set h s.t11 s.t10 s.t9) (Frame.fn_matrix_join 5 s) stack) else
if pc = 7 then (.active h (Frame.fn_matrix_join 6 { s with t10 := (s.v6 + s.v4) }) stack) else
if pc = 8 then (.active h (Frame.fn_matrix_join 7 { s with t11 := s.v5 }) stack) else
if pc = 9 then (.active h (Frame.fn_matrix_join_row 12 ({ v0 := s.t12, v1 := s.t13, v2 := s.t14 } : State_matrix_join_row)) ((fun value => match value with | .fn_matrix_join_row result => (Frame.fn_matrix_join 8 { s with t9 := result }) | _ => .invalid) :: stack)) else
if pc = 10 then (.active h (Frame.fn_matrix_join 9 { s with t14 := s.v4 }) stack) else
if pc = 11 then (.active h (Frame.fn_matrix_join 10 { s with t13 := ((seq_Seq_Int.get h s.v3 s.v6).getD 0) }) stack) else
if pc = 12 then (.active h (Frame.fn_matrix_join 11 { s with t12 := ((seq_Seq_Int.get h s.v2 s.v6).getD 0) }) stack) else
if pc = 13 then (.active (seq_Seq_Int.set h s.t17 s.t16 s.t15) (Frame.fn_matrix_join 12 s) stack) else
if pc = 14 then (.active h (Frame.fn_matrix_join 13 { s with t16 := s.v6 }) stack) else
if pc = 15 then (.active h (Frame.fn_matrix_join 14 { s with t17 := s.v5 }) stack) else
if pc = 16 then (.active h (Frame.fn_matrix_join_row 12 ({ v0 := s.t18, v1 := s.t19, v2 := s.t20 } : State_matrix_join_row)) ((fun value => match value with | .fn_matrix_join_row result => (Frame.fn_matrix_join 15 { s with t15 := result }) | _ => .invalid) :: stack)) else
if pc = 17 then (.active h (Frame.fn_matrix_join 16 { s with t20 := s.v4 }) stack) else
if pc = 18 then (.active h (Frame.fn_matrix_join 17 { s with t19 := ((seq_Seq_Int.get h s.v1 s.v6).getD 0) }) stack) else
if pc = 19 then (.active h (Frame.fn_matrix_join 18 { s with t18 := ((seq_Seq_Int.get h s.v0 s.v6).getD 0) }) stack) else
if pc = 20 then (.active h (Frame.fn_matrix_join 4 { s with v6 := (0 : Int) }) stack) else
if pc = 21 then (.active h (Frame.fn_matrix_join 20 { s with v5 := s.t21 }) stack) else
if pc = 22 then (.active (seq_Seq_Int.const h s.t22).1 (Frame.fn_matrix_join 21 { s with t21 := h.nextCollection }) stack) else
if pc = 23 then (.active (h.allocate (fun _ => s.t23)) (Frame.fn_matrix_join 22 { s with t22 := h.nextRef }) stack) else
if pc = 24 then (.active h (Frame.fn_matrix_join 23 { s with t23 := (0 : Int) }) stack) else
before
| .fn_strassen pc s =>
if pc = 1 then (Algo2LeanCore.resumeConfig h (Result.fn_strassen (s.t25)) stack) else
if pc = 2 then (.active h (Frame.fn_strassen 1 { s with t25 := s.v3 }) stack) else
if pc = 3 then (.active (h.tick "products" 1) (Frame.fn_strassen 2 s) stack) else
if pc = 4 then (.active (h.write ((seq_Seq_Int.get h s.v3 (0 : Int)).getD 0) (0 : Int) ((h.read ((seq_Seq_Int.get h s.v0 (0 : Int)).getD 0) (0 : Int)) * (h.read ((seq_Seq_Int.get h s.v1 (0 : Int)).getD 0) (0 : Int)))) (Frame.fn_strassen 3 s) stack) else
if pc = 5 then (.active (seq_Seq_Int.set h s.t28 s.t27 s.t26) (Frame.fn_strassen 4 s) stack) else
if pc = 6 then (.active h (Frame.fn_strassen 5 { s with t27 := (0 : Int) }) stack) else
if pc = 7 then (.active h (Frame.fn_strassen 6 { s with t28 := s.v3 }) stack) else
if pc = 8 then (.active (h.allocate (fun _ => s.t29)) (Frame.fn_strassen 7 { s with t26 := h.nextRef }) stack) else
if pc = 9 then (.active h (Frame.fn_strassen 8 { s with t29 := (0 : Int) }) stack) else
if pc = 10 then (.active h (Frame.fn_strassen 9 { s with v3 := s.t30 }) stack) else
if pc = 11 then (.active (seq_Seq_Int.const h s.t31).1 (Frame.fn_strassen 10 { s with t30 := h.nextCollection }) stack) else
if pc = 12 then (.active (h.allocate (fun _ => s.t32)) (Frame.fn_strassen 11 { s with t31 := h.nextRef }) stack) else
if pc = 13 then (.active h (Frame.fn_strassen 12 { s with t32 := (0 : Int) }) stack) else
if pc = 14 then (Algo2LeanCore.resumeConfig h (Result.fn_strassen (s.t33)) stack) else
if pc = 15 then (.active h (Frame.fn_matrix_join 24 ({ v0 := s.t34, v1 := s.t35, v2 := s.t36, v3 := s.t37, v4 := s.t38 } : State_matrix_join)) ((fun value => match value with | .fn_matrix_join result => (Frame.fn_strassen 14 { s with t33 := result }) | _ => .invalid) :: stack)) else
if pc = 16 then (.active h (Frame.fn_strassen 15 { s with t38 := s.v4 }) stack) else
if pc = 17 then (.active h (Frame.fn_strassen 16 { s with t37 := s.v23 }) stack) else
if pc = 18 then (.active h (Frame.fn_strassen 17 { s with t36 := s.v22 }) stack) else
if pc = 19 then (.active h (Frame.fn_strassen 18 { s with t35 := s.v21 }) stack) else
if pc = 20 then (.active h (Frame.fn_strassen 19 { s with t34 := s.v20 }) stack) else
if pc = 21 then (.active h (Frame.fn_strassen 20 { s with v23 := s.t39 }) stack) else
if pc = 22 then (.active h (Frame.fn_matrix_linear 18 ({ v0 := s.t40, v1 := s.t41, v2 := s.t42, v3 := s.t43 } : State_matrix_linear)) ((fun value => match value with | .fn_matrix_linear result => (Frame.fn_strassen 21 { s with t39 := result }) | _ => .invalid) :: stack)) else
if pc = 23 then (.active h (Frame.fn_strassen 22 { s with t43 := (-(1 : Int)) }) stack) else
if pc = 24 then (.active h (Frame.fn_strassen 23 { s with t42 := s.v4 }) stack) else
if pc = 25 then (.active h (Frame.fn_strassen 24 { s with t41 := s.v19 }) stack) else
if pc = 26 then (.active h (Frame.fn_matrix_linear 18 ({ v0 := s.t44, v1 := s.t45, v2 := s.t46, v3 := s.t47 } : State_matrix_linear)) ((fun value => match value with | .fn_matrix_linear result => (Frame.fn_strassen 25 { s with t40 := result }) | _ => .invalid) :: stack)) else
if pc = 27 then (.active h (Frame.fn_strassen 26 { s with t47 := (-(1 : Int)) }) stack) else
if pc = 28 then (.active h (Frame.fn_strassen 27 { s with t46 := s.v4 }) stack) else
if pc = 29 then (.active h (Frame.fn_strassen 28 { s with t45 := s.v15 }) stack) else
if pc = 30 then (.active h (Frame.fn_matrix_linear 18 ({ v0 := s.t48, v1 := s.t49, v2 := s.t50, v3 := s.t51 } : State_matrix_linear)) ((fun value => match value with | .fn_matrix_linear result => (Frame.fn_strassen 29 { s with t44 := result }) | _ => .invalid) :: stack)) else
if pc = 31 then (.active h (Frame.fn_strassen 30 { s with t51 := (1 : Int) }) stack) else
if pc = 32 then (.active h (Frame.fn_strassen 31 { s with t50 := s.v4 }) stack) else
if pc = 33 then (.active h (Frame.fn_strassen 32 { s with t49 := s.v13 }) stack) else
if pc = 34 then (.active h (Frame.fn_strassen 33 { s with t48 := s.v17 }) stack) else
if pc = 35 then (.active h (Frame.fn_strassen 34 { s with v22 := s.t52 }) stack) else
if pc = 36 then (.active h (Frame.fn_matrix_linear 18 ({ v0 := s.t53, v1 := s.t54, v2 := s.t55, v3 := s.t56 } : State_matrix_linear)) ((fun value => match value with | .fn_matrix_linear result => (Frame.fn_strassen 35 { s with t52 := result }) | _ => .invalid) :: stack)) else
if pc = 37 then (.active h (Frame.fn_strassen 36 { s with t56 := (1 : Int) }) stack) else
if pc = 38 then (.active h (Frame.fn_strassen 37 { s with t55 := s.v4 }) stack) else
if pc = 39 then (.active h (Frame.fn_strassen 38 { s with t54 := s.v16 }) stack) else
if pc = 40 then (.active h (Frame.fn_strassen 39 { s with t53 := s.v15 }) stack) else
if pc = 41 then (.active h (Frame.fn_strassen 40 { s with v21 := s.t57 }) stack) else
if pc = 42 then (.active h (Frame.fn_matrix_linear 18 ({ v0 := s.t58, v1 := s.t59, v2 := s.t60, v3 := s.t61 } : State_matrix_linear)) ((fun value => match value with | .fn_matrix_linear result => (Frame.fn_strassen 41 { s with t57 := result }) | _ => .invalid) :: stack)) else
if pc = 43 then (.active h (Frame.fn_strassen 42 { s with t61 := (1 : Int) }) stack) else
if pc = 44 then (.active h (Frame.fn_strassen 43 { s with t60 := s.v4 }) stack) else
if pc = 45 then (.active h (Frame.fn_strassen 44 { s with t59 := s.v14 }) stack) else
if pc = 46 then (.active h (Frame.fn_strassen 45 { s with t58 := s.v13 }) stack) else
if pc = 47 then (.active h (Frame.fn_strassen 46 { s with v20 := s.t62 }) stack) else
if pc = 48 then (.active h (Frame.fn_matrix_linear 18 ({ v0 := s.t63, v1 := s.t64, v2 := s.t65, v3 := s.t66 } : State_matrix_linear)) ((fun value => match value with | .fn_matrix_linear result => (Frame.fn_strassen 47 { s with t62 := result }) | _ => .invalid) :: stack)) else
if pc = 49 then (.active h (Frame.fn_strassen 48 { s with t66 := (1 : Int) }) stack) else
if pc = 50 then (.active h (Frame.fn_strassen 49 { s with t65 := s.v4 }) stack) else
if pc = 51 then (.active h (Frame.fn_strassen 50 { s with t64 := s.v18 }) stack) else
if pc = 52 then (.active h (Frame.fn_matrix_linear 18 ({ v0 := s.t67, v1 := s.t68, v2 := s.t69, v3 := s.t70 } : State_matrix_linear)) ((fun value => match value with | .fn_matrix_linear result => (Frame.fn_strassen 51 { s with t63 := result }) | _ => .invalid) :: stack)) else
if pc = 53 then (.active h (Frame.fn_strassen 52 { s with t70 := (-(1 : Int)) }) stack) else
if pc = 54 then (.active h (Frame.fn_strassen 53 { s with t69 := s.v4 }) stack) else
if pc = 55 then (.active h (Frame.fn_strassen 54 { s with t68 := s.v14 }) stack) else
if pc = 56 then (.active h (Frame.fn_matrix_linear 18 ({ v0 := s.t71, v1 := s.t72, v2 := s.t73, v3 := s.t74 } : State_matrix_linear)) ((fun value => match value with | .fn_matrix_linear result => (Frame.fn_strassen 55 { s with t67 := result }) | _ => .invalid) :: stack)) else
if pc = 57 then (.active h (Frame.fn_strassen 56 { s with t74 := (1 : Int) }) stack) else
if pc = 58 then (.active h (Frame.fn_strassen 57 { s with t73 := s.v4 }) stack) else
if pc = 59 then (.active h (Frame.fn_strassen 58 { s with t72 := s.v16 }) stack) else
if pc = 60 then (.active h (Frame.fn_strassen 59 { s with t71 := s.v17 }) stack) else
if pc = 61 then (.active h (Frame.fn_strassen 60 { s with v19 := s.t75 }) stack) else
if pc = 62 then (.active h (Frame.fn_strassen 195 ({ v0 := s.t76, v1 := s.t77, v2 := s.t78 } : State_strassen)) ((fun value => match value with | .fn_strassen result => (Frame.fn_strassen 61 { s with t75 := result }) | _ => .invalid) :: stack)) else
if pc = 63 then (.active h (Frame.fn_strassen 62 { s with t78 := s.v4 }) stack) else
if pc = 64 then (.active h (Frame.fn_matrix_linear 18 ({ v0 := s.t79, v1 := s.t80, v2 := s.t81, v3 := s.t82 } : State_matrix_linear)) ((fun value => match value with | .fn_matrix_linear result => (Frame.fn_strassen 63 { s with t77 := result }) | _ => .invalid) :: stack)) else
if pc = 65 then (.active h (Frame.fn_strassen 64 { s with t82 := (1 : Int) }) stack) else
if pc = 66 then (.active h (Frame.fn_strassen 65 { s with t81 := s.v4 }) stack) else
if pc = 67 then (.active h (Frame.fn_strassen 66 { s with t80 := s.v10 }) stack) else
if pc = 68 then (.active h (Frame.fn_strassen 67 { s with t79 := s.v9 }) stack) else
if pc = 69 then (.active h (Frame.fn_matrix_linear 18 ({ v0 := s.t83, v1 := s.t84, v2 := s.t85, v3 := s.t86 } : State_matrix_linear)) ((fun value => match value with | .fn_matrix_linear result => (Frame.fn_strassen 68 { s with t76 := result }) | _ => .invalid) :: stack)) else
if pc = 70 then (.active h (Frame.fn_strassen 69 { s with t86 := (-(1 : Int)) }) stack) else
if pc = 71 then (.active h (Frame.fn_strassen 70 { s with t85 := s.v4 }) stack) else
if pc = 72 then (.active h (Frame.fn_strassen 71 { s with t84 := s.v7 }) stack) else
if pc = 73 then (.active h (Frame.fn_strassen 72 { s with t83 := s.v5 }) stack) else
if pc = 74 then (.active h (Frame.fn_strassen 73 { s with v18 := s.t87 }) stack) else
if pc = 75 then (.active h (Frame.fn_strassen 195 ({ v0 := s.t88, v1 := s.t89, v2 := s.t90 } : State_strassen)) ((fun value => match value with | .fn_strassen result => (Frame.fn_strassen 74 { s with t87 := result }) | _ => .invalid) :: stack)) else
if pc = 76 then (.active h (Frame.fn_strassen 75 { s with t90 := s.v4 }) stack) else
if pc = 77 then (.active h (Frame.fn_matrix_linear 18 ({ v0 := s.t91, v1 := s.t92, v2 := s.t93, v3 := s.t94 } : State_matrix_linear)) ((fun value => match value with | .fn_matrix_linear result => (Frame.fn_strassen 76 { s with t89 := result }) | _ => .invalid) :: stack)) else
if pc = 78 then (.active h (Frame.fn_strassen 77 { s with t94 := (1 : Int) }) stack) else
if pc = 79 then (.active h (Frame.fn_strassen 78 { s with t93 := s.v4 }) stack) else
if pc = 80 then (.active h (Frame.fn_strassen 79 { s with t92 := s.v12 }) stack) else
if pc = 81 then (.active h (Frame.fn_strassen 80 { s with t91 := s.v11 }) stack) else
if pc = 82 then (.active h (Frame.fn_matrix_linear 18 ({ v0 := s.t95, v1 := s.t96, v2 := s.t97, v3 := s.t98 } : State_matrix_linear)) ((fun value => match value with | .fn_matrix_linear result => (Frame.fn_strassen 81 { s with t88 := result }) | _ => .invalid) :: stack)) else
if pc = 83 then (.active h (Frame.fn_strassen 82 { s with t98 := (-(1 : Int)) }) stack) else
if pc = 84 then (.active h (Frame.fn_strassen 83 { s with t97 := s.v4 }) stack) else
if pc = 85 then (.active h (Frame.fn_strassen 84 { s with t96 := s.v8 }) stack) else
if pc = 86 then (.active h (Frame.fn_strassen 85 { s with t95 := s.v6 }) stack) else
if pc = 87 then (.active h (Frame.fn_strassen 86 { s with v17 := s.t99 }) stack) else
if pc = 88 then (.active h (Frame.fn_strassen 195 ({ v0 := s.t100, v1 := s.t101, v2 := s.t102 } : State_strassen)) ((fun value => match value with | .fn_strassen result => (Frame.fn_strassen 87 { s with t99 := result }) | _ => .invalid) :: stack)) else
if pc = 89 then (.active h (Frame.fn_strassen 88 { s with t102 := s.v4 }) stack) else
if pc = 90 then (.active h (Frame.fn_matrix_linear 18 ({ v0 := s.t103, v1 := s.t104, v2 := s.t105, v3 := s.t106 } : State_matrix_linear)) ((fun value => match value with | .fn_matrix_linear result => (Frame.fn_strassen 89 { s with t101 := result }) | _ => .invalid) :: stack)) else
if pc = 91 then (.active h (Frame.fn_strassen 90 { s with t106 := (1 : Int) }) stack) else
if pc = 92 then (.active h (Frame.fn_strassen 91 { s with t105 := s.v4 }) stack) else
if pc = 93 then (.active h (Frame.fn_strassen 92 { s with t104 := s.v12 }) stack) else
if pc = 94 then (.active h (Frame.fn_strassen 93 { s with t103 := s.v9 }) stack) else
if pc = 95 then (.active h (Frame.fn_matrix_linear 18 ({ v0 := s.t107, v1 := s.t108, v2 := s.t109, v3 := s.t110 } : State_matrix_linear)) ((fun value => match value with | .fn_matrix_linear result => (Frame.fn_strassen 94 { s with t100 := result }) | _ => .invalid) :: stack)) else
if pc = 96 then (.active h (Frame.fn_strassen 95 { s with t110 := (1 : Int) }) stack) else
if pc = 97 then (.active h (Frame.fn_strassen 96 { s with t109 := s.v4 }) stack) else
if pc = 98 then (.active h (Frame.fn_strassen 97 { s with t108 := s.v8 }) stack) else
if pc = 99 then (.active h (Frame.fn_strassen 98 { s with t107 := s.v5 }) stack) else
if pc = 100 then (.active h (Frame.fn_strassen 99 { s with v16 := s.t111 }) stack) else
if pc = 101 then (.active h (Frame.fn_strassen 195 ({ v0 := s.t112, v1 := s.t113, v2 := s.t114 } : State_strassen)) ((fun value => match value with | .fn_strassen result => (Frame.fn_strassen 100 { s with t111 := result }) | _ => .invalid) :: stack)) else
if pc = 102 then (.active h (Frame.fn_strassen 101 { s with t114 := s.v4 }) stack) else
if pc = 103 then (.active h (Frame.fn_matrix_linear 18 ({ v0 := s.t115, v1 := s.t116, v2 := s.t117, v3 := s.t118 } : State_matrix_linear)) ((fun value => match value with | .fn_matrix_linear result => (Frame.fn_strassen 102 { s with t113 := result }) | _ => .invalid) :: stack)) else
if pc = 104 then (.active h (Frame.fn_strassen 103 { s with t118 := (-(1 : Int)) }) stack) else
if pc = 105 then (.active h (Frame.fn_strassen 104 { s with t117 := s.v4 }) stack) else
if pc = 106 then (.active h (Frame.fn_strassen 105 { s with t116 := s.v9 }) stack) else
if pc = 107 then (.active h (Frame.fn_strassen 106 { s with t115 := s.v11 }) stack) else
if pc = 108 then (.active h (Frame.fn_strassen 107 { s with t112 := s.v8 }) stack) else
if pc = 109 then (.active h (Frame.fn_strassen 108 { s with v15 := s.t119 }) stack) else
if pc = 110 then (.active h (Frame.fn_strassen 195 ({ v0 := s.t120, v1 := s.t121, v2 := s.t122 } : State_strassen)) ((fun value => match value with | .fn_strassen result => (Frame.fn_strassen 109 { s with t119 := result }) | _ => .invalid) :: stack)) else
if pc = 111 then (.active h (Frame.fn_strassen 110 { s with t122 := s.v4 }) stack) else
if pc = 112 then (.active h (Frame.fn_strassen 111 { s with t121 := s.v9 }) stack) else
if pc = 113 then (.active h (Frame.fn_matrix_linear 18 ({ v0 := s.t123, v1 := s.t124, v2 := s.t125, v3 := s.t126 } : State_matrix_linear)) ((fun value => match value with | .fn_matrix_linear result => (Frame.fn_strassen 112 { s with t120 := result }) | _ => .invalid) :: stack)) else
if pc = 114 then (.active h (Frame.fn_strassen 113 { s with t126 := (1 : Int) }) stack) else
if pc = 115 then (.active h (Frame.fn_strassen 114 { s with t125 := s.v4 }) stack) else
if pc = 116 then (.active h (Frame.fn_strassen 115 { s with t124 := s.v8 }) stack) else
if pc = 117 then (.active h (Frame.fn_strassen 116 { s with t123 := s.v7 }) stack) else
if pc = 118 then (.active h (Frame.fn_strassen 117 { s with v14 := s.t127 }) stack) else
if pc = 119 then (.active h (Frame.fn_strassen 195 ({ v0 := s.t128, v1 := s.t129, v2 := s.t130 } : State_strassen)) ((fun value => match value with | .fn_strassen result => (Frame.fn_strassen 118 { s with t127 := result }) | _ => .invalid) :: stack)) else
if pc = 120 then (.active h (Frame.fn_strassen 119 { s with t130 := s.v4 }) stack) else
if pc = 121 then (.active h (Frame.fn_strassen 120 { s with t129 := s.v12 }) stack) else
if pc = 122 then (.active h (Frame.fn_matrix_linear 18 ({ v0 := s.t131, v1 := s.t132, v2 := s.t133, v3 := s.t134 } : State_matrix_linear)) ((fun value => match value with | .fn_matrix_linear result => (Frame.fn_strassen 121 { s with t128 := result }) | _ => .invalid) :: stack)) else
if pc = 123 then (.active h (Frame.fn_strassen 122 { s with t134 := (1 : Int) }) stack) else
if pc = 124 then (.active h (Frame.fn_strassen 123 { s with t133 := s.v4 }) stack) else
if pc = 125 then (.active h (Frame.fn_strassen 124 { s with t132 := s.v6 }) stack) else
if pc = 126 then (.active h (Frame.fn_strassen 125 { s with t131 := s.v5 }) stack) else
if pc = 127 then (.active h (Frame.fn_strassen 126 { s with v13 := s.t135 }) stack) else
if pc = 128 then (.active h (Frame.fn_strassen 195 ({ v0 := s.t136, v1 := s.t137, v2 := s.t138 } : State_strassen)) ((fun value => match value with | .fn_strassen result => (Frame.fn_strassen 127 { s with t135 := result }) | _ => .invalid) :: stack)) else
if pc = 129 then (.active h (Frame.fn_strassen 128 { s with t138 := s.v4 }) stack) else
if pc = 130 then (.active h (Frame.fn_matrix_linear 18 ({ v0 := s.t139, v1 := s.t140, v2 := s.t141, v3 := s.t142 } : State_matrix_linear)) ((fun value => match value with | .fn_matrix_linear result => (Frame.fn_strassen 129 { s with t137 := result }) | _ => .invalid) :: stack)) else
if pc = 131 then (.active h (Frame.fn_strassen 130 { s with t142 := (-(1 : Int)) }) stack) else
if pc = 132 then (.active h (Frame.fn_strassen 131 { s with t141 := s.v4 }) stack) else
if pc = 133 then (.active h (Frame.fn_strassen 132 { s with t140 := s.v12 }) stack) else
if pc = 134 then (.active h (Frame.fn_strassen 133 { s with t139 := s.v10 }) stack) else
if pc = 135 then (.active h (Frame.fn_strassen 134 { s with t136 := s.v5 }) stack) else
if pc = 136 then (.active h (Frame.fn_strassen 135 { s with v12 := s.t143 }) stack) else
if pc = 137 then (.active h (Frame.fn_matrix_quadrant 17 ({ v0 := s.t144, v1 := s.t145, v2 := s.t146, v3 := s.t147, v4 := s.t148 } : State_matrix_quadrant)) ((fun value => match value with | .fn_matrix_quadrant result => (Frame.fn_strassen 136 { s with t143 := result }) | _ => .invalid) :: stack)) else
if pc = 138 then (.active h (Frame.fn_strassen 137 { s with t148 := s.v4 }) stack) else
if pc = 139 then (.active h (Frame.fn_strassen 138 { s with t147 := s.v4 }) stack) else
if pc = 140 then (.active h (Frame.fn_strassen 139 { s with t146 := s.v4 }) stack) else
if pc = 141 then (.active h (Frame.fn_strassen 140 { s with t145 := s.v2 }) stack) else
if pc = 142 then (.active h (Frame.fn_strassen 141 { s with t144 := s.v1 }) stack) else
if pc = 143 then (.active h (Frame.fn_strassen 142 { s with v11 := s.t149 }) stack) else
if pc = 144 then (.active h (Frame.fn_matrix_quadrant 17 ({ v0 := s.t150, v1 := s.t151, v2 := s.t152, v3 := s.t153, v4 := s.t154 } : State_matrix_quadrant)) ((fun value => match value with | .fn_matrix_quadrant result => (Frame.fn_strassen 143 { s with t149 := result }) | _ => .invalid) :: stack)) else
if pc = 145 then (.active h (Frame.fn_strassen 144 { s with t154 := (0 : Int) }) stack) else
if pc = 146 then (.active h (Frame.fn_strassen 145 { s with t153 := s.v4 }) stack) else
if pc = 147 then (.active h (Frame.fn_strassen 146 { s with t152 := s.v4 }) stack) else
if pc = 148 then (.active h (Frame.fn_strassen 147 { s with t151 := s.v2 }) stack) else
if pc = 149 then (.active h (Frame.fn_strassen 148 { s with t150 := s.v1 }) stack) else
if pc = 150 then (.active h (Frame.fn_strassen 149 { s with v10 := s.t155 }) stack) else
if pc = 151 then (.active h (Frame.fn_matrix_quadrant 17 ({ v0 := s.t156, v1 := s.t157, v2 := s.t158, v3 := s.t159, v4 := s.t160 } : State_matrix_quadrant)) ((fun value => match value with | .fn_matrix_quadrant result => (Frame.fn_strassen 150 { s with t155 := result }) | _ => .invalid) :: stack)) else
if pc = 152 then (.active h (Frame.fn_strassen 151 { s with t160 := s.v4 }) stack) else
if pc = 153 then (.active h (Frame.fn_strassen 152 { s with t159 := (0 : Int) }) stack) else
if pc = 154 then (.active h (Frame.fn_strassen 153 { s with t158 := s.v4 }) stack) else
if pc = 155 then (.active h (Frame.fn_strassen 154 { s with t157 := s.v2 }) stack) else
if pc = 156 then (.active h (Frame.fn_strassen 155 { s with t156 := s.v1 }) stack) else
if pc = 157 then (.active h (Frame.fn_strassen 156 { s with v9 := s.t161 }) stack) else
if pc = 158 then (.active h (Frame.fn_matrix_quadrant 17 ({ v0 := s.t162, v1 := s.t163, v2 := s.t164, v3 := s.t165, v4 := s.t166 } : State_matrix_quadrant)) ((fun value => match value with | .fn_matrix_quadrant result => (Frame.fn_strassen 157 { s with t161 := result }) | _ => .invalid) :: stack)) else
if pc = 159 then (.active h (Frame.fn_strassen 158 { s with t166 := (0 : Int) }) stack) else
if pc = 160 then (.active h (Frame.fn_strassen 159 { s with t165 := (0 : Int) }) stack) else
if pc = 161 then (.active h (Frame.fn_strassen 160 { s with t164 := s.v4 }) stack) else
if pc = 162 then (.active h (Frame.fn_strassen 161 { s with t163 := s.v2 }) stack) else
if pc = 163 then (.active h (Frame.fn_strassen 162 { s with t162 := s.v1 }) stack) else
if pc = 164 then (.active h (Frame.fn_strassen 163 { s with v8 := s.t167 }) stack) else
if pc = 165 then (.active h (Frame.fn_matrix_quadrant 17 ({ v0 := s.t168, v1 := s.t169, v2 := s.t170, v3 := s.t171, v4 := s.t172 } : State_matrix_quadrant)) ((fun value => match value with | .fn_matrix_quadrant result => (Frame.fn_strassen 164 { s with t167 := result }) | _ => .invalid) :: stack)) else
if pc = 166 then (.active h (Frame.fn_strassen 165 { s with t172 := s.v4 }) stack) else
if pc = 167 then (.active h (Frame.fn_strassen 166 { s with t171 := s.v4 }) stack) else
if pc = 168 then (.active h (Frame.fn_strassen 167 { s with t170 := s.v4 }) stack) else
if pc = 169 then (.active h (Frame.fn_strassen 168 { s with t169 := s.v2 }) stack) else
if pc = 170 then (.active h (Frame.fn_strassen 169 { s with t168 := s.v0 }) stack) else
if pc = 171 then (.active h (Frame.fn_strassen 170 { s with v7 := s.t173 }) stack) else
if pc = 172 then (.active h (Frame.fn_matrix_quadrant 17 ({ v0 := s.t174, v1 := s.t175, v2 := s.t176, v3 := s.t177, v4 := s.t178 } : State_matrix_quadrant)) ((fun value => match value with | .fn_matrix_quadrant result => (Frame.fn_strassen 171 { s with t173 := result }) | _ => .invalid) :: stack)) else
if pc = 173 then (.active h (Frame.fn_strassen 172 { s with t178 := (0 : Int) }) stack) else
if pc = 174 then (.active h (Frame.fn_strassen 173 { s with t177 := s.v4 }) stack) else
if pc = 175 then (.active h (Frame.fn_strassen 174 { s with t176 := s.v4 }) stack) else
if pc = 176 then (.active h (Frame.fn_strassen 175 { s with t175 := s.v2 }) stack) else
if pc = 177 then (.active h (Frame.fn_strassen 176 { s with t174 := s.v0 }) stack) else
if pc = 178 then (.active h (Frame.fn_strassen 177 { s with v6 := s.t179 }) stack) else
if pc = 179 then (.active h (Frame.fn_matrix_quadrant 17 ({ v0 := s.t180, v1 := s.t181, v2 := s.t182, v3 := s.t183, v4 := s.t184 } : State_matrix_quadrant)) ((fun value => match value with | .fn_matrix_quadrant result => (Frame.fn_strassen 178 { s with t179 := result }) | _ => .invalid) :: stack)) else
if pc = 180 then (.active h (Frame.fn_strassen 179 { s with t184 := s.v4 }) stack) else
if pc = 181 then (.active h (Frame.fn_strassen 180 { s with t183 := (0 : Int) }) stack) else
if pc = 182 then (.active h (Frame.fn_strassen 181 { s with t182 := s.v4 }) stack) else
if pc = 183 then (.active h (Frame.fn_strassen 182 { s with t181 := s.v2 }) stack) else
if pc = 184 then (.active h (Frame.fn_strassen 183 { s with t180 := s.v0 }) stack) else
if pc = 185 then (.active h (Frame.fn_strassen 184 { s with v5 := s.t185 }) stack) else
if pc = 186 then (.active h (Frame.fn_matrix_quadrant 17 ({ v0 := s.t186, v1 := s.t187, v2 := s.t188, v3 := s.t189, v4 := s.t190 } : State_matrix_quadrant)) ((fun value => match value with | .fn_matrix_quadrant result => (Frame.fn_strassen 185 { s with t185 := result }) | _ => .invalid) :: stack)) else
if pc = 187 then (.active h (Frame.fn_strassen 186 { s with t190 := (0 : Int) }) stack) else
if pc = 188 then (.active h (Frame.fn_strassen 187 { s with t189 := (0 : Int) }) stack) else
if pc = 189 then (.active h (Frame.fn_strassen 188 { s with t188 := s.v4 }) stack) else
if pc = 190 then (.active h (Frame.fn_strassen 189 { s with t187 := s.v2 }) stack) else
if pc = 191 then (.active h (Frame.fn_strassen 190 { s with t186 := s.v0 }) stack) else
if pc = 192 then (.active h (Frame.fn_strassen 191 { s with v4 := (Int.fdiv s.v2 (2 : Int)) }) stack) else
if pc = 193 then if s.t24 then (.active h (Frame.fn_strassen 13 s) stack) else (.active h (Frame.fn_strassen 192 s) stack) else
if pc = 194 then (.active h (Frame.fn_strassen 193 { s with t24 := (decide ((s.v2 ≤ (1 : Int)))) }) stack) else
if pc = 195 then (.active (h.tick "calls" 1) (Frame.fn_strassen 194 s) stack) else
before
end MatrixStrassenDeterminism
end
/-! Source: proofs/chapter4/StrassenTheorems.lean -/
section
open Algo2LeanCore Algo2LeanGenerated
open Algo2LeanCore.MatrixHeap
open MatrixStrassenExecution
open StrassenValues (strassenValue )
namespace MatrixStrassenVerified
-- Main result: Correctness
-- Main result: Running time
end MatrixStrassenVerified
end
end CLRS