Bounded execution of the rational upper-root routine
OpenLax109476Proofs.RamRounding.upperRootFraction_specalgorithmscomputational-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.
Retired because the namespace-wrapped declaration compiled during publication but the proof-comparison parser rejects that header (expected token / unknown full theorem identifier). The mathematically identical, fully qualified declaration is Lax109476Proofs.RamRounding.upperRootFraction_spec_native.
Preamble
import Definitions.Def_EdgeSublinearMWIS_Main_NativeDetailedInterfaces
Formal statement
namespace Lax109476Proofs.RamRounding
theorem upperRootFraction_spec : ∀ (B M s n d D : Nat),
Nat.lt
(Nat.add
(Nat.add
(@HPow.hPow Nat Nat Nat (@instHPow Nat Nat (@NPow.toPow Nat (@Monoid.toNPow Nat Nat.instMonoid)))
(Nat.add
(Nat.mul
((2:Nat))
(Nat.add
(@HPow.hPow Nat Nat Nat (@instHPow Nat Nat (@NPow.toPow Nat (@Monoid.toNPow Nat Nat.instMonoid))) M
((3:Nat)))
((2:Nat))))
((1:Nat)))
((2:Nat)))
(@HPow.hPow Nat Nat Nat (@instHPow Nat Nat (@NPow.toPow Nat (@Monoid.toNPow Nat Nat.instMonoid))) M
((3:Nat))))
((3:Nat)))
B →
Nat.le s ((1:Nat)) →
Nat.le n M →
Nat.le d M →
Nat.le D M →
Nat.lt ((0:Nat)) d →
Nat.lt ((0:Nat)) 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)
σ')
(Nat.add
(Nat.add
(Nat.mul
((26:Nat))
(Lax109476Proofs.RamRounding.upperMagnitude s n d D).size)
(Nat.mul
((36:Nat)) D.size))
((128:Nat))) := by sorry
end Lax109476Proofs.RamRounding
Source