Common — library colibrilib.congruence — module Congruence

The congruence domain of colibri2 (LRA): the set { rem + div * k | k in Z } with div a rational and rem a real that is rational or algebraic.

Reading guide

gamma c is the set of the reals of the class c. The specification of a function relates the gamma of its result to the gamma of its arguments:

The result Top of a function of type backward means that nothing is known. Each such function says exactly when it returns Top.

Every function of this module accepts any arguments, except the ones whose name ends with _nz, which have a precondition: the module Export has their total version, which is the one that is extracted.

Trusted base and helper facts

The trusted base is the numbers: StdQ and StdA, and the integers of Zarith (zarith.Z.gcdext, zarith.Zbit.trailing_zeros, tested by QCheck in colibri2/theories/LRA/congruence/test). The helper facts on divisibility are in colibrilib/dv.mlw and those on the low bits in colibrilib/lowbits.mlw.

30
module Congruence
31
use int.Int
32
use real.RealInfix
33
use real.FromInt
34
use real.Abs
35
use real.Truncate
36
use option.Option
37
use colibrilib.zarith.Zbit
38
use colibrilib.zbit.ZbitInt
39
use set.Set as S
40
use colibrilib.dv.Dv
41
use colibrilib.dv.RealSets
42
use colibrilib.dv.RealFacts
43
use colibrilib.lowbits.LowBits
44
use colibrilib.zarith.Z as Z
45
use number.Gcd as G
46
use number.Divisibility as D

The gcd of Zarith as qa stated it for Bezout

  Valid (63ms) (colibri2)
49
let ghost
gcd_facts
(a b:int) : unit
50
ensures { 0 <= G.gcd a b }
51
ensures { exists a':int. a = a' * G.gcd a b }
52
ensures { exists b':int. b = b' * G.gcd a b }
53
= assert { D.divides (G.gcd a b) a /\ D.divides (G.gcd a b) b }
54
use colibrilib.stdq.StdQ as Q
55
use colibrilib.q.Real as Real
56
use colibrilib.qa.ModE
57
use colibrilib.qa.Rat
58
use colibrilib.stda.StdA as A
59
use colibrilib.known_bits.KnownBits as KB

The class { rem + div * k | k in Z }. There is no invariant: div may be zero (the class is the single real rem) or negative; norm gives the normal form.

64
type
t
= {
div
: Q.t;
rem
: A.t }

The result of a propagator: R c is a class, Top says that nothing is known (all the reals).

68
type
backward
'a =
Top
|
R
'a

x is in the class of c: x - rem is an integer multiple of div

71
predicate
member
(x:real) (c:t) = dv (x -. A.real c.rem) (Q.real c.div)

The concretization of c: the set of the reals of its class

74
function
gamma
(c:t) : S.set real = fun x -> member x c

The representative is in its class

  Valid (26ms) (colibri2)
77
let ghost
rem_member
(c:t) : unit
78
ensures { member (A.real c.rem) c }
79
= dv_zero (Q.real c.div);
80
assert { A.real c.rem -. A.real c.rem = 0.0 }

rem + div is in the class

  Valid (24ms) (colibri2)
83
let ghost
rem_div_member
(c:t) : unit
84
ensures { member (A.real c.rem +. Q.real c.div) c }
85
= dv_self (Q.real c.div);
86
assert { A.real c.rem +. Q.real c.div -. A.real c.rem = Q.real c.div }

Membership through an inclusion of concretizations

  Valid (109ms) (cvc5)
89
let ghost
sub_member
(x y:t) (z:real) : unit
90
requires { S.subset (gamma x) (gamma y) }
91
requires { member z x }
92
ensures { member z y }
93
= ()

The set of the integers

96
function
ints
: S.set real = fun x -> Real.is_integer x

All the elements of c are integers

99
predicate
integral
(c:t) = S.subset (gamma c) ints

An integer is in ints

  Valid (33ms) (colibri2)
102
let ghost
ints_intro
(z:int) : unit
103
ensures { S.mem (from_int z) ints }
104
= ()

The set of the integers

  Valid (134ms) (colibri2)
107
let
integers
() : t
108
ensures { gamma result = ints }
109
ensures { Q.real result.div = 1.0 /\ A.real result.rem = 0.0 }
110
= let r = { div = Q.of_int 1; rem = A.of_int 0 } in
111
let lemma pw (x:real) : unit
112
ensures { member x r <-> Real.is_integer x }
113
= if pure { member x r } then begin
114
let k = quot pure { x -. A.real r.rem } pure { Q.real r.div } in
115
assert { Real.is_integer x by x = from_int k }
116
end;
117
if pure { Real.is_integer x } then begin
118
let z = Real.int_of x in
119
dv_intro (x -. A.real r.rem) (Q.real r.div) z
120
end in
121
set_ext (gamma r) ints;
122
r

The same set with a normalized representation: div is non negative, rem is in [0, div), and the integers are {div = 1; rem = 0}

  Valid (77ms) (colibri2 22) (split_vc 2) (depth 2)
126
let
norm
(n:t) : t
127
ensures { gamma result = gamma n }

the representative moves by a multiple of div

129
ensures { exists k:int. A.real result.rem = A.real n.rem +. from_int k *. Q.real n.div }
130
= if Q.is_zero n.div then begin
131
assert { A.real n.rem = A.real n.rem +. from_int 0 *. Q.real n.div };
132
n
133
end
134
else if Q.equal n.div (Q.of_int 1) && A.is_integer n.rem then begin
135
let r = integers () in
136
let ghost m = A.to_z n.rem in
137
assert { A.real r.rem = A.real n.rem +. from_int (- m) *. Q.real n.div };
138
let lemma same (x:real) : unit
139
ensures { member x n <-> S.mem x (gamma r) }
140
= if pure { member x n } then begin
141
let k = quot pure { x -. A.real n.rem } pure { Q.real n.div } in
142
assert { Real.is_integer x by x = from_int (k + m) }
143
end;
144
if pure { Real.is_integer x } then begin
145
let z = Real.int_of x in
146
dv_intro (x -. A.real n.rem) (Q.real n.div) (z - m)
147
end in
148
set_ext (gamma n) (gamma r);
149
r
150
end else begin
151
let div = Q.abs n.div in
152
let bd = A.of_q div in
153
let rem = A.mod_e n.rem bd in
154
mod_e_facts pure { A.real n.rem } pure { A.real bd };
155
let ghost k = pure { Real.div_e (A.real n.rem) (A.real bd) } in
156
let lemma same (x:real) : unit
157
ensures { member x n <-> dv (x -. A.real rem) (Q.real div) }
158
= dv_mul_int k pure { Q.real div };
159
dv_shift pure { x -. A.real rem } pure { from_int k *. Q.real div } pure { Q.real div };
160
dv_abs pure { x -. A.real n.rem } pure { Q.real n.div };
161
assert { A.real rem = A.real n.rem -. from_int k *. Q.real div };
162
assert { x -. A.real rem -. from_int k *. Q.real div = x -. A.real n.rem } in
163
assert { A.real rem = A.real n.rem -. from_int k *. Q.real div };
164
abs_shift pure { A.real n.rem } pure { A.real rem } pure { Q.real n.div } k;
165
let res = { div = div; rem = rem } in
166
assert { A.real res.rem = A.real rem };
167
set_ext (gamma res) (gamma n);
168
res
169
end
170
Valid (43ms) (colibri2)
171
let
a_divisible
(a:A.t) (q:Q.t) : bool
172
ensures { result <-> dv (A.real a) (Q.real q) }
173
= match A.view a with
174
| A.Irr ->
175
if pure { dv (A.real a) (Q.real q) } then begin
176
let k = any int ensures { A.real a = from_int result *. Q.real q } in
177
let r = Q.mul (Q.of_bigint k) q in
178
assert { Q.real r = A.real a }
179
end;
180
false
181
| A.Rat a -> let r, ghost _ = Q.divisible a q in r
182
end

The class of the single real v

  Valid (57ms) (colibri2)
185
let
singleton
(v:A.t) : t
186
ensures { gamma result = S.singleton (A.real v) }
187
ensures { Q.real result.div = 0.0 /\ A.real result.rem = A.real v }
188
= let r = { div = Q.of_int 0; rem = v } in
189
let lemma pw (x:real) : unit
190
ensures { member x r <-> x = A.real v }
191
= dv_zero_iff (x -. A.real v) in
192
set_ext (gamma r) (S.singleton (A.real v));
193
r

Some r when the class is the single real r

  Valid (54ms) (colibri2)
196
let
is_singleton
(c:t) : option A.t
197
ensures { match result with
198
| Some r -> gamma c = S.singleton (A.real r)
199
| None -> Q.real c.div <> 0.0
200
end }
201
= if Q.is_zero c.div then begin
202
let lemma pw (x:real) : unit
203
ensures { member x c <-> x = A.real c.rem }
204
= dv_zero_iff (x -. A.real c.rem) in
205
set_ext (gamma c) (S.singleton (A.real c.rem));
206
Some c.rem
207
end else None

All the elements of c are integers

  Valid (415ms) (colibri2 13) (cvc5 2) (split_vc 4) (depth 2)
210
let
is_integer
(c:t) : bool
211
ensures { result <-> integral c }
212
= let ia = A.is_integer c.rem in
213
let iq = Q.is_integer c.div in
214
let lemma forward (x:real) : unit
215
requires { ia /\ iq }
216
requires { member x c }
217
ensures { Real.is_integer x }
218
= let m = Q.to_z c.div in
219
let n = A.to_z c.rem in
220
let k = quot pure { x -. A.real c.rem } pure { Q.real c.div } in
221
assert { Real.is_integer x by x = from_int (n + k * m) } in
222
if not ia then begin
223
(* the representative itself is not an integer *)
224
assert { member (A.real c.rem) c }
225
end else if not iq then begin
226
let n = A.to_z c.rem in
227
assert { member (A.real c.rem +. Q.real c.div) c };
228
if pure { Real.is_integer (A.real c.rem +. Q.real c.div) } then begin
229
let z = Real.int_of (A.real c.rem +. Q.real c.div) in
230
assert { Real.is_integer (Q.real c.div) by Q.real c.div = from_int (z - n) }
231
end
232
end;
233
ia && iq

The intersection, exactly (None when it is empty; Bezout and the Chinese remainder theorem)

  Valid (769ms) (colibri2 62) (cvc5 2) (split_vc) (depth 1)
237
let
inter
(x y:t) : option t
238
ensures { match result with
239
| Some c -> gamma c = S.inter (gamma x) (gamma y)
240
| None -> S.is_empty (S.inter (gamma x) (gamma y))
241
end }
242
= let b = A.sub y.rem x.rem in
243
if Q.equal x.div y.div then begin
244
let r = a_divisible b x.div in
245
let lemma same (z:real) : unit
246
requires { r }
247
ensures { member z x <-> member z y }
248
= dv_shift (z -. A.real x.rem) (A.real y.rem -. A.real x.rem) (Q.real x.div);
249
assert { z -. A.real y.rem = (z -. A.real x.rem) -. (A.real y.rem -. A.real x.rem) };
250
dv_shift (z -. A.real y.rem) (A.real y.rem -. A.real x.rem) (Q.real x.div);
251
assert { z -. A.real x.rem = (z -. A.real y.rem) +. (A.real y.rem -. A.real x.rem) } in
252
let lemma empty (z:real) : unit
253
requires { not r }
254
requires { member z x }
255
requires { member z y }
256
ensures { false }
257
= dv_sub (z -. A.real x.rem) (z -. A.real y.rem) (Q.real x.div);
258
assert { A.real y.rem -. A.real x.rem = (z -. A.real x.rem) -. (z -. A.real y.rem) } in
259
if r then begin
260
set_ext (gamma x) (S.inter (gamma x) (gamma y));
261
Some x
262
end else None
263
end else begin
264
let g, ux, ghost uy = Q.gcdext x.div y.div in
265
(* the divisors are different, so not both zero *)
266
assert { Q.real g <> 0.0 };
267
let lemma empty_irr (z:real) : unit
268
requires { member z x }
269
requires { member z y }
270
ensures { dv (A.real b) (Q.real g) }
271
= dv_trans (z -. A.real x.rem) (Q.real x.div) (Q.real g);
272
dv_trans (z -. A.real y.rem) (Q.real y.div) (Q.real g);
273
dv_sub (z -. A.real x.rem) (z -. A.real y.rem) (Q.real g);
274
assert { A.real b = (z -. A.real x.rem) -. (z -. A.real y.rem) -. 0.0 } in
275
match A.view b with
276
| A.Irr ->
277
let lemma none (z:real) : unit
278
requires { member z x }
279
requires { member z y }
280
ensures { false }
281
= empty_irr z;
282
let k = any int ensures { z -. A.real x.rem = from_int result *. Q.real x.div } in
283
let l = any int ensures { z -. A.real y.rem = from_int result *. Q.real y.div } in
284
let q = Q.sub (Q.mul (Q.of_bigint k) x.div) (Q.mul (Q.of_bigint l) y.div) in
285
assert { Q.real q = A.real b } in
286
None
287
| A.Rat bq ->
288
let r, ghost _ = Q.divisible bq g in
289
if r then begin
290
let beta = Q.divexact bq g in
291
let p = Q.lcm x.div y.div in
292
let e = Q.mul x.div (Q.of_bigint (beta * ux)) in
293
let r1 = A.add x.rem (A.of_q e) in
294
let n0 = { div = p; rem = r1 } in
295
let c = norm n0 in
296
assert { A.real r1 = A.real x.rem +. Q.real e };
297
(* the representative `rx + e` is in both sets *)
298
let lemma offsets () : unit
299
ensures { dv (A.real x.rem +. Q.real e -. A.real x.rem) (Q.real x.div) }
300
ensures { dv (A.real x.rem +. Q.real e -. A.real y.rem) (Q.real y.div) }
301
= assert { A.real x.rem +. Q.real e -. A.real x.rem = from_int (beta * ux) *. Q.real x.div };
302
assert { A.real y.rem -. A.real x.rem = from_int beta *. Q.real g };
303
assert { Q.real g = from_int ux *. Q.real x.div +. from_int uy *. Q.real y.div };
304
let ghost fb = from_int beta in
305
let ghost fu = from_int ux in
306
let ghost fv = from_int uy in
307
assert { from_int (beta * ux) = fb *. fu };
308
assert { from_int (- (beta * uy)) = -. (fb *. fv) };
309
assert { Q.real e = Q.real x.div *. (fb *. fu) };
310
assert { A.real y.rem -. A.real x.rem = fb *. (fu *. Q.real x.div +. fv *. Q.real y.div) };
311
assert { A.real x.rem +. Q.real e -. A.real y.rem = from_int (- (beta * uy)) *. Q.real y.div };
312
dv_mul_int (beta * ux) (Q.real x.div);
313
dv_mul_int (- (beta * uy)) (Q.real y.div) in
314
let lemma fwd (z:real) : unit
315
requires { dv (z -. (A.real x.rem +. Q.real e)) (Q.real p) }
316
ensures { member z x /\ member z y }
317
= offsets ();
318
dv_trans (z -. (A.real x.rem +. Q.real e)) (Q.real p) (Q.real x.div);
319
dv_trans (z -. (A.real x.rem +. Q.real e)) (Q.real p) (Q.real y.div);
320
dv_add (z -. (A.real x.rem +. Q.real e)) (A.real x.rem +. Q.real e -. A.real x.rem) (Q.real x.div);
321
dv_add (z -. (A.real x.rem +. Q.real e)) (A.real x.rem +. Q.real e -. A.real y.rem) (Q.real y.div) in
322
let lemma bwd (z:real) : unit
323
requires { member z x /\ member z y }
324
ensures { dv (z -. (A.real x.rem +. Q.real e)) (Q.real p) }
325
= offsets ();
326
dv_sub (z -. A.real x.rem) (A.real x.rem +. Q.real e -. A.real x.rem) (Q.real x.div);
327
dv_sub (z -. A.real y.rem) (A.real x.rem +. Q.real e -. A.real y.rem) (Q.real y.div);
328
assert { z -. A.real x.rem -. (A.real x.rem +. Q.real e -. A.real x.rem)
329
= z -. (A.real x.rem +. Q.real e) };
330
assert { z -. A.real y.rem -. (A.real x.rem +. Q.real e -. A.real y.rem)
331
= z -. (A.real x.rem +. Q.real e) } in
332
let lemma both (z:real) : unit
333
ensures { member z c <-> (member z x /\ member z y) }
334
= assert { member z c <-> member z n0 };
335
assert { member z n0 <-> dv (z -. (A.real x.rem +. Q.real e)) (Q.real p) };
336
if pure { member z c } then fwd z;
337
if pure { member z x /\ member z y } then bwd z in
338
set_ext (gamma c) (S.inter (gamma x) (gamma y));
339
Some c
340
end else begin
341
let lemma none (z:real) : unit
342
requires { member z x }
343
requires { member z y }
344
ensures { false }
345
= empty_irr z in
346
None
347
end
348
end
349
end

The smallest element that contains x and y; Top when there is no such element (the difference of the representatives is not rational)

  Valid (988ms) (colibri2 42) (cvc5) (split_vc) (depth 1)
353
let
union
(x y:t) : backward t
354
ensures { match result with
355
| R c -> S.subset (gamma x) (gamma c) /\ S.subset (gamma y) (gamma c)
356
/\ (forall c'. S.subset (gamma x) (gamma c') -> S.subset (gamma y) (gamma c')
357
-> S.subset (gamma c) (gamma c'))
358
/\ Q.is_rat (A.real x.rem -. A.real y.rem)
359
| Top -> (forall c'. not (S.subset (gamma x) (gamma c') /\ S.subset (gamma y) (gamma c')))
360
/\ not (Q.is_rat (A.real x.rem -. A.real y.rem))
361
end }
362
= let d = A.sub x.rem y.rem in
363
match A.view d with
364
| A.Irr ->
365
let lemma none (c':t) : unit
366
requires { S.subset (gamma x) (gamma c') }
367
requires { S.subset (gamma y) (gamma c') }
368
ensures { false }
369
= rem_member x;
370
rem_member y;
371
sub_member x c' (A.real x.rem);
372
sub_member y c' (A.real y.rem);
373
dv_sub (A.real x.rem -. A.real c'.rem) (A.real y.rem -. A.real c'.rem) (Q.real c'.div);
374
let k = any int ensures { A.real d = from_int result *. Q.real c'.div } in
375
let q = Q.mul (Q.of_bigint k) c'.div in
376
assert { Q.real q = A.real d } in
377
Top
378
| A.Rat q ->
379
let g1 = Q.gcd x.div y.div in
380
let g = Q.gcd g1 q in
381
let r = norm { rem = x.rem; div = g } in
382
let lemma sound_x (z:real) : unit
383
requires { member z x }
384
ensures { member z r }
385
= dv_trans (z -. A.real x.rem) (Q.real x.div) (Q.real g1);
386
dv_trans (z -. A.real x.rem) (Q.real g1) (Q.real g) in
387
let lemma sound_y (z:real) : unit
388
requires { member z y }
389
ensures { member z r }
390
= dv_trans (z -. A.real y.rem) (Q.real y.div) (Q.real g1);
391
dv_trans (z -. A.real y.rem) (Q.real g1) (Q.real g);
392
dv_neg (Q.real q) (Q.real g);
393
dv_add (z -. A.real y.rem) (-. Q.real q) (Q.real g);
394
assert { z -. A.real x.rem = (z -. A.real y.rem) +. (-. Q.real q) } in
395
let lemma least (c':t) : unit
396
requires { S.subset (gamma x) (gamma c') }
397
requires { S.subset (gamma y) (gamma c') }
398
ensures { S.subset (gamma r) (gamma c') }
399
= rem_member x;
400
rem_member y;
401
rem_div_member x;
402
rem_div_member y;
403
sub_member x c' (A.real x.rem);
404
sub_member y c' (A.real y.rem);
405
sub_member x c' (A.real x.rem +. Q.real x.div);
406
sub_member y c' (A.real y.rem +. Q.real y.div);
407
dv_shift (A.real x.rem +. Q.real x.div -. A.real c'.rem) (A.real x.rem -. A.real c'.rem) (Q.real c'.div);
408
dv_shift (A.real y.rem +. Q.real y.div -. A.real c'.rem) (A.real y.rem -. A.real c'.rem) (Q.real c'.div);
409
dv_sub (A.real x.rem -. A.real c'.rem) (A.real y.rem -. A.real c'.rem) (Q.real c'.div);
410
let lemma inner (z:real) : unit
411
requires { member z r }
412
ensures { member z c' }
413
= dv_trans (z -. A.real x.rem) (Q.real g) (Q.real c'.div);
414
dv_add (z -. A.real x.rem) (A.real x.rem -. A.real c'.rem) (Q.real c'.div);
415
assert { z -. A.real c'.rem = (z -. A.real x.rem) +. (A.real x.rem -. A.real c'.rem) } in
416
() in
417
R r
418
end

x is a subset of y

  Valid (501ms) (cvc4)
421
let
is_included
(x y:t) : bool
422
ensures { result <-> S.subset (gamma x) (gamma y) }
423
= let r1, ghost _ = Q.divisible x.div y.div in
424
let r2 = a_divisible ((A.sub x.rem y.rem)) y.div in
425
let lemma back (z:real) : unit
426
requires { r1 /\ r2 }
427
requires { member z x }
428
ensures { member z y }
429
= dv_trans (z -. A.real x.rem) (Q.real x.div) (Q.real y.div);
430
dv_add (z -. A.real x.rem) (A.real x.rem -. A.real y.rem) (Q.real y.div);
431
assert { z -. A.real y.rem = (z -. A.real x.rem) +. (A.real x.rem -. A.real y.rem) } in
432
if not (r1 && r2) then begin
433
rem_member x;
434
rem_div_member x;
435
if pure { S.subset (gamma x) (gamma y) } then begin
436
sub_member x y (A.real x.rem);
437
sub_member x y (A.real x.rem +. Q.real x.div);
438
dv_shift (A.real x.rem +. Q.real x.div -. A.real y.rem) (A.real x.rem -. A.real y.rem) (Q.real y.div)
439
end
440
end;
441
r1 && r2

x belongs to da

  Valid (31ms) (colibri2)
444
let
mem
(x:A.t) (da:t) : bool
445
ensures { result <-> S.mem (A.real x) (gamma da) }
446
= a_divisible ((A.sub x da.rem)) da.div

da translated by q, exactly

  Valid (738ms) (colibri2)
449
let
add_cst
(q:A.t) (da:t) : t
450
ensures { gamma result = image (fun y -> y +. A.real q) (gamma da) }
451
= let n = { div = da.div; rem = A.add q da.rem } in
452
let r = norm n in
453
image_bij pure { fun y -> y +. A.real q } pure { fun x -> x -. A.real q }
454
pure { gamma da } pure { gamma n };
455
r

The sums of an element of da and an element of db

  Valid (752ms) (colibri2)
458
let
add_forward
(da db:t) : t
459
ensures { S.subset (map2 (fun x y -> x +. y) (gamma da) (gamma db)) (gamma result) }
460
= let g = Q.gcd da.div db.div in
461
let r = norm { div = g; rem = A.add da.rem db.rem } in
462
let lemma sound (x y:real) : unit
463
requires { member x da }
464
requires { member y db }
465
ensures { dv (x +. y -. (A.real da.rem +. A.real db.rem)) (Q.real g) }
466
= dv_trans (x -. A.real da.rem) (Q.real da.div) (Q.real g);
467
dv_trans (y -. A.real db.rem) (Q.real db.div) (Q.real g);
468
dv_add (x -. A.real da.rem) (y -. A.real db.rem) (Q.real g) in
469
map2_sound pure { fun x y -> x +. y } pure { gamma da } pure { gamma db } pure { gamma r };
470
r

The differences

  Valid (651ms) (colibri2)
473
let
sub_forward
(da db:t) : t
474
ensures { S.subset (map2 (fun x y -> x -. y) (gamma da) (gamma db)) (gamma result) }
475
= let g = Q.gcd da.div db.div in
476
let r = norm { div = g; rem = A.sub da.rem db.rem } in
477
let lemma sound (x y:real) : unit
478
requires { member x da }
479
requires { member y db }
480
ensures { dv (x -. y -. (A.real da.rem -. A.real db.rem)) (Q.real g) }
481
= dv_trans (x -. A.real da.rem) (Q.real da.div) (Q.real g);
482
dv_trans (y -. A.real db.rem) (Q.real db.div) (Q.real g);
483
dv_sub (x -. A.real da.rem) (y -. A.real db.rem) (Q.real g) in
484
map2_sound pure { fun x y -> x -. y } pure { gamma da } pure { gamma db } pure { gamma r };
485
r

The opposites, exactly

  Valid (801ms) (colibri2)
488
let
neg_forward
(da:t) : t
489
ensures { gamma result = image (fun x -> -. x) (gamma da) }
490
ensures { exists k:int. A.real result.rem = -. A.real da.rem +. from_int k *. Q.real da.div }
491
= let n = { div = da.div; rem = A.neg da.rem } in
492
let r = norm n in
493
let lemma same (x:real) : unit
494
ensures { member x n <-> member (-. x) da }
495
= if pure { member x n } then dv_neg (x -. (-. A.real da.rem)) (Q.real da.div);
496
if pure { member (-. x) da } then dv_neg ((-. x) -. A.real da.rem) (Q.real da.div) in
497
image_bij pure { fun x -> -. x } pure { fun x -> -. x } pure { gamma da } pure { gamma n };
498
r

The products by the constant q

  Valid (52ms) (colibri2 5) (split_vc) (depth 1)
501
let
mul_cst
(q:Q.t) (da:t) : t
502
ensures { S.subset (image (fun x -> x *. Q.real q) (gamma da)) (gamma result) }
503
= let div = Q.mul da.div q in
504
let r = norm { div = div; rem = A.mul da.rem (A.of_q q) } in
505
let lemma sound (x:real) : unit
506
requires { member x da }
507
ensures { dv (x *. Q.real q -. A.real da.rem *. Q.real q) (Q.real div) }
508
= let k = quot pure { x -. A.real da.rem } pure { Q.real da.div } in
509
assert { x *. Q.real q -. A.real da.rem *. Q.real q = from_int k *. Q.real div } in
510
image_sound pure { fun x -> x *. Q.real q } pure { gamma da } pure { gamma r };
511
r

The products. Top exactly when a representative is not rational.

  Valid (1.6s) (colibri2 21) (cvc5) (split_vc) (depth 1)
514
let
mul_forward
(da db:t) : backward t
515
ensures { match result with
516
| R c -> A.rational da.rem /\ A.rational db.rem
517
/\ S.subset (map2 (fun x y -> x *. y) (gamma da) (gamma db)) (gamma c)
518
| Top -> not (A.rational da.rem /\ A.rational db.rem)
519
end }
520
= match A.view db.rem, A.view da.rem with
521
| A.Rat dbrem, A.Rat darem ->
522
let g1 = Q.mul da.div db.div in
523
let a1 = Q.mul da.div dbrem in
524
let a2 = Q.mul db.div darem in
525
let g2 = Q.gcd a1 g1 in
526
let g = Q.gcd a2 g2 in
527
let r = norm { div = g; rem = A.of_q ((Q.mul darem dbrem)) } in
528
let lemma sound (x y:real) : unit
529
requires { member x da }
530
requires { member y db }
531
ensures { member (x *. y) r }
532
= let i = any int ensures { x -. A.real da.rem = from_int result *. Q.real da.div } in
533
let j = any int ensures { y -. A.real db.rem = from_int result *. Q.real db.div } in
534
dv_trans (Q.real a1) (Q.real g2) (Q.real g);
535
dv_trans (Q.real g1) (Q.real g2) (Q.real g);
536
dv_mul (Q.real a1) (Q.real g) i;
537
dv_mul (Q.real a2) (Q.real g) j;
538
dv_mul (Q.real g1) (Q.real g) (i * j);
539
dv_add (from_int i *. Q.real a1) (from_int j *. Q.real a2) (Q.real g);
540
dv_add (from_int i *. Q.real a1 +. from_int j *. Q.real a2) (from_int (i * j) *. Q.real g1) (Q.real g);
541
let ghost ra = A.real da.rem in
542
let ghost rb = A.real db.rem in
543
let ghost dad = Q.real da.div in
544
let ghost dbd = Q.real db.div in
545
let ghost fi = from_int i in
546
let ghost fj = from_int j in
547
assert { from_int (i * j) = fi *. fj };
548
assert { Q.real a1 = dad *. rb /\ Q.real a2 = dbd *. ra /\ Q.real g1 = dad *. dbd };
549
assert { x = ra +. fi *. dad /\ y = rb +. fj *. dbd };
550
assert { x *. y = (ra +. fi *. dad) *. (rb +. fj *. dbd) };
551
assert { (ra +. fi *. dad) *. (rb +. fj *. dbd) -. ra *. rb
552
= fi *. (dad *. rb) +. fj *. (dbd *. ra) +. (fi *. fj) *. (dad *. dbd) };
553
assert { x *. y -. ra *. rb
554
= from_int i *. Q.real a1 +. from_int j *. Q.real a2 +. from_int (i * j) *. Q.real g1 } in
555
map2_sound pure { fun x y -> x *. y } pure { gamma da } pure { gamma db } pure { gamma r };
556
R r
557
| _ -> Top
558
end

into * b = r backward, for an into whose elements are all integers (otherwise Top). Sound for the integers x that satisfy it. Top exactly when the representatives are not rational, into does not have only integers, or gcd (b.div, r.div) divides b.rem (the quotients would not be coprime).

  Valid (1.6s) (colibri2 76) (cvc5) (split_vc 5) (depth 5)
565
let
mul_backward
(r:t) (into:option t) (b:t) : backward t
566
ensures { match result with
567
| R c -> A.rational b.rem /\ A.rational r.rem
568
/\ (match into with Some d -> integral d | None -> false end)
569
/\ not (dv (A.real b.rem) (Q.gcd_q b.div r.div))
570
/\ S.subset (S.inter ints (pre_mul (gamma b) (gamma r))) (gamma c)
571
| Top -> not (A.rational b.rem) \/ not (A.rational r.rem)
572
\/ (match into with Some d -> not (integral d) | None -> true end)
573
\/ dv (A.real b.rem) (Q.gcd_q b.div r.div)
574
end }
575
= match A.view b.rem, A.view r.rem with
576
| A.Rat brem, A.Rat rrem ->
577
let ok = match into with Some d -> is_integer d | None -> false end in
578
if ok then begin
579
let m = Q.gcd b.div r.div in
580
let d = Q.gcd m brem in
581
if Q.equal d m then Top
582
else begin
583
(* `m` does not divide `brem`, otherwise `d = m` *)
584
if pure { dv (Q.real brem) (Q.real m) } then begin
585
dv_self (Q.real m);
586
dv_antisym (Q.real d) (Q.real m)
587
end;
588
(* `d` is not zero: otherwise `m` is zero too *)
589
assert { Q.real d <> 0.0 };
590
let div = Q.divexact m d in
591
let r_rem' = Q.div rrem d in
592
(* the coefficients of Bezout of the quotients, which are coprime *)
593
let lemma coprime (a':int) (g' u v:int) : unit
594
requires { Q.real brem = from_int a' *. Q.real d }
595
requires { 0 <= g' }
596
requires { g' = u * a' + v * div }
597
requires { exists a'':int. a' = a'' * g' }
598
requires { exists d':int. div = d' * g' }
599
ensures { g' = 1 }
600
= let a'' = any int ensures { a' = result * g' } in
601
let d' = any int ensures { div = result * g' } in
602
let r = Q.mul (Q.of_bigint g') d in
603
assert { Q.real r = from_int g' *. Q.real d };
604
assert { from_int a' = from_int a'' *. from_int g' };
605
assert { from_int div = from_int d' *. from_int g' };
606
assert { Q.real brem = from_int a'' *. Q.real r };
607
assert { Q.real m = from_int d' *. Q.real r };
608
assert { dv (Q.real brem) (Q.real r) };
609
assert { dv (Q.real m) (Q.real r) };
610
let k = any int ensures { Q.real d = from_int result *. Q.real r } in
611
assert { from_int (k * g') = 1.0 };
612
unit_int k g' in
613
let lemma core (a' u v xi:int) (y:real) : unit
614
requires { Q.real brem = from_int a' *. Q.real d }
615
requires { u * a' + v * div = 1 }
616
requires { member y b }
617
requires { member (from_int xi *. y) r }
618
ensures { dv (from_int xi -. Q.real r_rem' *. from_int u) (from_int div) }
619
= let x = from_int xi in
620
let l = any int ensures { y -. A.real b.rem = from_int result *. Q.real b.div } in
621
let k = any int ensures { x *. y -. A.real r.rem = from_int result *. Q.real r.div } in
622
let beta = any int ensures { Q.real b.div = from_int result *. Q.real m } in
623
let rho = any int ensures { Q.real r.div = from_int result *. Q.real m } in
624
let t = k * rho - xi * l * beta in
625
let ghost fd = Q.real d in
626
let ghost fm = Q.real m in
627
let ghost rr = Q.real r_rem' in
628
assert { A.real b.rem = Q.real brem /\ A.real r.rem = Q.real rrem };
629
assert { fm = from_int div *. fd };
630
assert { rr *. fd = Q.real rrem };
631
assert { from_int t = from_int k *. from_int rho -. from_int xi *. from_int l *. from_int beta };
632
let ghost fl = from_int l in
633
let ghost fk = from_int k in
634
let ghost fb = from_int beta in
635
let ghost fr = from_int rho in
636
assert { Q.real brem = y -. fl *. Q.real b.div };
637
assert { Q.real rrem = x *. y -. fk *. Q.real r.div };
638
assert { x *. Q.real brem = x *. (y -. fl *. Q.real b.div) };
639
assert { x *. (y -. fl *. Q.real b.div) = x *. y -. (x *. fl) *. Q.real b.div };
640
assert { x *. Q.real brem -. Q.real rrem = fk *. Q.real r.div -. (x *. fl) *. Q.real b.div };
641
assert { Q.real b.div = fb *. fm /\ Q.real r.div = fr *. fm };
642
assert { x *. Q.real brem -. Q.real rrem = (fk *. fr -. x *. fl *. fb) *. fm };
643
assert { x *. Q.real brem -. Q.real rrem = from_int t *. fm };
644
assert { (x *. from_int a' -. rr) *. fd = (from_int t *. from_int div) *. fd };
645
assert { x *. from_int a' -. rr = from_int t *. from_int div };
646
let ghost fu = from_int u in
647
let ghost fa = from_int a' in
648
let ghost fv = from_int v in
649
let ghost fdiv = from_int div in
650
assert { fu *. fa +. fv *. fdiv = 1.0 };
651
assert { x *. (fu *. fa +. fv *. fdiv) = x };
652
assert { x -. rr *. fu = x *. (fu *. fa +. fv *. fdiv) -. rr *. fu };
653
assert { x -. rr *. fu = fu *. (x *. fa -. rr) +. fv *. x *. fdiv };
654
assert { from_int (u * t + xi * v) = fu *. from_int t +. x *. fv };
655
assert { x -. rr *. from_int u = from_int (u * t + xi * v) *. from_int div } in
656
let rem, ghost a', ghost u, ghost v =
657
if Q.is_zero r_rem' then begin
658
let ghost a' = Q.divexact brem d in
659
let ghost g', u, v = Z.gcdext a' div in
660
gcd_facts a' div;
661
coprime a' g' u v;
662
((Q.of_int 0), a', u, v)
663
end else begin
664
let a' = Q.divexact brem d in
665
let g', u, ghost v = Z.gcdext a' div in
666
gcd_facts a' div;
667
coprime a' g' u v;
668
((Q.mul r_rem' (Q.of_bigint u)), a', u, v)
669
end in
670
let c = norm { div = Q.of_bigint div; rem = A.of_q rem } in
671
let lemma sound (x y:real) : unit
672
requires { Real.is_integer x }
673
requires { member y b }
674
requires { member (x *. y) r }
675
ensures { member x c }
676
= let xi = Real.int_of x in
677
core a' u v xi y;
678
assert { Q.real rem = Q.real r_rem' *. from_int u } in
679
R c
680
end
681
end else Top
682
| _ -> Top
683
end

r is the Euclidean remainder of x by y (which is not zero), in the terms of mod_e_facts

687
predicate
is_mod_e
(x y r:real) =
688
(exists k:int. r = x -. from_int k *. y) /\ 0.0 <=. r /\ r <. abs y

The remainder is unique

  Valid (131ms) (cvc5)
691
let ghost
mod_e_unique
(r r0 y:real) (n:int) : unit
692
requires { 0.0 <=. r /\ r <. abs y }
693
requires { 0.0 <=. r0 /\ r0 <. abs y }
694
requires { r -. r0 = from_int n *. y }
695
ensures { r = r0 }
696
= if n >= 1 then begin
697
assert { from_int n >=. 1.0 };
698
if y >. 0.0 then begin
699
mul_nonneg (from_int n -. 1.0) y;
700
assert { from_int n *. y >=. y }
701
end else begin
702
mul_nonneg (from_int n -. 1.0) (-. y);
703
assert { from_int n *. y <=. y }
704
end
705
end else if n <= -1 then begin
706
assert { from_int n <=. -1.0 };
707
if y >. 0.0 then begin
708
mul_nonneg (-. from_int n -. 1.0) y;
709
assert { from_int n *. y <=. -. y }
710
end else begin
711
mul_nonneg (-. from_int n -. 1.0) (-. y);
712
assert { from_int n *. y >=. -. y }
713
end
714
end else assert { n = 0 }

The remainders mod_e x y of the x of a by the non zero y of d, when d is not the single real zero with a a singleton (the case of the remainder by zero is mod_e_forward of Export). Top exactly when the representative of d is not rational.

  Valid (1.4s) (colibri2 46) (cvc4 2) (cvc5 4) (split_vc) (depth 1)
720
let
mod_e_forward_nz
(a d:t) : backward t
721
requires { not (Q.real d.div = 0.0 /\ A.real d.rem = 0.0 /\ Q.real a.div = 0.0) }
722
ensures { match result with
723
| R c -> A.rational d.rem
724
/\ S.subset (map2nz (fun (x:real) (y:real) -> Real.mod_e x y) (gamma a) (gamma d)) (gamma c)
725
| Top -> not (A.rational d.rem)
726
end }
727
= let lemma to_is (x y r:real) : unit
728
requires { y <> 0.0 }
729
requires { r = Real.mod_e x y }
730
ensures { is_mod_e x y r }
731
= mod_e_facts x y;
732
assert { exists k:int. r = x -. from_int k *. y by k = Real.div_e x y } in
733
match A.view d.rem with
734
| A.Rat drem ->
735
if Q.is_zero d.div then begin
736
let divisible, ghost lam = Q.divisible a.div drem in
737
if divisible then begin
738
begin
739
dv_zero_iff (Q.real a.div);
740
let r0 = A.mod_e a.rem d.rem in
741
mod_e_facts pure { A.real a.rem } pure { A.real d.rem };
742
let ghost k0 = pure { Real.div_e (A.real a.rem) (A.real d.rem) } in
743
let c = singleton r0 in
744
let lemma sound (x y r:real) : unit
745
requires { member x a }
746
requires { member y d }
747
requires { is_mod_e x y r }
748
ensures { member r c }
749
= let k = any int ensures { x -. A.real a.rem = from_int result *. Q.real a.div } in
750
let j = any int ensures { r = x -. from_int result *. y } in
751
assert { y = Q.real drem };
752
assert { Q.real a.div = from_int lam *. Q.real drem };
753
let ghost fk = from_int k in
754
let ghost fl = from_int lam in
755
let ghost fj = from_int j in
756
let ghost fk0 = from_int k0 in
757
assert { A.real d.rem = Q.real drem };
758
assert { A.real r0 = A.real a.rem -. fk0 *. y };
759
assert { x -. A.real a.rem = fk *. (fl *. y) };
760
assert { from_int (k * lam - j + k0) = fk *. fl -. fj +. fk0 };
761
assert { r -. A.real r0 = (fk *. fl -. fj +. fk0) *. y };
762
assert { r -. A.real r0 = from_int (k * lam - j + k0) *. y };
763
mod_e_unique r (A.real r0) y (k * lam - j + k0) in
764
map2nz_sound pure { fun (x:real) (y:real) -> Real.mod_e x y } pure { gamma a } pure { gamma d } pure { gamma c };
765
R c
766
end
767
end else begin
768
let g = Q.gcd a.div drem in
769
let c = norm { div = g; rem = a.rem } in
770
let lemma sound (x y r:real) : unit
771
requires { member x a }
772
requires { member y d }
773
requires { is_mod_e x y r }
774
ensures { member r c }
775
= let k = any int ensures { x -. A.real a.rem = from_int result *. Q.real a.div } in
776
let j = any int ensures { r = x -. from_int result *. y } in
777
assert { y = Q.real drem };
778
dv_mul (Q.real a.div) (Q.real g) k;
779
dv_mul (Q.real drem) (Q.real g) j;
780
dv_sub (from_int k *. Q.real a.div) (from_int j *. Q.real drem) (Q.real g);
781
assert { r -. A.real a.rem = from_int k *. Q.real a.div -. from_int j *. Q.real drem } in
782
map2nz_sound pure { fun (x:real) (y:real) -> Real.mod_e x y } pure { gamma a } pure { gamma d } pure { gamma c };
783
R c
784
end
785
end else begin
786
let g1 = Q.gcd a.div drem in
787
let g = Q.gcd d.div g1 in
788
let c = norm { div = g; rem = a.rem } in
789
let lemma sound (x y r:real) : unit
790
requires { member x a }
791
requires { member y d }
792
requires { is_mod_e x y r }
793
ensures { member r c }
794
= let k = any int ensures { x -. A.real a.rem = from_int result *. Q.real a.div } in
795
let l = any int ensures { y -. A.real d.rem = from_int result *. Q.real d.div } in
796
let j = any int ensures { r = x -. from_int result *. y } in
797
dv_trans (Q.real a.div) (Q.real g1) (Q.real g);
798
dv_trans (Q.real drem) (Q.real g1) (Q.real g);
799
dv_mul (Q.real a.div) (Q.real g) k;
800
dv_mul (Q.real drem) (Q.real g) j;
801
dv_mul (Q.real d.div) (Q.real g) (j * l);
802
dv_sub (from_int k *. Q.real a.div) (from_int j *. Q.real drem) (Q.real g);
803
dv_sub (from_int k *. Q.real a.div -. from_int j *. Q.real drem) (from_int (j * l) *. Q.real d.div) (Q.real g);
804
assert { A.real d.rem = Q.real drem };
805
assert { from_int (j * l) = from_int j *. from_int l };
806
assert { y = Q.real drem +. from_int l *. Q.real d.div };
807
assert { r = (A.real a.rem +. from_int k *. Q.real a.div)
808
-. from_int j *. (Q.real drem +. from_int l *. Q.real d.div) };
809
assert { r -. A.real a.rem
810
= from_int k *. Q.real a.div -. from_int j *. Q.real drem -. from_int (j * l) *. Q.real d.div } in
811
map2nz_sound pure { fun (x:real) (y:real) -> Real.mod_e x y } pure { gamma a } pure { gamma d } pure { gamma c };
812
R c
813
end
814
| A.Irr -> Top
815
end

The n such that m = n mod d for a d of sd (not zero) and an m of sm

819
function
mod_num
(sd sm: S.set real) : S.set real =
820
fun n -> exists d m. S.mem d sd /\ S.mem m sm /\ d <> 0.0 /\ m = Real.mod_e n d

The numerators of mod_ = num mod den

  Valid (1.5s) (colibri2 21) (cvc5 2) (split_vc) (depth 1)
823
let
mod_e_backward_num
(den mod_:t) : backward t
824
ensures { match result with
825
| R c -> A.rational den.rem
826
/\ S.subset (mod_num (gamma den) (gamma mod_)) (gamma c)
827
| Top -> not (A.rational den.rem)
828
end }
829
= match A.view den.rem with
830
| A.Rat den_rem ->
831
let g1 = Q.gcd den.div den_rem in
832
let g = Q.gcd g1 mod_.div in
833
let r = norm { div = g; rem = mod_.rem } in
834
let lemma sound (n d m:real) (q:int) : unit
835
requires { member d den }
836
requires { member m mod_ }
837
requires { n = m +. d *. from_int q }
838
ensures { member n r }
839
= let l = any int ensures { d -. A.real den.rem = from_int result *. Q.real den.div } in
840
let p = any int ensures { m -. A.real mod_.rem = from_int result *. Q.real mod_.div } in
841
dv_trans (Q.real den_rem) (Q.real g1) (Q.real g);
842
dv_trans (Q.real den.div) (Q.real g1) (Q.real g);
843
dv_mul (Q.real den_rem) (Q.real g) q;
844
dv_mul (Q.real den.div) (Q.real g) (l * q);
845
dv_mul (Q.real mod_.div) (Q.real g) p;
846
dv_add (from_int p *. Q.real mod_.div) (from_int q *. Q.real den_rem) (Q.real g);
847
dv_add (from_int p *. Q.real mod_.div +. from_int q *. Q.real den_rem)
848
(from_int (l * q) *. Q.real den.div) (Q.real g);
849
assert { A.real den.rem = Q.real den_rem };
850
assert { from_int (l * q) = from_int l *. from_int q };
851
assert { n -. A.real mod_.rem
852
= from_int p *. Q.real mod_.div +. from_int q *. Q.real den_rem
853
+. from_int (l * q) *. Q.real den.div } in
854
let lemma fin (n d m:real) : unit
855
requires { member d den }
856
requires { member m mod_ }
857
requires { d <> 0.0 }
858
requires { m = Real.mod_e n d }
859
ensures { member n r }
860
= mod_e_facts n d;
861
sound n d m (pure { Real.div_e n d }) in
862
R r
863
| A.Irr -> Top
864
end

The largest element of da that is not above a, for a da that is not a singleton

  Valid (665ms) (colibri2)
868
let
floor_a_nz
(a:A.t) (da:t) : A.t
869
requires { Q.real da.div <> 0.0 }
870
ensures { S.mem (A.real result) (gamma da) /\ A.real result <=. A.real a }
871
ensures { forall z. S.mem z (gamma da) -> z <=. A.real a -> z <=. A.real result }
872
= let m = Q.abs da.div in
873
let x = A.sub a da.rem in
874
let q = A.round_down_to x m in
875
let r = A.add (A.of_q q) da.rem in
876
let ghost k = quot pure { Q.real q } pure { Q.real m } in
877
dv_abs (A.real r -. A.real da.rem) (Q.real da.div);
878
assert { A.real r -. A.real da.rem = from_int k *. Q.real m };
879
let lemma best (z:real) : unit
880
requires { member z da }
881
requires { z <=. A.real a }
882
ensures { z <=. A.real r }
883
= dv_abs (z -. A.real da.rem) (Q.real da.div);
884
let j = quot pure { z -. A.real da.rem } pure { Q.real m } in
885
if j >= k + 1 then assert { from_int j *. Q.real m >=. from_int (k + 1) *. Q.real m };
886
assert { j <= k };
887
assert { from_int j *. Q.real m <=. from_int k *. Q.real m } in
888
r

The smallest element of da that is not below a, for a da that is not a singleton

  Valid (149ms) (colibri2)
892
let
ceil_a_nz
(a:A.t) (da:t) : A.t
893
requires { Q.real da.div <> 0.0 }
894
ensures { S.mem (A.real result) (gamma da) /\ A.real a <=. A.real result }
895
ensures { forall z. S.mem z (gamma da) -> A.real a <=. z -> A.real result <=. z }
896
= let m = Q.abs da.div in
897
let x = A.sub a da.rem in
898
let q = A.round_up_to x m in
899
let r = A.add (A.of_q q) da.rem in
900
let ghost k = quot pure { Q.real q } pure { Q.real m } in
901
dv_abs (A.real r -. A.real da.rem) (Q.real da.div);
902
assert { A.real r -. A.real da.rem = from_int k *. Q.real m };
903
let lemma best (z:real) : unit
904
requires { member z da }
905
requires { A.real a <=. z }
906
ensures { A.real r <=. z }
907
= dv_abs (z -. A.real da.rem) (Q.real da.div);
908
let j = quot pure { z -. A.real da.rem } pure { Q.real m } in
909
if j <= k - 1 then assert { from_int j *. Q.real m <=. from_int (k - 1) *. Q.real m };
910
assert { j >= k };
911
assert { from_int j *. Q.real m >=. from_int k *. Q.real m } in
912
r

The integers a and b have the same bits on the positions of mask (the meaning of KnownBits.cst_mask)

916
predicate
agree
(mask a b:int) =
917
forall j. 0 <= j -> Zbit.bittest mask j -> (Zbit.bittest a j <-> Zbit.bittest b j)

The divisor of c is an odd integer

920
predicate
odd_div
(c:t) = exists dd:int. Q.real c.div = from_int dd /\ Zbit.bittest dd 0

The bits shared by all the integers of c, as a KnownBits.t. It is KnownBits.top exactly when the divisor is zero or not an even integer, or the representative is not an integer.

  Valid (1.6s) (colibri2 16) (cvc4) (cvc5 2) (split_vc) (depth 1)
925
let
to_knownbits
(c:t) : KB.t
926
ensures { forall n:int. S.mem (from_int n) (gamma c) -> KB.mem n result }
927
ensures { result = KB.top <->
928
(Q.real c.div = 0.0 \/ not (Real.is_integer (Q.real c.div))
929
\/ not (Real.is_integer (A.real c.rem)) \/ odd_div c) }
930
= if not (Q.is_zero c.div) && Q.is_integer c.div && A.is_integer c.rem then begin
931
let dd = Q.to_z c.div in
932
let rv = A.to_z c.rem in
933
let i = Zbit.trailing_zeros dd in
934
if i = 0 then KB.top
935
else begin
936
let mask = ZbitInt.mask_int i in
937
(* `dd` is a multiple of `2^i` *)
938
LowBits.sub_low dd 0 i;
939
let ghost m = any int ensures { dd - 0 = result * Zbit.lsl 1 i } in
940
let lemma sound (n:int) : unit
941
requires { member (from_int n) c }
942
ensures { forall j. 0 <= j -> Zbit.bittest mask j -> (Zbit.bittest n j <-> Zbit.bittest rv j) }
943
= let k = any int ensures { from_int n -. A.real c.rem = from_int result *. Q.real c.div } in
944
assert { from_int (n - rv) = from_int (k * dd) };
945
assert { n - rv = (k * m) * Zbit.lsl 1 i };
946
LowBits.same_low n rv (k * m) i;
947
let lemma low (j:int) : unit
948
requires { 0 <= j }
949
requires { Zbit.bittest mask j }
950
ensures { j < i }
951
= () in () in
952
let r = KB.cst_mask rv mask in
953
(* `r` is not top: the bit 0 is in `mask` and `rv` has it set or not *)
954
if pure { r = KB.top } then begin
955
assert { Zbit.bittest mask 0 };
956
let x = Zbit.lxor rv 1 in
957
assert { KB.mem x r };
958
assert { Zbit.bittest x 0 <-> not (Zbit.bittest rv 0) }
959
end;
960
r
961
end
962
end else KB.top

The integers of a KnownBits.t

  Valid (787ms) (colibri2 13) (cvc5) (split_vc) (depth 1)
965
let
of_knownbits
(k:KB.t) : t
966
ensures { forall n:int. KB.mem n k -> S.mem (from_int n) (gamma result) }
967
= let l = k.KB.l in
968
let u = k.KB.u in
969
let d = Zbit.lxor l u in
970
let lemma dbit (j:int) : unit
971
requires { 0 <= j }
972
ensures { Zbit.bittest d j <-> not (Zbit.bittest l j <-> Zbit.bittest u j) }
973
= () in
974
if d = 0 then begin
975
let r = singleton (A.of_bigint l) in
976
let lemma sound (n:int) : unit
977
requires { Zbit.subset u n }
978
requires { Zbit.subset n l }
979
ensures { member (from_int n) r }
980
= let lemma bit (j:int) : unit
981
requires { 0 <= j }
982
ensures { Zbit.bittest n j <-> Zbit.bittest l j }
983
= () in
984
Zbit.ext_bittest n l in
985
r
986
end else begin
987
let t = Zbit.trailing_zeros d in
988
if t = 0 then integers ()
989
else begin
990
let rv = Zbit.land l (ZbitInt.mask_int t) in
991
let c = norm { div = Q.of_bigint (ZbitInt.lsl_int 1 t); rem = A.of_bigint rv } in
992
let lemma sound (n:int) : unit
993
requires { Zbit.subset u n }
994
requires { Zbit.subset n l }
995
ensures { member (from_int n) c }
996
= let lemma bit (j:int) : unit
997
requires { 0 <= j < t }
998
ensures { Zbit.bittest n j <-> Zbit.bittest rv j }
999
= () in
1000
LowBits.sub_low n rv t;
1001
let m = any int ensures { n - rv = result * Zbit.lsl 1 t } in
1002
assert { from_int n -. from_int rv = from_int m *. from_int (Zbit.lsl 1 t) } in
1003
c
1004
end
1005
end

The integers of c, exactly

  Valid (41ms) (colibri2)
1008
let
reduce_integers
(c:t) : option t
1009
ensures { match result with
1010
| Some r -> gamma r = S.inter ints (gamma c)
1011
| None -> S.is_empty (S.inter ints (gamma c))
1012
end }
1013
= inter (integers ()) c

The truncations of the elements of x

  Valid (46ms) (colibri2)
1016
let
truncate_forward
(x:t) : t
1017
ensures { S.subset (image (fun v -> from_int (Truncate.truncate v)) (gamma x)) (gamma result) }
1018
= let r = integers () in
1019
let lemma all (v:real) : unit
1020
ensures { S.mem (from_int (Truncate.truncate v)) (gamma r) }
1021
= ints_intro (Truncate.truncate v) in
1022
image_sound pure { fun v -> from_int (Truncate.truncate v) } pure { gamma x } pure { gamma r };
1023
r

The ceilings

  Valid (127ms) (colibri2)
1026
let
ceil_forward
(x:t) : t
1027
ensures { S.subset (image (fun v -> from_int (Truncate.ceil v)) (gamma x)) (gamma result) }
1028
= if Q.is_integer x.div then begin
1029
let c = A.of_bigint (A.ceil_z x.rem) in
1030
let r = norm { div = x.div; rem = c } in
1031
let lemma sound (v:real) : unit
1032
requires { member v x }
1033
ensures { dv (from_int (ceil v) -. A.real c) (Q.real x.div) }
1034
= let m = any int ensures { Q.real x.div = from_int result } in
1035
let k = any int ensures { v -. A.real x.rem = from_int result *. Q.real x.div } in
1036
assert { v = A.real x.rem +. from_int (k * m) };
1037
ceil_shift (A.real x.rem) (k * m);
1038
assert { from_int (ceil v) -. A.real c = from_int k *. Q.real x.div } in
1039
image_sound pure { fun v -> from_int (Truncate.ceil v) } pure { gamma x } pure { gamma r };
1040
r
1041
end else begin
1042
let r = integers () in
1043
let lemma all (v:real) : unit
1044
ensures { S.mem (from_int (Truncate.ceil v)) (gamma r) }
1045
= ints_intro (Truncate.ceil v) in
1046
image_sound pure { fun v -> from_int (Truncate.ceil v) } pure { gamma x } pure { gamma r };
1047
r
1048
end

The floors

  Valid (370ms) (colibri2)
1051
let
floor_forward
(x:t) : t
1052
ensures { S.subset (image (fun v -> from_int (Truncate.floor v)) (gamma x)) (gamma result) }
1053
= if Q.is_integer x.div then begin
1054
let c = A.of_bigint (A.floor_z x.rem) in
1055
let r = norm { div = x.div; rem = c } in
1056
let lemma sound (v:real) : unit
1057
requires { member v x }
1058
ensures { dv (from_int (floor v) -. A.real c) (Q.real x.div) }
1059
= let m = any int ensures { Q.real x.div = from_int result } in
1060
let k = any int ensures { v -. A.real x.rem = from_int result *. Q.real x.div } in
1061
assert { v = A.real x.rem +. from_int (k * m) };
1062
floor_shift (A.real x.rem) (k * m);
1063
assert { from_int (floor v) -. A.real c = from_int k *. Q.real x.div } in
1064
image_sound pure { fun v -> from_int (Truncate.floor v) } pure { gamma x } pure { gamma r };
1065
r
1066
end else begin
1067
let r = integers () in
1068
let lemma all (v:real) : unit
1069
ensures { S.mem (from_int (Truncate.floor v)) (gamma r) }
1070
= ints_intro (Truncate.floor v) in
1071
image_sound pure { fun v -> from_int (Truncate.floor v) } pure { gamma x } pure { gamma r };
1072
r
1073
end

The values of relu. Top exactly when the representative is not rational.

  Valid (774ms) (cvc4)
1077
let
relu_forward
(a:t) : backward t
1078
ensures { match result with
1079
| R c -> A.rational a.rem
1080
/\ S.subset (image (fun x -> if x <. 0.0 then 0.0 else x) (gamma a)) (gamma c)
1081
| Top -> not (A.rational a.rem)
1082
end }
1083
= rat_neg (A.real a.rem);
1084
let z = singleton ((A.of_int 0)) in
1085
match union z a with
1086
| R c ->
1087
let lemma pw (x:real) : unit
1088
requires { member x a }
1089
ensures { member (if x <. 0.0 then 0.0 else x) c }
1090
= if x <. 0.0 then begin
1091
assert { member 0.0 z };
1092
sub_member z c 0.0
1093
end else sub_member a c x in
1094
image_sound pure { fun x -> if x <. 0.0 then 0.0 else x } pure { gamma a } pure { gamma c };
1095
R c
1096
| Top -> Top
1097
end

The absolute values. Top exactly when the representative is not rational.

  Valid (135ms) (colibri2 13) (split_vc) (depth 1)
1101
let
abs_forward
(a:t) : backward t
1102
ensures { match result with
1103
| R c -> A.rational a.rem
1104
/\ S.subset (image (fun x -> abs x) (gamma a)) (gamma c)
1105
| Top -> not (A.rational a.rem)
1106
end }
1107
= let n = neg_forward a in
1108
rat_q a.div;
1109
let ghost k = any int ensures { A.real n.rem = -. A.real a.rem +. from_int result *. Q.real a.div } in
1110
rat_double (A.real a.rem) (A.real n.rem) (Q.real a.div) k;
1111
match union a n with
1112
| R c ->
1113
let lemma pw (x:real) : unit
1114
requires { member x a }
1115
ensures { member (abs x) c }
1116
= if x >=. 0.0 then begin
1117
assert { abs x = x };
1118
sub_member a c x
1119
end else begin
1120
assert { abs x = -. x };
1121
assert { member (-. x) n };
1122
sub_member n c (-. x)
1123
end in
1124
image_sound pure { fun x -> abs x } pure { gamma a } pure { gamma c };
1125
R c
1126
| Top -> Top
1127
end

y is in a or in the negation of a when |y| is in a

  Valid (44ms) (colibri2)
1130
let ghost
abs_cases
(a n:t) (y:real) : unit
1131
requires { forall x. member x n <-> member (-. x) a }
1132
requires { member (abs y) a }
1133
ensures { member y a \/ member y n }
1134
= if y >=. 0.0 then assert { abs y = y }
1135
else assert { abs y = -. y }

The y whose absolute value is in a. Top exactly when the representative is not rational.

  Valid (2.5s) (colibri2 6) (cvc5 2) (split_vc 2) (depth 2)
1139
let
abs_backward
(a:t) : backward t
1140
ensures { match result with
1141
| R c -> A.rational a.rem
1142
/\ S.subset (preimage (fun y -> abs y) (gamma a)) (gamma c)
1143
| Top -> not (A.rational a.rem)
1144
end }
1145
= let n = neg_forward a in
1146
rat_q a.div;
1147
let ghost k = any int ensures { A.real n.rem = -. A.real a.rem +. from_int result *. Q.real a.div } in
1148
rat_double (A.real a.rem) (A.real n.rem) (Q.real a.div) k;
1149
match union a n with
1150
| R c ->
1151
let lemma back (y:real) : unit
1152
requires { member (abs y) a }
1153
ensures { member y c }
1154
= abs_cases a n y in
1155
R c
1156
| Top -> Top
1157
end

The integer divisions have an integer result

  Valid (54ms) (colibri2)
1160
let
div_e_forward
(a b:t) : t
1161
ensures { S.subset (map2nz (fun (x:real) (y:real) -> from_int (Real.div_e x y)) (gamma a) (gamma b))
1162
(gamma result) }
1163
= let r = integers () in
1164
let lemma all (x y:real) : unit
1165
ensures { S.mem (from_int (Real.div_e x y)) (gamma r) }
1166
= ints_intro pure { Real.div_e x y } in
1167
map2nz_sound pure { fun (x:real) (y:real) -> from_int (Real.div_e x y) }
1168
pure { gamma a } pure { gamma b } pure { gamma r };
1169
r
1170
Valid (55ms) (colibri2)
1171
let
div_f_forward
(a b:t) : t
1172
ensures { S.subset (map2nz (fun (x:real) (y:real) -> from_int (Real.div_f x y)) (gamma a) (gamma b))
1173
(gamma result) }
1174
= let r = integers () in
1175
let lemma all (x y:real) : unit
1176
ensures { S.mem (from_int (Real.div_f x y)) (gamma r) }
1177
= ints_intro pure { Real.div_f x y } in
1178
map2nz_sound pure { fun (x:real) (y:real) -> from_int (Real.div_f x y) }
1179
pure { gamma a } pure { gamma b } pure { gamma r };
1180
r
1181
Valid (64ms) (colibri2)
1182
let
div_t_forward
(a b:t) : t
1183
ensures { S.subset (map2nz (fun (x:real) (y:real) -> from_int (Real.div_t x y)) (gamma a) (gamma b))
1184
(gamma result) }
1185
= let r = integers () in
1186
let lemma all (x y:real) : unit
1187
ensures { S.mem (from_int (Real.div_t x y)) (gamma r) }
1188
= ints_intro pure { Real.div_t x y } in
1189
map2nz_sound pure { fun (x:real) (y:real) -> from_int (Real.div_t x y) }
1190
pure { gamma a } pure { gamma b } pure { gamma r };
1191
r
1192
end