Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Value and heap-effect specifications for Strassen matrix multiplication

Definition
CLRS_Chapter4_Algo2LeanExamples_MatrixStrassen

by Chutong · Oct 11, 2026 · Mathlib 0df444a (Lean v4.33.1)

algo2leanalgo2lean-clrs-chapter4-fd33cf9algorithmsclrsrunning-timetextbook

This 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.

Definition code
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
Source
Algo2Lean Chapter 4 development, module Algo2LeanExamples.MatrixStrassen, immutable source fd33cf959b39f9e4a9fcfda4ef31d5a36b784d41: https://github.com/chutongyang98/Lean_formalization/blob/fd33cf959b39f9e4a9fcfda4ef31d5a36b784d41/examples/matrix_strassen.algo; https://github.com/chutongyang98/Lean_formalization/blob/fd33cf959b39f9e4a9fcfda4ef31d5a36b784d41/examples/analysis/matrix_strassen.lean

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me