Initialize the stored rational ellipsoid state
ProvedLax109476Proofs.RamInitialState.initialState_spec_nativealgorithmscomputational-complexitygraph-theory
Let be a natural dimension and suppose , and . From the complete center, shape and ellipsoid workspace extents, with the dimension register equal to , the fixed initialization command stores
It retains the workspace and dimension and runs in at most instructions. The empty dimension is included under the same guards.
Preamble
import Definitions.Def_EdgeSublinearMWIS_Main_NativeBoundsInterfaces namespace Lax109476Proofs.RamInitialState end Lax109476Proofs.RamInitialState
Formal statement
theorem Lax109476Proofs.RamInitialState.initialState_spec_native : ∀ (B n : Nat),
@LT.lt Nat instLTNat n B →
@LT.lt Nat instLTNat (@HMul.hMul Nat Nat Nat (@instHMul Nat instMulNat) n n) B →
@LT.lt Nat instLTNat (@OfNat.ofNat Nat (nat_lit 1) (instOfNatNat (nat_lit 1))) B →
Lax808846Proofs.Reasoning.Spec B
(fun (σ : Lax808846Proofs.Imp.Env) =>
And (Lax109476Proofs.RamEllipsoidStep.Extents "ell.center" n σ)
(And
(Lax109476Proofs.RamEllipsoidStep.Extents "ell.shape"
(@HMul.hMul Nat Nat Nat (@instHMul Nat instMulNat) n n) σ)
(And (Lax109476Proofs.RamEllipsoidStep.Workspace n σ) (@Eq Nat (σ.vars "vec.n") n))))
Lax109476Proofs.RamInitialState.initialState
(fun (x τ : Lax808846Proofs.Imp.Env) =>
And
(Lax109476Proofs.RamRationalArrays.Represents "ell.center"
(@List.ofFn Rat n
(@OfNat.ofNat (Fin n → Rat) (nat_lit 0)
(@Zero.toOfNat0 (Fin n → Rat)
(@Pi.instZero (Fin n) (fun (a : Fin n) => Rat) fun (i : Fin n) =>
@MulZeroClass.toZero Rat (@instMulZeroClassOfSemiring Rat Rat.semiring)))))
τ)
(And
(Lax109476Proofs.RamRationalArrays.Represents "ell.shape"
(@Lax109476Proofs.RamMatrixStorage.flatten n n
(@OfNat.ofNat (Matrix (Fin n) (Fin n) Rat) (nat_lit 1)
(@One.toOfNat1 (Matrix (Fin n) (Fin n) Rat)
(@Matrix.one (Fin n) Rat (instDecidableEqFin n)
(@MulZeroClass.toZero Rat (@instMulZeroClassOfSemiring Rat Rat.semiring))
(@AddMonoidWithOne.toOne Rat
(@AddGroupWithOne.toAddMonoidWithOne Rat
(@Ring.toAddGroupWithOne Rat (@DivisionRing.toRing Rat Rat.instDivisionRing))))))))
τ)
(And (Lax109476Proofs.RamEllipsoidStep.Workspace n τ)
(And (@Eq Nat (τ.vars "vec.n") n)
(@Eq Nat (τ.vars "iter.k") (@OfNat.ofNat Nat (nat_lit 0) (instOfNatNat (nat_lit 0))))))))
(@HAdd.hAdd Nat Nat Nat (@instHAdd Nat instAddNat)
(@HAdd.hAdd Nat Nat Nat (@instHAdd Nat instAddNat)
(@HMul.hMul Nat Nat Nat (@instHMul Nat instMulNat)
(@OfNat.ofNat Nat (nat_lit 33) (instOfNatNat (nat_lit 33))) n)
(@HMul.hMul Nat Nat Nat (@instHMul Nat instMulNat)
(@OfNat.ofNat Nat (nat_lit 76) (instOfNatNat (nat_lit 76)))
(@HMul.hMul Nat Nat Nat (@instHMul Nat instMulNat) n n)))
(@OfNat.ofNat Nat (nat_lit 56) (instOfNatNat (nat_lit 56)))) := by sorrySource