Bounded execution of signed rational multiplication
OpenLax109476Proofs.RamRational.multiplyFraction_specalgorithmscomputational-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.
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.RamRational.multiplyFraction_spec_native.
Preamble
import Definitions.Def_EdgeSublinearMWIS_Main_NativeDetailedInterfaces
Formal statement
namespace Lax109476Proofs.RamRational
theorem multiplyFraction_spec : ∀ (B M s₁ n₁ d₁ s₂ n₂ d₂ : Nat),
Nat.lt
(Nat.add
(Nat.mul ((2:Nat))
(@HPow.hPow Nat Nat Nat (@instHPow Nat Nat (@NPow.toPow Nat (@Monoid.toNPow Nat Nat.instMonoid))) M
((2:Nat))))
((3:Nat)))
B →
Nat.le s₁ ((1:Nat)) →
Nat.le s₂ ((1:Nat)) →
Nat.le n₁ M →
Nat.le d₁ M →
Nat.le n₂ M →
Nat.le d₂ M →
Nat.lt ((0:Nat)) d₁ →
Nat.lt ((0:Nat)) d₂ →
Lax808846Proofs.Reasoning.Spec B (Lax109476Proofs.RamRational.fractionInputs s₁ n₁ d₁ s₂ n₂ d₂)
Lax109476Proofs.RamRational.multiplyFraction
(fun (x σ' : Lax808846Proofs.Imp.Env) =>
Lax109476Proofs.RamRational.FractionOutput
(@HMul.hMul Rat Rat Rat (@instHMul Rat Rat.instMul)
(Lax109476Proofs.RamRational.fractionValue s₁ n₁ d₁)
(Lax109476Proofs.RamRational.fractionValue s₂ n₂ d₂))
σ')
(Nat.add
(Nat.mul
((36:Nat))
(Nat.mul d₁ d₂).size)
((64:Nat))) := by sorry
end Lax109476Proofs.RamRational
Source