Compute the native root envelope and workspace budget
ProvedLax263307Proofs.NativeRootBudget.command_spec_nativealgorithmscomputational-complexitygraph-theory
Let be natural numbers, with . Write , , , and . Suppose the complete arithmetic guard
From stored , one fixed command computes resource , rounding width and recursion stride while preserving . Its instruction bound is
Thus these resource quantities are calculated by the program itself.
Preamble
import Definitions.Def_EdgeSublinearMWIS_Main_NativePhaseInterfaces namespace Lax263307Proofs.NativeRootBudget end Lax263307Proofs.NativeRootBudget
Formal statement
theorem Lax263307Proofs.NativeRootBudget.command_spec_native : ∀ (B C d Q e n D : Nat),
@LT.lt Nat instLTNat (@OfNat.ofNat Nat (nat_lit 0) (instOfNatNat (nat_lit 0))) n →
@LT.lt Nat instLTNat (@OfNat.ofNat Nat (nat_lit 0) (instOfNatNat (nat_lit 0))) D →
@LT.lt Nat instLTNat (Lax263307Proofs.NativeRootBudget.guard C d Q e n D) B →
Lax808846Proofs.Reasoning.Spec B
(fun (σ : Lax808846Proofs.Imp.Env) => And (@Eq Nat (σ.vars "graph.n") n) (@Eq Nat (σ.vars "node.D") D))
(Lax263307Proofs.NativeRootBudget.command C d Q e)
(fun (x τ : Lax808846Proofs.Imp.Env) =>
And (@Eq Nat (τ.vars "graph.n") n)
(And (@Eq Nat (τ.vars "node.D") D)
(And (@Eq Nat (τ.vars "algorithm.resource") (Lax263307Proofs.NativeRootResource.envelope C d n D))
(And (@Eq Nat (τ.vars "algorithm.roundWidth") (Lax263307Proofs.NativeRootResource.budget Q e C d n D))
(@Eq Nat (τ.vars "recursion.stride")
(@HMul.hMul Nat Nat Nat (@instHMul Nat instMulNat)
(@OfNat.ofNat Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))
(@HAdd.hAdd Nat Nat Nat (@instHAdd Nat instAddNat)
(Lax263307Proofs.NativeRootResource.budget Q e C d n D)
(@OfNat.ofNat Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))))))))
(@HAdd.hAdd Nat Nat Nat (@instHAdd Nat instAddNat)
(@HAdd.hAdd Nat Nat Nat (@instHAdd Nat instAddNat)
(@HAdd.hAdd Nat Nat Nat (@instHAdd Nat instAddNat)
(@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 12) (instOfNatNat (nat_lit 12))) n.size)
(@HMul.hMul Nat Nat Nat (@instHMul Nat instMulNat)
(@OfNat.ofNat Nat (nat_lit 12) (instOfNatNat (nat_lit 12)))
(@HMul.hMul Nat Nat Nat (@instHMul Nat instMulNat)
(@OfNat.ofNat Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) n).size))
(@HMul.hMul Nat Nat Nat (@instHMul Nat instMulNat)
(@OfNat.ofNat Nat (nat_lit 12) (instOfNatNat (nat_lit 12))) d))
(@HMul.hMul Nat Nat Nat (@instHMul Nat instMulNat)
(@OfNat.ofNat Nat (nat_lit 12) (instOfNatNat (nat_lit 12)))
(@HMul.hMul Nat Nat Nat (@instHMul Nat instMulNat) C
(@HPow.hPow Nat Nat Nat (@instHPow Nat Nat (@NPow.toPow Nat (@Monoid.toNPow Nat Nat.instMonoid)))
(@HMul.hMul Nat Nat Nat (@instHMul Nat instMulNat) D (Lax263307.AlgorithmParameters.logarithm n))
d))))
(@HMul.hMul Nat Nat Nat (@instHMul Nat instMulNat)
(@OfNat.ofNat Nat (nat_lit 12) (instOfNatNat (nat_lit 12))) e))
(@OfNat.ofNat Nat (nat_lit 78) (instOfNatNat (nat_lit 78)))) := by sorrySource