Bounded execution of rational downward grid rounding
ProvedLax109476Proofs.RamRounding.roundFraction_spec_nativealgorithmscomputational-complexitygraph-theory
Let , with , and . Under , the operand and grid registers specify a fixed command returning downward rounding to the grid. Its cost is at most :
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.roundFraction_spec_native : ∀ (B M s n d D : Nat),
@LT.lt Nat instLTNat
(@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)))
(@HPow.hPow Nat Nat Nat (@instHPow Nat Nat (@NPow.toPow Nat (@Monoid.toNPow Nat Nat.instMonoid))) M
(@OfNat.ofNat Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))))
(@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.roundFraction
(fun (x σ' : Lax808846Proofs.Imp.Env) =>
Lax109476Proofs.RamRational.FractionOutput
(Lax109476Proofs.RationalRounding.roundDown (Lax109476Proofs.RamRational.fractionValue s n d) D)
σ')
(@HAdd.hAdd Nat Nat Nat (@instHAdd Nat instAddNat)
(@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 96) (instOfNatNat (nat_lit 96)))) := by sorrySource