Bounded execution of signed rational addition
ProvedLax109476Proofs.RamRational.addFraction_spec_nativealgorithmscomputational-complexitygraph-theory
Let , where , and . Assume and that the operand registers contain these signed fractions. The fixed command returns a reduced representation of the exact result in at most instructions:
This is a reusable source interface for composing the complete finite-program implementation.
Preamble
import Definitions.Def_EdgeSublinearMWIS_Main_NativeDetailedInterfaces namespace Lax109476Proofs.RamRational end Lax109476Proofs.RamRational
Formal statement
theorem Lax109476Proofs.RamRational.addFraction_spec_native : ∀ (B M s₁ n₁ d₁ s₂ n₂ 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 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 n₂ 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 (Lax109476Proofs.RamRational.fractionInputs s₁ n₁ d₁ s₂ n₂ d₂)
Lax109476Proofs.RamRational.addFraction
(fun (x σ' : Lax808846Proofs.Imp.Env) =>
Lax109476Proofs.RamRational.FractionOutput
(@HAdd.hAdd Rat Rat Rat (@instHAdd Rat Rat.instAdd)
(Lax109476Proofs.RamRational.fractionValue s₁ n₁ d₁)
(Lax109476Proofs.RamRational.fractionValue s₂ n₂ 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)))
(@HMul.hMul Nat Nat Nat (@instHMul Nat instMulNat) d₁ d₂).size)
(@OfNat.ofNat Nat (nat_lit 96) (instOfNatNat (nat_lit 96)))) := by sorrySource