Bounded execution of the rational upper-root routine
ProvedLax109476Proofs.RamRounding.upperRootFraction_spec_nativealgorithmscomputational-complexitygraph-theory
Let , where , and . Under and initialized operand/grid registers, the fixed upper-root command returns as a reduced fraction. Here
This is a reusable source interface for composing the complete finite-program implementation.
Preamble
import Definitions.Def_EdgeSublinearMWIS_Main_NativeDetailedInterfaces namespace Lax109476Proofs.RamRounding end Lax109476Proofs.RamRounding
Formal statement
theorem Lax109476Proofs.RamRounding.upperRootFraction_spec_native : ∀ (B M s n d D : Nat),
@LT.lt Nat instLTNat
(@HAdd.hAdd Nat Nat Nat (@instHAdd Nat instAddNat)
(@HAdd.hAdd Nat Nat Nat (@instHAdd Nat instAddNat)
(@HPow.hPow Nat Nat Nat (@instHPow Nat Nat (@NPow.toPow Nat (@Monoid.toNPow Nat Nat.instMonoid)))
(@HAdd.hAdd Nat Nat Nat (@instHAdd Nat instAddNat)
(@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)
(@HPow.hPow Nat Nat Nat (@instHPow Nat Nat (@NPow.toPow Nat (@Monoid.toNPow Nat Nat.instMonoid))) M
(@OfNat.ofNat Nat (nat_lit 3) (instOfNatNat (nat_lit 3))))
(@OfNat.ofNat Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))))
(@OfNat.ofNat Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(@OfNat.ofNat Nat (nat_lit 2) (instOfNatNat (nat_lit 2))))
(@HPow.hPow Nat Nat Nat (@instHPow Nat Nat (@NPow.toPow Nat (@Monoid.toNPow Nat Nat.instMonoid))) M
(@OfNat.ofNat Nat (nat_lit 3) (instOfNatNat (nat_lit 3)))))
(@OfNat.ofNat Nat (nat_lit 3) (instOfNatNat (nat_lit 3))))
B →
@LE.le Nat instLENat s (@OfNat.ofNat Nat (nat_lit 1) (instOfNatNat (nat_lit 1))) →
@LE.le Nat instLENat n M →
@LE.le Nat instLENat d M →
@LE.le Nat instLENat D M →
@LT.lt Nat instLTNat (@OfNat.ofNat Nat (nat_lit 0) (instOfNatNat (nat_lit 0))) d →
@LT.lt Nat instLTNat (@OfNat.ofNat Nat (nat_lit 0) (instOfNatNat (nat_lit 0))) D →
Lax808846Proofs.Reasoning.Spec B
(fun (σ : Lax808846Proofs.Imp.Env) =>
And (@Eq Nat (σ.vars "left.s") s)
(And (@Eq Nat (σ.vars "left.n") n)
(And (@Eq Nat (σ.vars "left.d") d) (@Eq Nat (σ.vars "grid.D") D))))
Lax109476Proofs.RamRounding.upperRootFraction
(fun (x σ' : Lax808846Proofs.Imp.Env) =>
Lax109476Proofs.RamRational.FractionOutput
(Lax109476Proofs.RationalRounding.sqrtUpper (Lax109476Proofs.RamRational.fractionValue s n d) D)
σ')
(@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 26) (instOfNatNat (nat_lit 26)))
(Lax109476Proofs.RamRounding.upperMagnitude s n d D).size)
(@HMul.hMul Nat Nat Nat (@instHMul Nat instMulNat)
(@OfNat.ofNat Nat (nat_lit 36) (instOfNatNat (nat_lit 36))) D.size))
(@OfNat.ofNat Nat (nat_lit 128) (instOfNatNat (nat_lit 128)))) := by sorrySource