Bounded execution of fraction normalization
OpenLax109476Proofs.RamArithmetic.normalizeFraction_specalgorithmscomputational-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.
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.RamArithmetic.normalizeFraction_spec_native.
Preamble
import Definitions.Def_EdgeSublinearMWIS_Main_NativeDetailedInterfaces
Formal statement
namespace Lax109476Proofs.RamArithmetic
theorem normalizeFraction_spec : ∀ (B n d : Nat),
Nat.lt n B →
Nat.lt d B →
Nat.lt ((0:Nat)) 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))))
(Nat.add
(Nat.mul
((36:Nat)) d.size)
((16:Nat))) := by sorry
end Lax109476Proofs.RamArithmetic
Source