library colibrilib.modulo — module Divisiblemodule Divisible12use bool.Bool3use colibrilib.q.Z as Z4use colibrilib.q.Q as Q5use int.Int6use real.RealInfix7use real.Truncate8use real.FromInt910exception FinitePositiveExpected11Valid (128ms) (cvc4)12let lemma round_modulo (a:real) (m:real): unit13requires { 0. <. m }14ensures { 0. <=. a -. from_int (floor (a /. m )) *. m <. m }15ensures { let r = from_int (floor (a /. m )) *. m in16r <. a -> forall q. not (r <. (from_int q) *. m <=. a) }17=18let d = a /. m in19let t = floor d in20let f = from_int t in21assert { f <=. d <. from_int (t + 1) }2223predicate ddivisible_using (a b:real) (d:int) =24a = (from_int d) *. b2526predicate ddivisible (a b: real) =27exists d. ddivisible_using a b d28Valid (57ms) (colibri2)29let round_down_to (a:Q.t) (m:Q.t) : (r:Q.t,ghost q':int)30requires { (0. <. Q.real m ) }31ensures { ddivisible_using r m q' }32ensures { Q.( r <= a) }33ensures { Q.(0. <=. (a.real -. r.real) <. m.real) }34ensures { Q.( r.real <. a.real) -> forall q. not Q.(r.real <. (from_int q) *. m.real <=. a.real ) }35=36if Q.(a = (Q.of_int 0)) then a,037else begin38round_modulo pure { a.Q.real } pure { m.Q.real };39
it is surely possible to improve this computation
let q' = Q.(floor (a / m)) in41let r = Q.(of_int q' * m) in42r, q'43end44Valid (3.7s) (colibri2 3) (cvc5 2) (split_vc 2) (depth 2)45let round_up_to (a:Q.t) (m:Q.t) : (r:Q.t,ghost q':int)46requires { 0. <. Q.real m }47ensures { ddivisible_using r m q' }48ensures { Q.(a <= r) }49ensures { Q.(0. <=. (r.real -. a.real) <. m.real) }50ensures { Q.( a.real <. r.real) -> forall q. not Q.(a.real <=. (from_int q) *. m.real <. r.real ) }51=52let res,q' = round_down_to Q.((of_int 0) - a) m in53Q.((of_int 0) - res),(-q')54Valid (23ms) (colibri2)55let lemma simple_mul_div (a b : real)56requires { b <> 0. }57ensures { (a /. b) *. b = a } =58()59Valid (24ms) (colibri2)60let lemma remove_product_right (a b c:int) : unit61requires { b <> 0 }62requires { a * b = c * b }63ensures { a = c } =64()65Valid (43ms) (colibri2)66let lemma divisible_to_z (a b:Q.t) (d:int) : (dnum:int, dden: int)67requires { b.Q.real <> 0. }68requires { ddivisible_using a.Q.real b.Q.real d }69ensures { Z.ddivisible_using a.Q.num b.Q.num dnum }70ensures { Z.ddivisible_using b.Q.den a.Q.den dden }71ensures { d = dnum * dden } =72assert { b.Q.den * a.Q.num = d * b.Q.num * a.Q.den73by from_int b.Q.den *. from_int a.Q.num = from_int d *. from_int b.Q.num *. from_int a.Q.den74by (from_int a.Q.num /. from_int a.Q.den) *. from_int a.Q.den *. from_int b.Q.den = (from_int d *. (from_int b.Q.num /. from_int b.Q.den)) *. from_int a.Q.den *. from_int b.Q.den75by from_int a.Q.num /. from_int a.Q.den = from_int d *. (from_int b.Q.num /. from_int b.Q.den)76};77let dnum = Z.prime_to_one_another_mul b.Q.num (d * a.Q.den) b.Q.den a.Q.num in78assert { Z.ddivisible_using a.Q.num b.Q.num dnum };79let dden = Z.prime_to_one_another_mul a.Q.num b.Q.den a.Q.den (d * b.Q.num) in80assert { Z.ddivisible_using b.Q.den a.Q.den dden };81assert { dnum * dden * b.Q.num * a.Q.den = d * b.Q.num * a.Q.den };82remove_product_right (dnum * dden * b.Q.num) a.Q.den (d * b.Q.num);83remove_product_right (dnum * dden) b.Q.num d;84(dnum,dden)85Valid (43ms) (colibri2)86let lemma divisible_from_z (a b:Q.t) (dnum:int) (dden:int) : unit87requires { Z.ddivisible_using a.Q.num b.Q.num dnum }88requires { Z.ddivisible_using b.Q.den a.Q.den dden }89ensures { ddivisible_using a.Q.real b.Q.real (dnum*dden) }90=91ghost (simple_mul_div (from_int a.Q.num) (from_int a.Q.den);92simple_mul_div (from_int b.Q.num) (from_int b.Q.den););93let ghost d = dnum * dden in94assert { a.Q.real = (from_int d) *. b.Q.real95by from_int a.Q.num /. from_int a.Q.den = from_int d *. (from_int b.Q.num /. from_int b.Q.den)96by (from_int a.Q.num /. from_int a.Q.den) *. (from_int b.Q.den /. from_int b.Q.den) = from_int d *. (from_int b.Q.num /. from_int b.Q.den) *. (from_int a.Q.den /. from_int a.Q.den)97by (from_int a.Q.num *. from_int b.Q.den) /. from_int a.Q.den /. from_int b.Q.den = (from_int d *. from_int b.Q.num *. from_int a.Q.den) /. from_int a.Q.den /. from_int b.Q.den98by from_int a.Q.num *. from_int b.Q.den = from_int d *. from_int b.Q.num *. from_int a.Q.den99by from_int a.Q.num *. from_int b.Q.den = from_int dnum *. from_int dden *. from_int b.Q.num *. from_int a.Q.den100by from_int a.Q.num *. from_int b.Q.den = from_int (dnum * b.Q.num) *. from_int (dden * a.Q.den)101}102Valid (115ms) (cvc4)103let divisible (a:Q.t) (b:Q.t) : (r:bool,ghost d: int)104ensures { not r -> forall d. not (ddivisible_using a.Q.real b.Q.real d) }105ensures { r -> ddivisible_using a.Q.real b.Q.real d } =106if Int.(=) b.Q.num 0 then107(Int.(=) a.Q.num 0, ghost 0)108else109let b1,dnum = Z.divisible a.Q.num b.Q.num in110if b1 then111let b2,dden = Z.divisible b.Q.den a.Q.den in112if b2 then113(true,dnum*dden)114else begin115let ghost () = if pure { exists d. ddivisible_using a.Q.real b.Q.real d } then116let d = any (d:int) ensures { ddivisible_using a.Q.real b.Q.real d } in117let _dnum, dden = divisible_to_z a b d in118assert { Z.ddivisible_using a.Q.den b.Q.den dden };119absurd120in121(false,ghost 0)122end123else begin124let ghost () = if pure { exists d. ddivisible_using a.Q.real b.Q.real d } then125let d = any (d:int) ensures { ddivisible_using a.Q.real b.Q.real d } in126let dnum, _dden = divisible_to_z a b d in127assert { Z.ddivisible_using a.Q.num b.Q.num dnum };128absurd129in130(false,ghost 0)131end132Valid (351ms) (colibri2)133let mult_cst_divisible (a:Q.t) (q:Q.t) : (a':Q.t)134ensures { forall r. ddivisible r a.Q.real -> ddivisible (r *. q.Q.real ) a'.Q.real } =135let a' = Q.(a*q) in136let lemma post (r:real) : unit137requires { ddivisible r a.Q.real }138ensures { ddivisible (r *. q.Q.real) a'.Q.real } =139let d = any int ensures { ddivisible_using r a.Q.real result } in140assert {ddivisible_using (r *. q.Q.real) a'.Q.real d }141in142a'143144end145