library colibrilib.union_congr — module UnionCongrcongruence class
The value { c; u } is the set of the reals of the union u (colibrilib/union.mlw) that are in the class c (colibrilib/congruence.mlw), when there is one. It is the domain Dom_interval.D of colibri2 (colibri2/theories/LRA/stages/stage2/union.ml calls these functions).
The specifications have the shapes of colibrilib/spec.mlw, on the membership mem.
module UnionCongr12use int.Int13use real.RealInfix14use real.FromInt15use real.Abs16use real.Truncate17use option.Option18use list.List19use set.Set as S20use colibrilib.bound.Bound21use colibrilib.spec.Sound22use colibrilib.spec.Opt23use colibrilib.dv.Dv24use colibrilib.dv.RealSets25use colibrilib.q.Real as Real26use colibrilib.stdq.StdQ as Q27use colibrilib.stda.StdA as A28use colibrilib.union.Union29use colibrilib.congruence.Congruence as C30use colibrilib.congruence.Export as CE31use real.Square32use real.MinMax33
type t = { c: option C.t; u: Make.t }3738predicate memc (x: real) (c: option C.t) =39match c with None -> true | Some c -> C.member x c end40
x is in the domain t
predicate mem (x: real) (t: t) = Make.memt x t.u /\ memc x t.c43
Valid (251ms) (colibri2)let reals () : t47ensures { exact mem (fun _ -> true) result }48= { c = None; u = { Make.a = Make.On Make.Inf } }49Valid (399ms) (colibri2)50let integers () : t51ensures { exact mem (fun x -> Real.is_integer x) result }52= { c = Some (C.integers ()); u = { Make.a = Make.On Make.Inf } }53Valid (371ms) (colibri2)54let singleton (q: A.t) : t55ensures { exact mem (fun x -> x = A.real q) result }56= { c = Some (C.singleton q); u = Make.singleton q }57Valid (46ms) (colibri2)58let zero () : t59ensures { exact mem (fun x -> x = 0.0) result }60= singleton (A.of_int 0)61Valid (40ms) (colibri2)62let of_congruence (c: C.t) : t63ensures { exact mem (fun x -> C.member x c) result }64= { c = Some c; u = { Make.a = Make.On Make.Inf } }65Valid (274ms) (colibri2)66let gt (q: A.t) : t67ensures { exact mem (fun x -> A.real q <. x) result }68= { c = None; u = Make.gt q }69Valid (303ms) (colibri2)70let ge (q: A.t) : t71ensures { exact mem (fun x -> A.real q <=. x) result }72= { c = None; u = Make.ge q }73Valid (41ms) (colibri2)74let lt (q: A.t) : t75ensures { exact mem (fun x -> x <. A.real q) result }76= { c = None; u = Make.lt q }77Valid (246ms) (colibri2)78let le (q: A.t) : t79ensures { exact mem (fun x -> x <=. A.real q) result }80= { c = None; u = Make.le q }81
The reals above (resp. below) a real of t
Valid (234ms) (colibri2)let gt' (t: t) : t84ensures { sound_rel mem (>.) t result }85= { c = None; u = Make.gt' t.u }86Valid (245ms) (colibri2)87let ge' (t: t) : t88ensures { sound_rel mem (>=.) t result }89= { c = None; u = Make.ge' t.u }90Valid (253ms) (colibri2)91let lt' (t: t) : t92ensures { sound_rel mem (<.) t result }93= { c = None; u = Make.lt' t.u }94Valid (214ms) (colibri2)95let le' (t: t) : t96ensures { sound_rel mem (<=.) t result }97= { c = None; u = Make.le' t.u }98
The members of an integral class are integers
Valid (238ms) (colibri2)let ghost integral_mem (c: C.t) : unit101requires { C.integral c }102ensures { forall x. C.member x c -> Real.is_integer x }103= assert { forall x. C.member x c -> S.mem x (C.gamma c) }104
Valid (261ms) (colibri2)let mem_a (x: A.t) (t: t) : bool108ensures { result <-> mem (A.real x) t }109= Make.mem x t.u && match t.c with None -> true | Some c -> C.mem x c end110
Only integers
Valid (756ms) (cvc5)let is_integer (t: t) : bool113ensures { result -> forall x. mem x t -> Real.is_integer x }114= match t.c with None -> false | Some c -> C.is_integer c end115
All the reals
Valid (38ms) (colibri2)let is_reals (t: t) : bool118ensures { result -> forall x. mem x t }119= match t.c, t.u.Make.a with None, Make.On Make.Inf -> true | _ -> false end120
At most the real q
Valid (322ms) (colibri2)let is_singleton (t: t) : option A.t123ensures { match result with124| Some q -> forall x. mem x t -> x = A.real q125| None -> true end }126= match t.c with127| Some c ->128match C.is_singleton c with129| Some q -> Some q130| None -> let (o, _, _) = Make.is_singleton t.u in o131end132| None -> let (o, _, _) = Make.is_singleton t.u in o133end134Valid (2.3s) (colibri2 2) (cvc4) (cvc5) (split_vc 2) (depth 2)135let is_included (a b: t) : bool136ensures { result -> forall x. mem x a -> mem x b }137= (match a.c, b.c with138| Some c1, Some c2 -> C.is_included c1 c2139| _, None -> true140| None, Some _ -> false141end) &&142Make.for_all (fun x y -> if x then y else true) a.u b.u143Valid (835ms) (cvc4)144let is_distinct (a b: t) : bool145ensures { result -> forall x. mem x a -> not (mem x b) }146= Make.for_all (fun x y -> not (x && y)) a.u b.u147
u by the classTwo members of a class differ by at least |div|
Valid (229ms) (colibri2 7) (cvc4) (cvc5) (split_vc 2) (depth 2)let ghost gap (r x d: real) : unit152requires { dv (r -. x) d /\ d <> 0.0 /\ r <. x }153ensures { r <=. x -. abs d }154= {proof…}155let k = quot (r -. x) d in156if d >. 0.0 then begin157assert { from_int k <. 0.0 by from_int k *. d <. 0.0 };158assert { from_int k <=. -. 1.0 };159assert { from_int k *. d <=. -. d by (from_int k +. 1.0) *. d <=. 0.0 };160end else begin161assert { from_int k >. 0.0 by from_int k *. d <. 0.0 };162assert { from_int k >=. 1.0 };163assert { from_int k *. d <=. d }164end165{qed}166
The members of the class c next to a member x
Valid (317ms) (colibri2)let ghost next (c: C.t) (x: real) : unit169requires { C.member x c /\ Q.real c.C.div <> 0.0 }170ensures { C.member (x -. Q.real c.C.div) c /\ C.member (x +. Q.real c.C.div) c }171ensures { forall r. C.member r c -> r <. x -> r <=. x -. abs (Q.real c.C.div) }172ensures { forall r. C.member r c -> x <. r -> x +. abs (Q.real c.C.div) <=. r }173= let d = Q.real c.C.div in174let rm = A.real c.C.rem in175dv_self d;176dv_sub (x -. rm) d d;177dv_add (x -. rm) d d;178let lemma below (r: real) requires { C.member r c /\ r <. x } ensures { r <=. x -. abs d }179= dv_sub (r -. rm) (x -. rm) d; gap r x d in180let lemma above (r: real) requires { C.member r c /\ x <. r } ensures { x +. abs d <=. r }181= dv_sub (x -. rm) (r -. rm) d; gap x r d in182()183
The members of c in u; c is not a singleton
Valid (979ms) (colibri2 26) (cvc5 2) (split_vc 9) (depth 3)let reduce_congruence_nz (c: C.t) (u: Make.t) : option t186requires { Q.real c.C.div <> 0.0 }187ensures { restrict Make.memt (fun x -> C.member x c) u188(match result with None -> None | Some r -> Some r.u end) }189ensures { match result with Some r -> r.c = Some c | None -> true end }190= let floorb (x: A.t) (b: Bound.t) : A.t191ensures { C.member (A.real result) c }192ensures { Make.cmp result b x }193ensures { forall r. Make.cmp r b x -> A.real result <. r -> not (C.member r c) }194= let x' = C.floor_a_nz x c in195{proof…} next c (A.real x'); {qed}196match b with197| Bound.Large -> x'198| Bound.Strict ->199if A.equal x x' then200(if Q.lt (Q.of_int 0) c.C.div then A.sub x' (A.of_q c.C.div) else A.add x' (A.of_q c.C.div))201else x'202end in203let ceilb (x: A.t) (b: Bound.t) : A.t204ensures { C.member (A.real result) c }205ensures { Make.cmp x b result }206ensures { forall r. Make.cmp x b r -> r <. A.real result -> not (C.member r c) }207= let x' = C.ceil_a_nz x c in208{proof…} next c (A.real x'); {qed}209match b with210| Bound.Large -> x'211| Bound.Strict ->212if A.equal x x' then213(if Q.lt (Q.of_int 0) c.C.div then A.add x' (A.of_q c.C.div) else A.sub x' (A.of_q c.C.div))214else x'215end in216let op = { Make.red_min = Make.I; Make.red_is_in = (fun x -> C.member x c);217Make.red_is_integer = (fun x -> C.mem x c);218Make.red_floorb = floorb; Make.red_ceilb = ceilb } in219match Make.reduce_generic op u with220| None -> None221| Some u -> Some { c = Some c; u = u }222end223
The members of c in u
Valid (275ms) (colibri2 3) (split_vc 2) (depth 2)let reduce_congruence (c: C.t) (u: Make.t) : option t226ensures { forall x. Make.memt x u -> C.member x c ->227match result with None -> false | Some r -> mem x r end }228= match C.is_singleton c with229| None -> reduce_congruence_nz c u230| Some q -> if Make.mem q u then Some { c = Some c; u = Make.singleton q } else None231end232
The integers of t
Valid (1.2s) (colibri2 2) (cvc4) (split_vc 3) (depth 3)let reduce_integers (t: t) : option t235ensures { restrict mem (fun x -> Real.is_integer x) t result }236= match t.c with237| None -> reduce_congruence (C.integers ()) t.u238| Some c ->239match C.reduce_integers c with240| None -> None241| Some c -> reduce_congruence c t.u242end243end244
Valid (1.4s) (colibri2 7) (cvc4) (split_vc 3) (depth 3)let inter (a b: t) : option t248ensures { restrict mem (fun x -> mem x b) a result }249= let inter_u (c: option C.t) (u1 u2: Make.t) : option t250ensures { exact_opt mem (fun x -> Make.memt x u1 /\ Make.memt x u2 /\ memc x c) result }251= match Make.inter u1 u2 with None -> None | Some u -> Some { c = c; u = u } end in252match a.c, b.c with253| Some ca, None ->254if C.is_integer ca then begin255{proof…} integral_mem ca; {qed}256match Make.reduce_integers b.u with257| None -> None258| Some u2 -> inter_u a.c a.u u2259end end260else inter_u a.c a.u b.u261| None, Some cb ->262if C.is_integer cb then begin263{proof…} integral_mem cb; {qed}264match Make.reduce_integers a.u with265| None -> None266| Some u1 -> inter_u b.c u1 b.u267end end268else inter_u b.c a.u b.u269| None, None ->270match inter_u None a.u b.u with271| None -> None272| Some r ->273match r.u.Make.a with274| Make.Off (Make.Sin q Make.Inf) -> Some { c = Some (C.singleton q); u = r.u }275| _ -> Some r276end277end278| Some c1, Some c2 ->279match C.inter c1 c2 with280| None -> None281| Some cc -> inter_u (Some cc) a.u b.u282end283end284Valid (2.8s) (colibri2 3) (cvc5) (split_vc 3) (depth 3)285let union (a b: t) : t286ensures { forall x. mem x a \/ mem x b -> mem x result }287= let c = match a.c, b.c with288| Some c1, Some c2 -> match C.union c1 c2 with C.Top -> None | C.R c -> Some c end289| _ -> None290end in291{ c = c; u = Make.union a.u b.u }292
t without q
Valid (3.1s) (colibri2 4) (cvc5) (split_vc 5) (depth 5)let except (t: t) (q: A.t) : option t295ensures { restrict mem (fun x -> x <> A.real q) t result }296= match t.c with297| Some ct ->298if not (C.mem q ct) then Some t299else match Make.except t.u q with300| None -> None301| Some u ->302if C.is_integer ct then303match Make.reduce_integers u with304| None -> None305| Some u -> Some { c = t.c; u = u }306end307else Some { c = t.c; u = u }308end309| None ->310match Make.except t.u q with311| None -> None312| Some u -> Some { c = None; u = u }313end314end315
The reals not in t: exact without a class, or when u is a singleton of the class; else all the reals (the complement of a class is not a class)
Valid (294ms) (colibri2 8) (split_vc 8) (depth 5)let complement (t: t) : option t320ensures { forall x. not (mem x t) ->321match result with None -> false | Some r -> mem x r end }322= let ex = match t.c with323| None -> true324| Some ct -> let (o, _, _) = Make.is_singleton t.u in325match o with Some q -> C.mem q ct | None -> false end326end in327if ex then328match Make.complement t.u with329| None -> None330| Some u -> Some { c = None; u = u }331end332else Some (reals ())333
Valid (378ms) (colibri2)let ghost image_c (f: real -> real) (a r: C.t) : unit337requires { S.subset (image f (C.gamma a)) (C.gamma r) }338ensures { forall x. C.member x a -> C.member (f x) r }339= assert { forall x. C.member x a -> S.mem (f x) (image f (C.gamma a)) }340Valid (280ms) (colibri2)341let ghost preimage_c (f: real -> real) (a r: C.t) : unit342requires { S.subset (preimage f (C.gamma a)) (C.gamma r) }343ensures { forall x. C.member (f x) a -> C.member x r }344= assert { forall x. C.member (f x) a -> S.mem x (preimage f (C.gamma a)) }345Valid (741ms) (colibri2) (cvc5) (split_vc) (depth 1)346let ghost image2_c (f: real -> real -> real) (a b r: C.t) : unit347requires { S.subset (map2 f (C.gamma a) (C.gamma b)) (C.gamma r) }348ensures { forall x y. C.member x a -> C.member y b -> C.member (f x y) r }349= assert { forall x y. C.member x a -> C.member y b ->350S.mem (f x y) (map2 f (C.gamma a) (C.gamma b)) }351
The members x of the integral class i whose square is in c
Valid (812ms) (colibri2 4) (cvc5) (split_vc) (depth 1)let ghost square_c (i c r: C.t) : unit354requires { C.integral i }355requires { S.subset (S.inter C.ints (pre_mul (C.gamma i) (C.gamma c))) (C.gamma r) }356ensures { forall x. C.member x i -> C.member (x *. x) c -> C.member x r }357= integral_mem i;358assert { forall x. C.member x i -> S.mem x C.ints };359assert { forall x. C.member x i -> C.member (x *. x) c ->360S.mem x (pre_mul (C.gamma i) (C.gamma c))361by S.mem x (C.gamma i) /\ S.mem (x *. x) (C.gamma c) };362assert { forall x. C.member x i -> C.member (x *. x) c ->363S.mem x (S.inter C.ints (pre_mul (C.gamma i) (C.gamma c))) }364Valid (651ms) (colibri2) (cvc5) (split_vc) (depth 1)365let ghost image2nz_c (f: real -> real -> real) (a b r: C.t) : unit366requires { S.subset (map2nz f (C.gamma a) (C.gamma b)) (C.gamma r) }367ensures { forall x y. C.member x a -> C.member y b -> y <> 0.0 ->368C.member (f x y) r }369= assert { forall x y. C.member x a -> C.member y b -> y <> 0.0 ->370S.mem (f x y) (map2nz f (C.gamma a) (C.gamma b)) }371
The reals of a that are not in b: the complement of the union of b when the class of a is in the one of b, else a
Valid (632ms) (colibri2 5) (split_vc 3) (depth 3)let diff (a b: t) : option t375ensures { restrict mem (fun x -> not (mem x b)) a result }376= let inside = match a.c, b.c with377| _, None -> true378| Some ca, Some cb -> C.is_included ca cb379| None, Some _ -> false380end in381{proof…}382assert { inside -> forall x. memc x a.c -> memc x b.c383by forall x. memc x a.c -> S.mem x (match a.c with Some ca -> C.gamma ca | None -> S.all end) };384{qed}385if inside then386match Make.complement b.u with387| None -> None388| Some u -> inter a { c = None; u = u }389end390else Some a391
Valid (361ms) (colibri2)let from_convex_hull (h: Make.convex_hull) : option t395ensures { match result with396| Some r -> forall x. Make.in_hull x h -> mem x r397| None -> forall x. not (Make.in_hull x h) end }398= match Make.from_convex_hull h with None -> None | Some u -> Some { c = None; u = u } end399
The lower bound of the integers above the bound b
Valid (303ms) (colibri2)let int_lo (b: option (A.t, Bound.t)) : option (A.t, Bound.t)402ensures { forall x. Real.is_integer x -> Make.in_hull x (b, None) -> Make.in_hull x (result, None) }403= match b with404| None -> None405| Some (z, Bound.Strict) ->406if A.is_integer z then Some (A.add z (A.of_int 1), Bound.Large) else Some (A.of_bigint (A.ceil_z z), Bound.Large)407| Some (z, Bound.Large) -> if A.is_integer z then b else Some (A.of_bigint (A.ceil_z z), Bound.Large)408end409
The upper bound of the integers below the bound b
Valid (301ms) (colibri2)let int_hi (b: option (A.t, Bound.t)) : option (A.t, Bound.t)412ensures { forall x. Real.is_integer x -> Make.in_hull x (None, b) -> Make.in_hull x (None, result) }413= match b with414| None -> None415| Some (z, Bound.Strict) ->416if A.is_integer z then Some (A.sub z (A.of_int 1), Bound.Large) else Some (A.of_bigint (A.floor_z z), Bound.Large)417| Some (z, Bound.Large) -> if A.is_integer z then b else Some (A.of_bigint (A.floor_z z), Bound.Large)418end419
The bounds of t; integers when t has only integers
Valid (554ms) (colibri2) (split_vc) (depth 1)let get_convex_hull (t: t) : Make.convex_hull422ensures { forall x. mem x t -> Make.in_hull x result }423= let (lo, hi) = Make.get_convex_hull t.u in424if is_integer t then (int_lo lo, int_hi hi) else (lo, hi)425
enlarge big down up t replaces the bounds q of t with big q by down q (lower bounds) and up q (upper bounds), when they are on the right side of q
Valid (781ms) (colibri2)let enlarge (big: A.t -> bool) (down up: A.t -> A.t) (t: t) : t432ensures { forall x. mem x t -> mem x result }433= let dn (q: A.t) : A.t ensures { A.real result <=. A.real q }434= if big q then (let d = down q in if A.le d q then d else q) else q in435let upq (q: A.t) : A.t ensures { A.real q <=. A.real result }436= if big q then (let d = up q in if A.le q d then d else q) else q in437let lo (b: Make.Map.qbound) : Make.Map.qbound438ensures { forall r. Make.Map.cmp_inf_qbound b r -> Make.Map.cmp_inf_qbound result r }439= match b with440| Make.Map.BInf -> b441| Make.Map.BLarge q -> Make.Map.BLarge (dn q)442| Make.Map.BStrict q -> Make.Map.BStrict (dn q)443end in444let hi (b: Make.Map.qbound) : Make.Map.qbound445ensures { forall r. Make.Map.cmp_sup_qbound r b -> Make.Map.cmp_sup_qbound r result }446= match b with447| Make.Map.BInf -> b448| Make.Map.BLarge q -> Make.Map.BLarge (upq q)449| Make.Map.BStrict q -> Make.Map.BStrict (upq q)450end in451let f (i: Make.Map.interval) : Make.Map.res_interval452ensures { forall r. Make.Map.mem_interval r i -> Make.Map.mem_res_interval r result }453ensures { result <> Nil }454= match i with455| Make.Map.Singleton q ->456if big q then Cons (Make.Map.Inter (Make.Map.BLarge (dn q)) (Make.Map.BLarge (upq q))) Nil457else Cons i Nil458| Make.Map.Inter b1 b2 -> Cons (Make.Map.Inter (lo b1) (hi b2)) Nil459end in460{ c = t.c; u = Make.Map.Unary.map { Make.Map.Unary.f = f; Make.Map.Unary.fr = (fun x -> x) } t.u }461
Valid (1.8s) (cvc4)let neg (t: t) : t465ensures { sound1 mem (fun x -> -. x) t result }466= let c = match t.c with467| None -> None468| Some ct -> Some (C.neg_forward ct)469end in470{ c = c; u = Make.Increasing.Unary.neg t.u }471Valid (503ms) (colibri2 2) (split_vc) (depth 1)472let add (a b: t) : t473ensures { sound2 mem (fun x y -> x +. y) a b result }474= let c = match a.c, b.c with475| Some ca, Some cb ->476let r = C.add_forward ca cb in477{proof…} image2_c (fun x y -> x +. y) ca cb r; {qed}478Some r479| _ -> None480end in481{ c = c; u = Make.Increasing.Binary.add a.u b.u }482Valid (393ms) (colibri2 4) (split_vc 2) (depth 2)483let minus (a b: t) : t484ensures { sound2 mem (fun x y -> x -. y) a b result }485= let nb = neg b in486let r = add a nb in487{proof…}488assert { forall x y. mem x a -> mem y nb -> mem (x +. y) r };489assert { forall x y. mem x a -> mem y b -> mem (x -. y) r by x -. y = x +. (-. y) };490{qed}491r492Valid (635ms) (colibri2) (split_vc) (depth 1)493let add_cst (q: A.t) (t: t) : t494ensures { sound1 mem (fun x -> x +. A.real q) t result }495= let c = match t.c with496| None -> None497| Some ct -> Some (C.add_cst q ct)498end in499{ c = c; u = Make.Increasing.Binary.add_cst t.u q }500Valid (613ms) (colibri2 2) (split_vc 2) (depth 2)501let mult_cst (q: A.t) (t: t) : t502ensures { sound1 mem (fun x -> A.real q *. x) t result }503= let c = match t.c, A.view q with504| Some ct, A.Rat qq ->505let r = C.mul_cst qq ct in {proof…} image_c (fun x -> x *. Q.real qq) ct r; {qed} Some r506| _ -> None507end in508{ c = c; u = Make.Increasing.Unary.mult_cst q t.u }509Valid (686ms) (colibri2 2) (split_vc 2) (depth 2)510let mul (a b: t) : t511ensures { sound2 mem (fun x y -> x *. y) a b result }512= let c = match a.c, b.c with513| Some ca, Some cb ->514match C.mul_forward ca cb with515| C.Top -> None516| C.R r -> {proof…} image2_c (fun x y -> x *. y) ca cb r; {qed} Some r517end518| _ -> None519end in520{ c = c; u = Make.Increasing.Binary.mul a.u b.u }521Valid (273ms) (colibri2)522let inv (t: t) : t523ensures { sound1 mem (fun x -> 1.0 /. x) t result }524= { c = None; u = Make.Increasing.Binary.inv t.u }525Valid (272ms) (colibri2)526let div (a b: t) : t527ensures { sound2 mem (fun x y -> x /. y) a b result }528= { c = None; u = Make.Increasing.Binary.div a.u b.u }529
The x of into with x * y in r for a y of b
Valid (1.4s) (colibri2 13) (cvc5 2) (split_vc 8) (depth 5)let mul_backward (r: t) (into: option t) (b: t) : C.backward t532ensures { match result with533| C.R res -> forall x y. (match into with Some i -> mem x i | None -> true end) ->534mem y b -> mem (x *. y) r -> mem x res535| C.Top -> true end }536= if Make.mem (A.of_int 0) b.u then C.Top537else begin538let into_c = match into with None -> None | Some i -> i.c end in539let c = match r.c, b.c with540| Some cr, Some cb ->541match C.mul_backward cr into_c cb with542| C.Top -> None543| C.R res ->544{proof…}545match into_c with546| Some d ->547integral_mem d;548let lemma pm (x y: real) : unit549requires { C.member x d /\ C.member y cb /\ C.member (x *. y) cr }550ensures { C.member x res }551= assert { S.mem x C.ints };552assert { S.mem x (pre_mul (C.gamma cb) (C.gamma cr)) } in ()553| None -> ()554end;555{qed}556Some res557end558| _ -> None559end in560let u = Make.Increasing.Binary.div r.u b.u in561{proof…}562assert { forall x y. Make.memt y b.u -> Make.memt (x *. y) r.u -> Make.memt x u563by y <> 0.0 so (x *. y) /. y = x };564{qed}565C.R { c = c; u = u }566end567Valid (435ms) (colibri2 2) (split_vc) (depth 1)568let ceil (t: t) : t569ensures { sound1 mem (fun x -> from_int (Truncate.ceil x)) t result }570= let c = match t.c with571| None -> None572| Some ct ->573let r = C.ceil_forward ct in574{proof…} image_c (fun v -> from_int (Truncate.ceil v)) ct r; {qed}575Some r576end in577{ c = c; u = Make.NonIncreasing.ceil t.u }578Valid (435ms) (colibri2 2) (split_vc) (depth 1)579let floor (t: t) : t580ensures { sound1 mem (fun x -> from_int (Truncate.floor x)) t result }581= let c = match t.c with582| None -> None583| Some ct ->584let r = C.floor_forward ct in585{proof…} image_c (fun v -> from_int (Truncate.floor v)) ct r; {qed}586Some r587end in588{ c = c; u = Make.NonIncreasing.floor t.u }589Valid (571ms) (colibri2) (cvc4) (split_vc) (depth 1)590let truncate (t: t) : t591ensures { sound1 mem (fun x -> from_int (Truncate.truncate x)) t result }592= let c = match t.c with593| None -> None594| Some ct ->595let r = C.truncate_forward ct in596{proof…} image_c (fun v -> from_int (Truncate.truncate v)) ct r; {qed}597Some r598end in599{ c = c; u = Make.NonIncreasing.truncate t.u }600Valid (221ms) (colibri2 2) (split_vc 2) (depth 2)601let relu (t: t) : t602ensures { sound1 mem (fun x -> max 0.0 x) t result }603= let c = match t.c with604| None -> None605| Some ct ->606match C.relu_forward ct with607| C.Top -> None608| C.R r ->609{proof…} image_c (fun x -> if x <. 0.0 then 0.0 else x) ct r; {qed}610Some r611end612end in613{ c = c; u = Make.NonIncreasing.relu t.u }614Valid (374ms) (colibri2 2) (split_vc 2) (depth 2)615let abs_forward (t: t) : t616ensures { sound1 mem (fun x -> abs x) t result }617= let c = match t.c with618| None -> None619| Some ct ->620match C.abs_forward ct with621| C.Top -> None622| C.R r -> {proof…} image_c (fun x -> abs x) ct r; {qed} Some r623end624end in625{ c = c; u = Make.Increasing.abs_forward t.u }626Valid (384ms) (colibri2 2) (split_vc 2) (depth 2)627let abs_backward (t: t) : t628ensures { preimage1 mem (fun x -> abs x) t result }629= let c = match t.c with630| None -> None631| Some ct ->632match C.abs_backward ct with633| C.Top -> None634| C.R r -> {proof…} preimage_c (fun y -> abs y) ct r; {qed} Some r635end636end in637{ c = c; u = Make.Increasing.abs_backward t.u }638
The x of into with x * x in t
Valid (294ms) (colibri2 7) (split_vc) (depth 1)let square_backward (into: option t) (t: t) : option t641ensures { forall x. (match into with Some i -> mem x i | None -> true end) ->642mem (x *. x) t -> match result with None -> false | Some r -> mem x r end }643= match Make.square_backward t.u with644| None ->645{proof…}646assert { preimage1_opt Make.memt (fun (x:real) -> sqr x) t.u None };647assert { forall x. not Make.memt (sqr x) t.u };648{qed}649None650| Some u ->651{proof…}652assert { preimage1_opt Make.memt (fun (x:real) -> sqr x) t.u (Some u) };653assert { forall x. Make.memt (sqr x) t.u -> Make.memt x u };654{qed}655let c = match t.c, into with656| Some ct, Some i ->657match i.c with658| Some ic ->659match C.mul_backward ct (Some ic) ic with660| C.Top -> None661| C.R r ->662{proof…} square_c ic ct r; {qed}663Some r664end665| None -> None666end667| _ -> None668end in669Some { c = c; u = u }670end671
Valid (832ms) (colibri2 3) (split_vc 2) (depth 2)let div_e_forward (a b: t) : t675ensures { sound2 mem (fun x y -> from_int (Real.div_e x y)) a b result }676= if mem_a (A.of_int 0) b then reals ()677else begin678let c = match a.c, b.c with679| Some ca, Some cb ->680let r = C.div_e_forward ca cb in681{proof…}682image2nz_c (fun (x:real) (y:real) -> from_int (Real.div_e x y)) ca cb r;683{qed}684Some r685| _ -> None686end in687{ c = c; u = Make.ED.div_e_forward a.u b.u }688end689Valid (1.2s) (colibri2 2) (split_vc) (depth 1)690let div_f_forward (a b: t) : t691ensures { sound2 mem (fun x y -> from_int (Real.div_f x y)) a b result }692= if mem_a (A.of_int 0) b then reals ()693else begin694let c = match a.c, b.c with695| Some ca, Some cb ->696let r = C.div_f_forward ca cb in697{proof…}698image2nz_c (fun (x:real) (y:real) -> from_int (Real.div_f x y)) ca cb r;699{qed}700Some r701| _ -> None702end in703{ c = c; u = Make.ED.div_f_forward a.u b.u }704end705Valid (1.2s) (colibri2 3) (split_vc 2) (depth 2)706let div_t_forward (a b: t) : t707ensures { sound2 mem (fun x y -> from_int (Real.div_t x y)) a b result }708= if mem_a (A.of_int 0) b then reals ()709else begin710let c = match a.c, b.c with711| Some ca, Some cb ->712let r = C.div_t_forward ca cb in713{proof…}714image2nz_c (fun (x:real) (y:real) -> from_int (Real.div_t x y)) ca cb r;715{qed}716Some r717| _ -> None718end in719{ c = c; u = Make.ED.div_t_forward a.u b.u }720end721Valid (7.8s) (colibri2 4) (cvc4) (split_vc 4) (depth 4)722let mod_e_forward (a b: t) : t723ensures { sound2 mem (fun x y -> Real.mod_e x y) a b result }724= if mem_a (A.of_int 0) b then reals ()725else begin726let c = match a.c, b.c with727| Some ca, Some cb ->728match CE.mod_e_forward ca cb with729| C.Top -> None730| C.R r -> Some r731end732| _ -> None733end in734{ c = c; u = Make.ED.mod_e_forward a.u b.u }735end736Valid (1.1s) (colibri2)737let mod_f_forward (a b: t) : t738ensures { sound2 mem (fun x y -> Real.mod_f x y) a b result }739= if mem_a (A.of_int 0) b then reals ()740else { c = None; u = Make.ED.mod_f_forward a.u b.u }741Valid (1.1s) (colibri2)742let mod_t_forward (a b: t) : t743ensures { sound2 mem (fun x y -> Real.mod_t x y) a b result }744= if mem_a (A.of_int 0) b then reals ()745else { c = None; u = Make.ED.mod_t_forward a.u b.u }746
The class of the numerators x of the class nc with x mod y in mod_ for a y of den, which does not contain 0; None when there is no such x
Valid (3.7s) (colibri2 9) (cvc4) (cvc5 2) (split_vc 8) (depth 5)let mod_e_class (nc: option C.t) (den mod_: t) : option (option C.t)751requires { not (mem 0.0 den) }752ensures { forall x y. memc x nc -> mem y den -> mem (Real.mod_e x y) mod_ ->753match result with None -> false | Some c -> memc x c end }754= match den.c, mod_.c with755| Some cd, Some cm ->756match C.mod_e_backward_num cd cm with757| C.Top -> Some nc758| C.R cr ->759match nc with760| None -> Some (Some cr)761| Some ncc ->762match C.inter ncc cr with763| None -> None764| Some ci -> Some (Some ci)765end766end767end768| _ -> Some nc769end770
The numerators x of num with x mod y in mod_ for a y of den; the class of C.mod_e_backward_num only when den does not contain 0 (the class is for the nonzero divisors)
Valid (1.2s) (colibri2 3) (split_vc 2) (depth 2)let mod_e_backward_num (num den mod_: t) : option t775ensures { back2 mem (fun x y -> Real.mod_e x y) num den mod_ result }776= match Make.ED.mod_e_backward_num num.u den.u mod_.u with777| None -> None778| Some u ->779if mem_a (A.of_int 0) den then Some { c = num.c; u = u } else780match mod_e_class num.c den mod_ with781| None -> None782| Some None -> Some { c = None; u = u }783| Some (Some c) -> reduce_congruence c u784end785end786Valid (469ms) (colibri2)787let mod_f_backward_num (num den mod_: t) : option t788ensures { back2 mem (fun x y -> Real.mod_f x y) num den mod_ result }789= match Make.ED.mod_f_backward_num num.u den.u mod_.u with790| None -> None791| Some u -> Some { c = num.c; u = u }792end793Valid (1.3s) (cvc4)794let mod_t_backward_num (num den mod_: t) : option t795ensures { back2 mem (fun x y -> Real.mod_t x y) num den mod_ result }796= match Make.ED.mod_t_backward_num num.u den.u mod_.u with797| None -> None798| Some u -> Some { c = num.c; u = u }799end800end801