Common — library colibrilib.union_congr — module UnionCongr

The domain of the reals of colibri2 (LRA): a union of intervals and a

congruence 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.

12
module UnionCongr
13
use int.Int
14
use real.RealInfix
15
use real.FromInt
16
use real.Abs
17
use real.Truncate
18
use option.Option
19
use list.List
20
use set.Set as S
21
use colibrilib.bound.Bound
22
use colibrilib.spec.Sound
23
use colibrilib.spec.Opt
24
use colibrilib.dv.Dv
25
use colibrilib.dv.RealSets
26
use colibrilib.q.Real as Real
27
use colibrilib.stdq.StdQ as Q
28
use colibrilib.stda.StdA as A
29
use colibrilib.union.Union
30
use colibrilib.congruence.Congruence as C
31
use colibrilib.congruence.Export as CE
32
use real.Square
33
use real.MinMax

The domain

37
type
t
= {
c
: option C.t;
u
: Make.t }
38
39
predicate
memc
(x: real) (c: option C.t) =
40
match c with None -> true | Some c -> C.member x c end

x is in the domain t

43
predicate
mem
(x: real) (t: t) = Make.memt x t.u /\ memc x t.c

Constants

  Valid (251ms) (colibri2)
47
let
reals
() : t
48
ensures { exact mem (fun _ -> true) result }
49
= { c = None; u = { Make.a = Make.On Make.Inf } }
50
Valid (399ms) (colibri2)
51
let
integers
() : t
52
ensures { exact mem (fun x -> Real.is_integer x) result }
53
= { c = Some (C.integers ()); u = { Make.a = Make.On Make.Inf } }
54
Valid (371ms) (colibri2)
55
let
singleton
(q: A.t) : t
56
ensures { exact mem (fun x -> x = A.real q) result }
57
= { c = Some (C.singleton q); u = Make.singleton q }
58
Valid (46ms) (colibri2)
59
let
zero
() : t
60
ensures { exact mem (fun x -> x = 0.0) result }
61
= singleton (A.of_int 0)
62
Valid (40ms) (colibri2)
63
let
of_congruence
(c: C.t) : t
64
ensures { exact mem (fun x -> C.member x c) result }
65
= { c = Some c; u = { Make.a = Make.On Make.Inf } }
66
Valid (274ms) (colibri2)
67
let
gt
(q: A.t) : t
68
ensures { exact mem (fun x -> A.real q <. x) result }
69
= { c = None; u = Make.gt q }
70
Valid (303ms) (colibri2)
71
let
ge
(q: A.t) : t
72
ensures { exact mem (fun x -> A.real q <=. x) result }
73
= { c = None; u = Make.ge q }
74
Valid (41ms) (colibri2)
75
let
lt
(q: A.t) : t
76
ensures { exact mem (fun x -> x <. A.real q) result }
77
= { c = None; u = Make.lt q }
78
Valid (246ms) (colibri2)
79
let
le
(q: A.t) : t
80
ensures { exact mem (fun x -> x <=. A.real q) result }
81
= { c = None; u = Make.le q }

The reals above (resp. below) a real of t

  Valid (234ms) (colibri2)
84
let
gt'
(t: t) : t
85
ensures { sound_rel mem (>.) t result }
86
= { c = None; u = Make.gt' t.u }
87
Valid (245ms) (colibri2)
88
let
ge'
(t: t) : t
89
ensures { sound_rel mem (>=.) t result }
90
= { c = None; u = Make.ge' t.u }
91
Valid (253ms) (colibri2)
92
let
lt'
(t: t) : t
93
ensures { sound_rel mem (<.) t result }
94
= { c = None; u = Make.lt' t.u }
95
Valid (214ms) (colibri2)
96
let
le'
(t: t) : t
97
ensures { sound_rel mem (<=.) t result }
98
= { c = None; u = Make.le' t.u }

The members of an integral class are integers

  Valid (238ms) (colibri2)
101
let ghost
integral_mem
(c: C.t) : unit
102
requires { C.integral c }
103
ensures { forall x. C.member x c -> Real.is_integer x }
104
= assert { forall x. C.member x c -> S.mem x (C.gamma c) }

Tests

  Valid (261ms) (colibri2)
108
let
mem_a
(x: A.t) (t: t) : bool
109
ensures { result <-> mem (A.real x) t }
110
= Make.mem x t.u && match t.c with None -> true | Some c -> C.mem x c end

Only integers

  Valid (756ms) (cvc5)
113
let
is_integer
(t: t) : bool
114
ensures { result -> forall x. mem x t -> Real.is_integer x }
115
= match t.c with None -> false | Some c -> C.is_integer c end

All the reals

  Valid (38ms) (colibri2)
118
let
is_reals
(t: t) : bool
119
ensures { result -> forall x. mem x t }
120
= match t.c, t.u.Make.a with None, Make.On Make.Inf -> true | _ -> false end

At most the real q

  Valid (322ms) (colibri2)
123
let
is_singleton
(t: t) : option A.t
124
ensures { match result with
125
| Some q -> forall x. mem x t -> x = A.real q
126
| None -> true end }
127
= match t.c with
128
| Some c ->
129
match C.is_singleton c with
130
| Some q -> Some q
131
| None -> let (o, _, _) = Make.is_singleton t.u in o
132
end
133
| None -> let (o, _, _) = Make.is_singleton t.u in o
134
end
135
Valid (2.3s) (colibri2 2) (cvc4) (cvc5) (split_vc 2) (depth 2)
136
let
is_included
(a b: t) : bool
137
ensures { result -> forall x. mem x a -> mem x b }
138
= (match a.c, b.c with
139
| Some c1, Some c2 -> C.is_included c1 c2
140
| _, None -> true
141
| None, Some _ -> false
142
end) &&
143
Make.for_all (fun x y -> if x then y else true) a.u b.u
144
Valid (835ms) (cvc4)
145
let
is_distinct
(a b: t) : bool
146
ensures { result -> forall x. mem x a -> not (mem x b) }
147
= Make.for_all (fun x y -> not (x && y)) a.u b.u

The reductions of the bounds of u by the class

Two members of a class differ by at least |div|

  Valid (229ms) (colibri2 7) (cvc4) (cvc5) (split_vc 2) (depth 2)
152
let ghost
gap
(r x d: real) : unit
153
requires { dv (r -. x) d /\ d <> 0.0 /\ r <. x }
154
ensures { r <=. x -. abs d }
155
= {proof…}
156
let k = quot (r -. x) d in
157
if d >. 0.0 then begin
158
assert { from_int k <. 0.0 by from_int k *. d <. 0.0 };
159
assert { from_int k <=. -. 1.0 };
160
assert { from_int k *. d <=. -. d by (from_int k +. 1.0) *. d <=. 0.0 };
161
end else begin
162
assert { from_int k >. 0.0 by from_int k *. d <. 0.0 };
163
assert { from_int k >=. 1.0 };
164
assert { from_int k *. d <=. d }
165
end
166
{qed}

The members of the class c next to a member x

  Valid (317ms) (colibri2)
169
let ghost next (c: C.t) (x: real) : unit
170
requires { C.member x c /\ Q.real c.C.div <> 0.0 }
171
ensures { C.member (x -. Q.real c.C.div) c /\ C.member (x +. Q.real c.C.div) c }
172
ensures { forall r. C.member r c -> r <. x -> r <=. x -. abs (Q.real c.C.div) }
173
ensures { forall r. C.member r c -> x <. r -> x +. abs (Q.real c.C.div) <=. r }
174
= let d = Q.real c.C.div in
175
let rm = A.real c.C.rem in
176
dv_self d;
177
dv_sub (x -. rm) d d;
178
dv_add (x -. rm) d d;
179
let lemma below (r: real) requires { C.member r c /\ r <. x } ensures { r <=. x -. abs d }
180
= dv_sub (r -. rm) (x -. rm) d; gap r x d in
181
let lemma above (r: real) requires { C.member r c /\ x <. r } ensures { x +. abs d <=. r }
182
= dv_sub (x -. rm) (r -. rm) d; gap x r d in
183
()

The members of c in u; c is not a singleton

  Valid (979ms) (colibri2 26) (cvc5 2) (split_vc 9) (depth 3)
186
let
reduce_congruence_nz
(c: C.t) (u: Make.t) : option t
187
requires { Q.real c.C.div <> 0.0 }
188
ensures { restrict Make.memt (fun x -> C.member x c) u
189
(match result with None -> None | Some r -> Some r.u end) }
190
ensures { match result with Some r -> r.c = Some c | None -> true end }
191
= let floorb (x: A.t) (b: Bound.t) : A.t
192
ensures { C.member (A.real result) c }
193
ensures { Make.cmp result b x }
194
ensures { forall r. Make.cmp r b x -> A.real result <. r -> not (C.member r c) }
195
= let x' = C.floor_a_nz x c in
196
{proof…} next c (A.real x'); {qed}
197
match b with
198
| Bound.Large -> x'
199
| Bound.Strict ->
200
if A.equal x x' then
201
(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))
202
else x'
203
end in
204
let ceilb (x: A.t) (b: Bound.t) : A.t
205
ensures { C.member (A.real result) c }
206
ensures { Make.cmp x b result }
207
ensures { forall r. Make.cmp x b r -> r <. A.real result -> not (C.member r c) }
208
= let x' = C.ceil_a_nz x c in
209
{proof…} next c (A.real x'); {qed}
210
match b with
211
| Bound.Large -> x'
212
| Bound.Strict ->
213
if A.equal x x' then
214
(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))
215
else x'
216
end in
217
let op = { Make.red_min = Make.I; Make.red_is_in = (fun x -> C.member x c);
218
Make.red_is_integer = (fun x -> C.mem x c);
219
Make.red_floorb = floorb; Make.red_ceilb = ceilb } in
220
match Make.reduce_generic op u with
221
| None -> None
222
| Some u -> Some { c = Some c; u = u }
223
end

The members of c in u

  Valid (275ms) (colibri2 3) (split_vc 2) (depth 2)
226
let
reduce_congruence
(c: C.t) (u: Make.t) : option t
227
ensures { forall x. Make.memt x u -> C.member x c ->
228
match result with None -> false | Some r -> mem x r end }
229
= match C.is_singleton c with
230
| None -> reduce_congruence_nz c u
231
| Some q -> if Make.mem q u then Some { c = Some c; u = Make.singleton q } else None
232
end

The integers of t

  Valid (1.2s) (colibri2 2) (cvc4) (split_vc 3) (depth 3)
235
let
reduce_integers
(t: t) : option t
236
ensures { restrict mem (fun x -> Real.is_integer x) t result }
237
= match t.c with
238
| None -> reduce_congruence (C.integers ()) t.u
239
| Some c ->
240
match C.reduce_integers c with
241
| None -> None
242
| Some c -> reduce_congruence c t.u
243
end
244
end

Lattice

  Valid (1.4s) (colibri2 7) (cvc4) (split_vc 3) (depth 3)
248
let
inter
(a b: t) : option t
249
ensures { restrict mem (fun x -> mem x b) a result }
250
= let inter_u (c: option C.t) (u1 u2: Make.t) : option t
251
ensures { exact_opt mem (fun x -> Make.memt x u1 /\ Make.memt x u2 /\ memc x c) result }
252
= match Make.inter u1 u2 with None -> None | Some u -> Some { c = c; u = u } end in
253
match a.c, b.c with
254
| Some ca, None ->
255
if C.is_integer ca then begin
256
{proof…} integral_mem ca; {qed}
257
match Make.reduce_integers b.u with
258
| None -> None
259
| Some u2 -> inter_u a.c a.u u2
260
end end
261
else inter_u a.c a.u b.u
262
| None, Some cb ->
263
if C.is_integer cb then begin
264
{proof…} integral_mem cb; {qed}
265
match Make.reduce_integers a.u with
266
| None -> None
267
| Some u1 -> inter_u b.c u1 b.u
268
end end
269
else inter_u b.c a.u b.u
270
| None, None ->
271
match inter_u None a.u b.u with
272
| None -> None
273
| Some r ->
274
match r.u.Make.a with
275
| Make.Off (Make.Sin q Make.Inf) -> Some { c = Some (C.singleton q); u = r.u }
276
| _ -> Some r
277
end
278
end
279
| Some c1, Some c2 ->
280
match C.inter c1 c2 with
281
| None -> None
282
| Some cc -> inter_u (Some cc) a.u b.u
283
end
284
end
285
Valid (2.8s) (colibri2 3) (cvc5) (split_vc 3) (depth 3)
286
let
union
(a b: t) : t
287
ensures { forall x. mem x a \/ mem x b -> mem x result }
288
= let c = match a.c, b.c with
289
| Some c1, Some c2 -> match C.union c1 c2 with C.Top -> None | C.R c -> Some c end
290
| _ -> None
291
end in
292
{ c = c; u = Make.union a.u b.u }

t without q

  Valid (3.1s) (colibri2 4) (cvc5) (split_vc 5) (depth 5)
295
let
except
(t: t) (q: A.t) : option t
296
ensures { restrict mem (fun x -> x <> A.real q) t result }
297
= match t.c with
298
| Some ct ->
299
if not (C.mem q ct) then Some t
300
else match Make.except t.u q with
301
| None -> None
302
| Some u ->
303
if C.is_integer ct then
304
match Make.reduce_integers u with
305
| None -> None
306
| Some u -> Some { c = t.c; u = u }
307
end
308
else Some { c = t.c; u = u }
309
end
310
| None ->
311
match Make.except t.u q with
312
| None -> None
313
| Some u -> Some { c = None; u = u }
314
end
315
end

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)
320
let
complement
(t: t) : option t
321
ensures { forall x. not (mem x t) ->
322
match result with None -> false | Some r -> mem x r end }
323
= let ex = match t.c with
324
| None -> true
325
| Some ct -> let (o, _, _) = Make.is_singleton t.u in
326
match o with Some q -> C.mem q ct | None -> false end
327
end in
328
if ex then
329
match Make.complement t.u with
330
| None -> None
331
| Some u -> Some { c = None; u = u }
332
end
333
else Some (reals ())

From the specifications of the classes (sets) to member

  Valid (378ms) (colibri2)
337
let ghost
image_c
(f: real -> real) (a r: C.t) : unit
338
requires { S.subset (image f (C.gamma a)) (C.gamma r) }
339
ensures { forall x. C.member x a -> C.member (f x) r }
340
= assert { forall x. C.member x a -> S.mem (f x) (image f (C.gamma a)) }
341
Valid (280ms) (colibri2)
342
let ghost
preimage_c
(f: real -> real) (a r: C.t) : unit
343
requires { S.subset (preimage f (C.gamma a)) (C.gamma r) }
344
ensures { forall x. C.member (f x) a -> C.member x r }
345
= assert { forall x. C.member (f x) a -> S.mem x (preimage f (C.gamma a)) }
346
Valid (741ms) (colibri2) (cvc5) (split_vc) (depth 1)
347
let ghost
image2_c
(f: real -> real -> real) (a b r: C.t) : unit
348
requires { S.subset (map2 f (C.gamma a) (C.gamma b)) (C.gamma r) }
349
ensures { forall x y. C.member x a -> C.member y b -> C.member (f x y) r }
350
= assert { forall x y. C.member x a -> C.member y b ->
351
S.mem (f x y) (map2 f (C.gamma a) (C.gamma b)) }

The members x of the integral class i whose square is in c

  Valid (812ms) (colibri2 4) (cvc5) (split_vc) (depth 1)
354
let ghost
square_c
(i c r: C.t) : unit
355
requires { C.integral i }
356
requires { S.subset (S.inter C.ints (pre_mul (C.gamma i) (C.gamma c))) (C.gamma r) }
357
ensures { forall x. C.member x i -> C.member (x *. x) c -> C.member x r }
358
= integral_mem i;
359
assert { forall x. C.member x i -> S.mem x C.ints };
360
assert { forall x. C.member x i -> C.member (x *. x) c ->
361
S.mem x (pre_mul (C.gamma i) (C.gamma c))
362
by S.mem x (C.gamma i) /\ S.mem (x *. x) (C.gamma c) };
363
assert { forall x. C.member x i -> C.member (x *. x) c ->
364
S.mem x (S.inter C.ints (pre_mul (C.gamma i) (C.gamma c))) }
365
Valid (651ms) (colibri2) (cvc5) (split_vc) (depth 1)
366
let ghost
image2nz_c
(f: real -> real -> real) (a b r: C.t) : unit
367
requires { S.subset (map2nz f (C.gamma a) (C.gamma b)) (C.gamma r) }
368
ensures { forall x y. C.member x a -> C.member y b -> y <> 0.0 ->
369
C.member (f x y) r }
370
= assert { forall x y. C.member x a -> C.member y b -> y <> 0.0 ->
371
S.mem (f x y) (map2nz f (C.gamma a) (C.gamma b)) }

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)
375
let
diff
(a b: t) : option t
376
ensures { restrict mem (fun x -> not (mem x b)) a result }
377
= let inside = match a.c, b.c with
378
| _, None -> true
379
| Some ca, Some cb -> C.is_included ca cb
380
| None, Some _ -> false
381
end in
382
{proof…}
383
assert { inside -> forall x. memc x a.c -> memc x b.c
384
by forall x. memc x a.c -> S.mem x (match a.c with Some ca -> C.gamma ca | None -> S.all end) };
385
{qed}
386
if inside then
387
match Make.complement b.u with
388
| None -> None
389
| Some u -> inter a { c = None; u = u }
390
end
391
else Some a

Convex hull

  Valid (361ms) (colibri2)
395
let
from_convex_hull
(h: Make.convex_hull) : option t
396
ensures { match result with
397
| Some r -> forall x. Make.in_hull x h -> mem x r
398
| None -> forall x. not (Make.in_hull x h) end }
399
= match Make.from_convex_hull h with None -> None | Some u -> Some { c = None; u = u } end

The lower bound of the integers above the bound b

  Valid (303ms) (colibri2)
402
let
int_lo
(b: option (A.t, Bound.t)) : option (A.t, Bound.t)
403
ensures { forall x. Real.is_integer x -> Make.in_hull x (b, None) -> Make.in_hull x (result, None) }
404
= match b with
405
| None -> None
406
| Some (z, Bound.Strict) ->
407
if 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)
408
| Some (z, Bound.Large) -> if A.is_integer z then b else Some (A.of_bigint (A.ceil_z z), Bound.Large)
409
end

The upper bound of the integers below the bound b

  Valid (301ms) (colibri2)
412
let
int_hi
(b: option (A.t, Bound.t)) : option (A.t, Bound.t)
413
ensures { forall x. Real.is_integer x -> Make.in_hull x (None, b) -> Make.in_hull x (None, result) }
414
= match b with
415
| None -> None
416
| Some (z, Bound.Strict) ->
417
if 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)
418
| Some (z, Bound.Large) -> if A.is_integer z then b else Some (A.of_bigint (A.floor_z z), Bound.Large)
419
end

The bounds of t; integers when t has only integers

  Valid (554ms) (colibri2) (split_vc) (depth 1)
422
let
get_convex_hull
(t: t) : Make.convex_hull
423
ensures { forall x. mem x t -> Make.in_hull x result }
424
= let (lo, hi) = Make.get_convex_hull t.u in
425
if is_integer t then (int_lo lo, int_hi hi) else (lo, hi)

Smaller numbers

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)
432
let
enlarge
(big: A.t -> bool) (down up: A.t -> A.t) (t: t) : t
433
ensures { forall x. mem x t -> mem x result }
434
= let dn (q: A.t) : A.t ensures { A.real result <=. A.real q }
435
= if big q then (let d = down q in if A.le d q then d else q) else q in
436
let upq (q: A.t) : A.t ensures { A.real q <=. A.real result }
437
= if big q then (let d = up q in if A.le q d then d else q) else q in
438
let lo (b: Make.Map.qbound) : Make.Map.qbound
439
ensures { forall r. Make.Map.cmp_inf_qbound b r -> Make.Map.cmp_inf_qbound result r }
440
= match b with
441
| Make.Map.BInf -> b
442
| Make.Map.BLarge q -> Make.Map.BLarge (dn q)
443
| Make.Map.BStrict q -> Make.Map.BStrict (dn q)
444
end in
445
let hi (b: Make.Map.qbound) : Make.Map.qbound
446
ensures { forall r. Make.Map.cmp_sup_qbound r b -> Make.Map.cmp_sup_qbound r result }
447
= match b with
448
| Make.Map.BInf -> b
449
| Make.Map.BLarge q -> Make.Map.BLarge (upq q)
450
| Make.Map.BStrict q -> Make.Map.BStrict (upq q)
451
end in
452
let f (i: Make.Map.interval) : Make.Map.res_interval
453
ensures { forall r. Make.Map.mem_interval r i -> Make.Map.mem_res_interval r result }
454
ensures { result <> Nil }
455
= match i with
456
| Make.Map.Singleton q ->
457
if big q then Cons (Make.Map.Inter (Make.Map.BLarge (dn q)) (Make.Map.BLarge (upq q))) Nil
458
else Cons i Nil
459
| Make.Map.Inter b1 b2 -> Cons (Make.Map.Inter (lo b1) (hi b2)) Nil
460
end in
461
{ c = t.c; u = Make.Map.Unary.map { Make.Map.Unary.f = f; Make.Map.Unary.fr = (fun x -> x) } t.u }

Arithmetic

  Valid (1.8s) (cvc4)
465
let
neg
(t: t) : t
466
ensures { sound1 mem (fun x -> -. x) t result }
467
= let c = match t.c with
468
| None -> None
469
| Some ct -> Some (C.neg_forward ct)
470
end in
471
{ c = c; u = Make.Increasing.Unary.neg t.u }
472
Valid (503ms) (colibri2 2) (split_vc) (depth 1)
473
let
add
(a b: t) : t
474
ensures { sound2 mem (fun x y -> x +. y) a b result }
475
= let c = match a.c, b.c with
476
| Some ca, Some cb ->
477
let r = C.add_forward ca cb in
478
{proof…} image2_c (fun x y -> x +. y) ca cb r; {qed}
479
Some r
480
| _ -> None
481
end in
482
{ c = c; u = Make.Increasing.Binary.add a.u b.u }
483
Valid (393ms) (colibri2 4) (split_vc 2) (depth 2)
484
let
minus
(a b: t) : t
485
ensures { sound2 mem (fun x y -> x -. y) a b result }
486
= let nb = neg b in
487
let r = add a nb in
488
{proof…}
489
assert { forall x y. mem x a -> mem y nb -> mem (x +. y) r };
490
assert { forall x y. mem x a -> mem y b -> mem (x -. y) r by x -. y = x +. (-. y) };
491
{qed}
492
r
493
Valid (635ms) (colibri2) (split_vc) (depth 1)
494
let
add_cst
(q: A.t) (t: t) : t
495
ensures { sound1 mem (fun x -> x +. A.real q) t result }
496
= let c = match t.c with
497
| None -> None
498
| Some ct -> Some (C.add_cst q ct)
499
end in
500
{ c = c; u = Make.Increasing.Binary.add_cst t.u q }
501
Valid (613ms) (colibri2 2) (split_vc 2) (depth 2)
502
let
mult_cst
(q: A.t) (t: t) : t
503
ensures { sound1 mem (fun x -> A.real q *. x) t result }
504
= let c = match t.c, A.view q with
505
| Some ct, A.Rat qq ->
506
let r = C.mul_cst qq ct in {proof…} image_c (fun x -> x *. Q.real qq) ct r; {qed} Some r
507
| _ -> None
508
end in
509
{ c = c; u = Make.Increasing.Unary.mult_cst q t.u }
510
Valid (686ms) (colibri2 2) (split_vc 2) (depth 2)
511
let
mul
(a b: t) : t
512
ensures { sound2 mem (fun x y -> x *. y) a b result }
513
= let c = match a.c, b.c with
514
| Some ca, Some cb ->
515
match C.mul_forward ca cb with
516
| C.Top -> None
517
| C.R r -> {proof…} image2_c (fun x y -> x *. y) ca cb r; {qed} Some r
518
end
519
| _ -> None
520
end in
521
{ c = c; u = Make.Increasing.Binary.mul a.u b.u }
522
Valid (273ms) (colibri2)
523
let
inv
(t: t) : t
524
ensures { sound1 mem (fun x -> 1.0 /. x) t result }
525
= { c = None; u = Make.Increasing.Binary.inv t.u }
526
Valid (272ms) (colibri2)
527
let
div
(a b: t) : t
528
ensures { sound2 mem (fun x y -> x /. y) a b result }
529
= { c = None; u = Make.Increasing.Binary.div a.u b.u }

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)
532
let
mul_backward
(r: t) (into: option t) (b: t) : C.backward t
533
ensures { match result with
534
| C.R res -> forall x y. (match into with Some i -> mem x i | None -> true end) ->
535
mem y b -> mem (x *. y) r -> mem x res
536
| C.Top -> true end }
537
= if Make.mem (A.of_int 0) b.u then C.Top
538
else begin
539
let into_c = match into with None -> None | Some i -> i.c end in
540
let c = match r.c, b.c with
541
| Some cr, Some cb ->
542
match C.mul_backward cr into_c cb with
543
| C.Top -> None
544
| C.R res ->
545
{proof…}
546
match into_c with
547
| Some d ->
548
integral_mem d;
549
let lemma pm (x y: real) : unit
550
requires { C.member x d /\ C.member y cb /\ C.member (x *. y) cr }
551
ensures { C.member x res }
552
= assert { S.mem x C.ints };
553
assert { S.mem x (pre_mul (C.gamma cb) (C.gamma cr)) } in ()
554
| None -> ()
555
end;
556
{qed}
557
Some res
558
end
559
| _ -> None
560
end in
561
let u = Make.Increasing.Binary.div r.u b.u in
562
{proof…}
563
assert { forall x y. Make.memt y b.u -> Make.memt (x *. y) r.u -> Make.memt x u
564
by y <> 0.0 so (x *. y) /. y = x };
565
{qed}
566
C.R { c = c; u = u }
567
end
568
Valid (435ms) (colibri2 2) (split_vc) (depth 1)
569
let
ceil
(t: t) : t
570
ensures { sound1 mem (fun x -> from_int (Truncate.ceil x)) t result }
571
= let c = match t.c with
572
| None -> None
573
| Some ct ->
574
let r = C.ceil_forward ct in
575
{proof…} image_c (fun v -> from_int (Truncate.ceil v)) ct r; {qed}
576
Some r
577
end in
578
{ c = c; u = Make.NonIncreasing.ceil t.u }
579
Valid (435ms) (colibri2 2) (split_vc) (depth 1)
580
let
floor
(t: t) : t
581
ensures { sound1 mem (fun x -> from_int (Truncate.floor x)) t result }
582
= let c = match t.c with
583
| None -> None
584
| Some ct ->
585
let r = C.floor_forward ct in
586
{proof…} image_c (fun v -> from_int (Truncate.floor v)) ct r; {qed}
587
Some r
588
end in
589
{ c = c; u = Make.NonIncreasing.floor t.u }
590
Valid (571ms) (colibri2) (cvc4) (split_vc) (depth 1)
591
let
truncate
(t: t) : t
592
ensures { sound1 mem (fun x -> from_int (Truncate.truncate x)) t result }
593
= let c = match t.c with
594
| None -> None
595
| Some ct ->
596
let r = C.truncate_forward ct in
597
{proof…} image_c (fun v -> from_int (Truncate.truncate v)) ct r; {qed}
598
Some r
599
end in
600
{ c = c; u = Make.NonIncreasing.truncate t.u }
601
Valid (221ms) (colibri2 2) (split_vc 2) (depth 2)
602
let
relu
(t: t) : t
603
ensures { sound1 mem (fun x -> max 0.0 x) t result }
604
= let c = match t.c with
605
| None -> None
606
| Some ct ->
607
match C.relu_forward ct with
608
| C.Top -> None
609
| C.R r ->
610
{proof…} image_c (fun x -> if x <. 0.0 then 0.0 else x) ct r; {qed}
611
Some r
612
end
613
end in
614
{ c = c; u = Make.NonIncreasing.relu t.u }
615
Valid (374ms) (colibri2 2) (split_vc 2) (depth 2)
616
let
abs_forward
(t: t) : t
617
ensures { sound1 mem (fun x -> abs x) t result }
618
= let c = match t.c with
619
| None -> None
620
| Some ct ->
621
match C.abs_forward ct with
622
| C.Top -> None
623
| C.R r -> {proof…} image_c (fun x -> abs x) ct r; {qed} Some r
624
end
625
end in
626
{ c = c; u = Make.Increasing.abs_forward t.u }
627
Valid (384ms) (colibri2 2) (split_vc 2) (depth 2)
628
let
abs_backward
(t: t) : t
629
ensures { preimage1 mem (fun x -> abs x) t result }
630
= let c = match t.c with
631
| None -> None
632
| Some ct ->
633
match C.abs_backward ct with
634
| C.Top -> None
635
| C.R r -> {proof…} preimage_c (fun y -> abs y) ct r; {qed} Some r
636
end
637
end in
638
{ c = c; u = Make.Increasing.abs_backward t.u }

The x of into with x * x in t

  Valid (294ms) (colibri2 7) (split_vc) (depth 1)
641
let
square_backward
(into: option t) (t: t) : option t
642
ensures { forall x. (match into with Some i -> mem x i | None -> true end) ->
643
mem (x *. x) t -> match result with None -> false | Some r -> mem x r end }
644
= match Make.square_backward t.u with
645
| None ->
646
{proof…}
647
assert { preimage1_opt Make.memt (fun (x:real) -> sqr x) t.u None };
648
assert { forall x. not Make.memt (sqr x) t.u };
649
{qed}
650
None
651
| Some u ->
652
{proof…}
653
assert { preimage1_opt Make.memt (fun (x:real) -> sqr x) t.u (Some u) };
654
assert { forall x. Make.memt (sqr x) t.u -> Make.memt x u };
655
{qed}
656
let c = match t.c, into with
657
| Some ct, Some i ->
658
match i.c with
659
| Some ic ->
660
match C.mul_backward ct (Some ic) ic with
661
| C.Top -> None
662
| C.R r ->
663
{proof…} square_c ic ct r; {qed}
664
Some r
665
end
666
| None -> None
667
end
668
| _ -> None
669
end in
670
Some { c = c; u = u }
671
end

Euclidean, floor and truncated division

  Valid (832ms) (colibri2 3) (split_vc 2) (depth 2)
675
let
div_e_forward
(a b: t) : t
676
ensures { sound2 mem (fun x y -> from_int (Real.div_e x y)) a b result }
677
= if mem_a (A.of_int 0) b then reals ()
678
else begin
679
let c = match a.c, b.c with
680
| Some ca, Some cb ->
681
let r = C.div_e_forward ca cb in
682
{proof…}
683
image2nz_c (fun (x:real) (y:real) -> from_int (Real.div_e x y)) ca cb r;
684
{qed}
685
Some r
686
| _ -> None
687
end in
688
{ c = c; u = Make.ED.div_e_forward a.u b.u }
689
end
690
Valid (1.2s) (colibri2 2) (split_vc) (depth 1)
691
let
div_f_forward
(a b: t) : t
692
ensures { sound2 mem (fun x y -> from_int (Real.div_f x y)) a b result }
693
= if mem_a (A.of_int 0) b then reals ()
694
else begin
695
let c = match a.c, b.c with
696
| Some ca, Some cb ->
697
let r = C.div_f_forward ca cb in
698
{proof…}
699
image2nz_c (fun (x:real) (y:real) -> from_int (Real.div_f x y)) ca cb r;
700
{qed}
701
Some r
702
| _ -> None
703
end in
704
{ c = c; u = Make.ED.div_f_forward a.u b.u }
705
end
706
Valid (1.2s) (colibri2 3) (split_vc 2) (depth 2)
707
let
div_t_forward
(a b: t) : t
708
ensures { sound2 mem (fun x y -> from_int (Real.div_t x y)) a b result }
709
= if mem_a (A.of_int 0) b then reals ()
710
else begin
711
let c = match a.c, b.c with
712
| Some ca, Some cb ->
713
let r = C.div_t_forward ca cb in
714
{proof…}
715
image2nz_c (fun (x:real) (y:real) -> from_int (Real.div_t x y)) ca cb r;
716
{qed}
717
Some r
718
| _ -> None
719
end in
720
{ c = c; u = Make.ED.div_t_forward a.u b.u }
721
end
722
Valid (7.8s) (colibri2 4) (cvc4) (split_vc 4) (depth 4)
723
let
mod_e_forward
(a b: t) : t
724
ensures { sound2 mem (fun x y -> Real.mod_e x y) a b result }
725
= if mem_a (A.of_int 0) b then reals ()
726
else begin
727
let c = match a.c, b.c with
728
| Some ca, Some cb ->
729
match CE.mod_e_forward ca cb with
730
| C.Top -> None
731
| C.R r -> Some r
732
end
733
| _ -> None
734
end in
735
{ c = c; u = Make.ED.mod_e_forward a.u b.u }
736
end
737
Valid (1.1s) (colibri2)
738
let
mod_f_forward
(a b: t) : t
739
ensures { sound2 mem (fun x y -> Real.mod_f x y) a b result }
740
= if mem_a (A.of_int 0) b then reals ()
741
else { c = None; u = Make.ED.mod_f_forward a.u b.u }
742
Valid (1.1s) (colibri2)
743
let
mod_t_forward
(a b: t) : t
744
ensures { sound2 mem (fun x y -> Real.mod_t x y) a b result }
745
= if mem_a (A.of_int 0) b then reals ()
746
else { c = None; u = Make.ED.mod_t_forward a.u b.u }

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)
751
let
mod_e_class
(nc: option C.t) (den mod_: t) : option (option C.t)
752
requires { not (mem 0.0 den) }
753
ensures { forall x y. memc x nc -> mem y den -> mem (Real.mod_e x y) mod_ ->
754
match result with None -> false | Some c -> memc x c end }
755
= match den.c, mod_.c with
756
| Some cd, Some cm ->
757
match C.mod_e_backward_num cd cm with
758
| C.Top -> Some nc
759
| C.R cr ->
760
match nc with
761
| None -> Some (Some cr)
762
| Some ncc ->
763
match C.inter ncc cr with
764
| None -> None
765
| Some ci -> Some (Some ci)
766
end
767
end
768
end
769
| _ -> Some nc
770
end

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)
775
let
mod_e_backward_num
(num den mod_: t) : option t
776
ensures { back2 mem (fun x y -> Real.mod_e x y) num den mod_ result }
777
= match Make.ED.mod_e_backward_num num.u den.u mod_.u with
778
| None -> None
779
| Some u ->
780
if mem_a (A.of_int 0) den then Some { c = num.c; u = u } else
781
match mod_e_class num.c den mod_ with
782
| None -> None
783
| Some None -> Some { c = None; u = u }
784
| Some (Some c) -> reduce_congruence c u
785
end
786
end
787
Valid (469ms) (colibri2)
788
let
mod_f_backward_num
(num den mod_: t) : option t
789
ensures { back2 mem (fun x y -> Real.mod_f x y) num den mod_ result }
790
= match Make.ED.mod_f_backward_num num.u den.u mod_.u with
791
| None -> None
792
| Some u -> Some { c = num.c; u = u }
793
end
794
Valid (1.3s) (cvc4)
795
let
mod_t_backward_num
(num den mod_: t) : option t
796
ensures { back2 mem (fun x y -> Real.mod_t x y) num den mod_ result }
797
= match Make.ED.mod_t_backward_num num.u den.u mod_.u with
798
| None -> None
799
| Some u -> Some { c = num.c; u = u }
800
end
801
end