Bounded execution of fraction normalization
ProvedLax109476Proofs.RamArithmetic.normalizeFraction_spec_nativealgorithmscomputational-complexitygraph-theory
Let be natural numbers with , . Starting with numerator and denominator in the rational registers, the normalization command divides both by . It terminates in at most instructions and leaves
This is a reusable source interface for composing the complete finite-program implementation.
Preamble
import Definitions.Def_EdgeSublinearMWIS_Main_NativeDetailedInterfaces namespace Lax109476Proofs.RamArithmetic end Lax109476Proofs.RamArithmetic
Formal statement
theorem Lax109476Proofs.RamArithmetic.normalizeFraction_spec_native : ∀ (B n d : Nat),
@LT.lt Nat instLTNat n B →
@LT.lt Nat instLTNat d B →
@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 "rat.n") n) (@Eq Nat (σ.vars "rat.d") d))
Lax109476Proofs.RamArithmetic.normalizeFraction
(fun (x σ' : Lax808846Proofs.Imp.Env) =>
And (@Eq Nat (σ'.vars "rat.n") (@HDiv.hDiv Nat Nat Nat (@instHDiv Nat Nat.instDiv) n (n.gcd d)))
(@Eq Nat (σ'.vars "rat.d") (@HDiv.hDiv Nat Nat Nat (@instHDiv Nat Nat.instDiv) d (n.gcd 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 16) (instOfNatNat (nat_lit 16)))) := by sorrySource