Common — library colibrilib.fp_facts — module Facts

Facts derived from the interface

Each fact on the order has a version with requires, used when the hypotheses are known, and a total version (_any, implications) that can be called in any branch.

12
module Facts
13
use int.Int
14
use int.Power
15
use int.EuclideanDivision
16
use real.RealInfix
17
use colibrilib.fp.Ereal
18
use colibrilib.fbin.Fp
19
Valid (28ms) (colibri2)
20
let ghost
le_refl
(x: t) : unit
21
requires { is_not_nan x }
22
ensures { le_dz x x }
23
= {proof…} () {qed}
24
Valid (27ms) (colibri2)
25
let ghost
le_trans
(x y z: t) : unit
26
requires { le_dz x y /\ le_dz y z }
27
ensures { le_dz x z }
28
= {proof…} () {qed}
29
Valid (35ms) (colibri2)
30
let ghost
lt_le_trans
(x y z: t) : unit
31
requires { lt_dz x y /\ le_dz y z }
32
ensures { lt_dz x z }
33
= {proof…} () {qed}
34
Valid (25ms) (colibri2)
35
let ghost
le_lt_trans
(x y z: t) : unit
36
requires { le_dz x y /\ lt_dz y z }
37
ensures { lt_dz x z }
38
= {proof…} () {qed}
39
Valid (20ms) (colibri2)
40
let ghost
total
(x y: t) : unit
41
requires { is_not_nan x /\ is_not_nan y /\ fmt x = fmt y }
42
ensures { le_dz x y \/ lt_dz y x }
43
= {proof…} () {qed}
44
Valid (23ms) (colibri2)
45
let ghost
lt_not_le
(x y: t) : unit
46
requires { lt_dz x y }
47
ensures { not (le_dz y x) }
48
= {proof…} () {qed}
49
Valid (28ms) (colibri2)
50
let ghost
lt_le
(x y: t) : unit
51
requires { lt_dz x y }
52
ensures { le_dz x y }
53
= {proof…} () {qed}
54
Valid (23ms) (colibri2)
55
let ghost
le_refl_any
(x: t) : unit
56
ensures { is_not_nan x -> le_dz x x }
57
= if not (is_nan x) then le_refl x
58
Valid (22ms) (colibri2)
59
let ghost
le_not_nan_any
(x y: t) : unit
60
ensures { le_dz x y -> is_not_nan x /\ is_not_nan y }
61
= ()
62
Valid (27ms) (colibri2)
63
let ghost
le_trans_any
(x y z: t) : unit
64
ensures { le_dz x y -> le_dz y z -> le_dz x z }
65
= if le_diff_zero x y && le_diff_zero y z then le_trans x y z
66
Valid (31ms) (colibri2)
67
let ghost
lt_le_trans_any
(x y z: t) : unit
68
ensures { lt_dz x y -> le_dz y z -> lt_dz x z }
69
= if lt_diff_zero x y && le_diff_zero y z then lt_le_trans x y z
70
Valid (33ms) (colibri2)
71
let ghost
le_lt_trans_any
(x y z: t) : unit
72
ensures { le_dz x y -> lt_dz y z -> lt_dz x z }
73
= if le_diff_zero x y && lt_diff_zero y z then le_lt_trans x y z
74
Valid (30ms) (colibri2)
75
let ghost
total_any
(x y: t) : unit
76
ensures { is_not_nan x -> is_not_nan y -> fmt x = fmt y ->
77
le_dz x y \/ lt_dz y x }
78
= if not (is_nan x) && not (is_nan y) && pure { fmt x = fmt y } then total x y
79
Valid (25ms) (colibri2)
80
let ghost
lt_not_le_any
(x y: t) : unit
81
ensures { lt_dz x y -> not (le_dz y x) }
82
= if lt_diff_zero x y then lt_not_le x y
83
Valid (24ms) (colibri2)
84
let ghost
lt_le_any
(x y: t) : unit
85
ensures { lt_dz x y -> le_dz x y }
86
= if lt_diff_zero x y then lt_le x y

The minimum and the maximum

  Valid (22ms) (colibri2)
90
let
min_diff_zero
(x y: t) : t
91
requires { is_not_nan x /\ is_not_nan y /\ fmt x = fmt y }
92
ensures { (result = x /\ le_dz x y) \/ (result = y /\ le_dz y x) }
93
= if le_diff_zero x y then x else begin total x y; lt_le y x; y end
94
Valid (25ms) (colibri2)
95
let
max_diff_zero
(x y: t) : t
96
requires { is_not_nan x /\ is_not_nan y /\ fmt x = fmt y }
97
ensures { (result = y /\ le_dz x y) \/ (result = x /\ le_dz y x) }
98
= if le_diff_zero x y then y else begin total x y; lt_le y x; x end

Negation

  Valid (35ms) (colibri2 4) (split_vc) (depth 1)
102
let ghost
neg_neg
(x: t) : unit
103
ensures { neg (neg x) = x }
104
= {proof…}
105
if is_nan x then assert { neg (neg x) = not_a_number (fmt x) = x }
106
else begin
107
assert { index (neg (neg x)) = index x };
108
assert { of_index (fmt x) (index (neg (neg x))) = of_index (fmt x) (index x) }
109
end
110
{qed}

Successor and predecessor

succ_dz, pred_dz and their implementations succ_diff_zero, pred_diff_zero are in Intf; their properties are below, not ensures that every call would bring into the context.

  Valid (255ms) (colibri2 4) (cvc4) (split_vc) (depth 1)
118
let ghost
succ_gt
(x: t) : unit
119
requires { is_not_nan x /\ not is_plus_infinity x }
120
ensures { is_not_nan (succ_dz x) /\ lt_dz x (succ_dz x) }
121
= {proof…}
122
assert { lt_dz x (plus_infinity (fmt x)) };
123
index_range (plus_infinity (fmt x)); index_range x;
124
of_index_range (fmt x) (index x + 1)
125
{qed}

No float between x and its successor

  Valid (276ms) (colibri2 4) (cvc5) (split_vc) (depth 1)
128
let ghost
succ_least
(x y: t) : unit
129
requires { lt_dz x y }
130
ensures { le_dz (succ_dz x) y }
131
= {proof…}
132
index_range x; index_range y; of_index_range (fmt x) (index x + 1);
133
assert { index (succ_dz x) = index x + 1 <= index y }
134
{qed}
135
Valid (39ms) (colibri2)
136
let ghost
pred_lt
(x: t) : unit
137
requires { is_not_nan x /\ not is_minus_infinity x }
138
ensures { is_not_nan (pred_dz x) /\ lt_dz (pred_dz x) x }
139
= {proof…}
140
assert { lt_dz (minus_infinity (fmt x)) x };
141
index_range (minus_infinity (fmt x)); index_range x;
142
of_index_range (fmt x) (index x - 1)
143
{qed}
144
Valid (282ms) (colibri2 4) (cvc5) (split_vc) (depth 1)
145
let ghost
pred_greatest
(x y: t) : unit
146
requires { lt_dz y x }
147
ensures { le_dz y (pred_dz x) }
148
= {proof…}
149
index_range x; index_range y; of_index_range (fmt x) (index x - 1);
150
assert { index y <= index x - 1 = index (pred_dz x) }
151
{qed}

Addition

The positive floats are above the negative ones

  Valid (21ms) (colibri2)
156
let ghost
le_positive
(x y: t) : unit
157
requires { le_dz x y } ensures { is_positive x -> is_positive y }
158
= {proof…} le_not_nan x y {qed}

NaN on a NaN or on two infinities of opposite signs; an infinity otherwise wins

  Valid (329ms) (cvc5)
162
let ghost
add_special
(m: mode) (x y: t) : unit
163
ensures { is_nan (fp_add m x y) <->
164
is_nan x \/ is_nan y \/ (is_plus_infinity x /\ is_minus_infinity y)
165
\/ (is_minus_infinity x /\ is_plus_infinity y) }
166
ensures { is_not_nan x /\ is_not_nan y ->
167
(is_plus_infinity x /\ not is_minus_infinity y) \/
168
(is_plus_infinity y /\ not is_minus_infinity x) ->
169
is_plus_infinity (fp_add m x y) }
170
ensures { is_not_nan x /\ is_not_nan y ->
171
(is_minus_infinity x /\ not is_plus_infinity y) \/
172
(is_minus_infinity y /\ not is_plus_infinity x) ->
173
is_minus_infinity (fp_add m x y) }
174
= {proof…}
175
plus_infinity_unique (plus_infinity (fmt x));
176
minus_infinity_unique (minus_infinity (fmt x));
177
if is_not_nan x && is_not_nan y then
178
round_f_not_nan (fmt x) m (add_zneg m x y) (eadd (ext x) (ext y))
179
{qed}

add is increasing in both arguments where it is not NaN

  Valid (334ms) (cvc5)
182
let ghost
add_box
(m: mode) (x1 x2 y1 y2: t) : unit
183
requires { le_dz x1 x2 /\ le_dz y1 y2 }
184
requires { is_not_nan (fp_add m x1 y1) /\ is_not_nan (fp_add m x2 y2) }
185
ensures { le_dz (fp_add m x1 y1) (fp_add m x2 y2) }
186
= {proof…}
187
le_not_nan x1 x2; le_not_nan y1 y2;
188
add_special m x1 y1; add_special m x2 y2;
189
eadd_le2 (ext x1) (ext x2) (ext y1) (ext y2);
190
le_positive x1 x2; le_positive y1 y2;
191
assert { add_zneg m x2 y2 -> add_zneg m x1 y1 }
192
{qed}

Multiplication

The sign of the extended real of a float

  Valid (523ms) (colibri2)
197
let ghost
ext_sign
(x: t) : unit
198
requires { is_not_nan x }
199
ensures { is_positive x -> ele (Fin 0.0) (ext x) }
200
ensures { not is_positive x -> ele (ext x) (Fin 0.0) }
201
ensures { is_zero x <-> ext x = Fin 0.0 }
202
= {proof…}
203
of_index_range (fmt x) 0; of_index_range (fmt x) (-1);
204
let ghost pz = of_index (fmt x) 0 in
205
let ghost nz = of_index (fmt x) (-1) in
206
if pure { is_positive x } then assert { le_dz pz x }
207
else assert { le_dz x nz }
208
{qed}

|x1| <= |x2|, both of the sign p (true: positive)

211
predicate
mag_le
(p: bool) (x1 x2: t) =
212
is_not_nan x1 /\ is_not_nan x2 /\
213
if p then is_positive x1 /\ le_dz x1 x2
214
else not is_positive x1 /\ le_dz x2 x1
215
Valid (42ms) (colibri2 10) (split_vc 3) (depth 3)
216
let ghost
mag_le_sign
(p: bool) (x1 x2: t) : unit
217
requires { mag_le p x1 x2 }
218
ensures { is_positive x1 <-> p }
219
ensures { is_positive x2 <-> p }
220
ensures { emag_le p (ext x1) (ext x2) }
221
= {proof…}
222
ext_sign x1; ext_sign x2;
223
if p then le_positive x1 x2
224
else if pure { is_positive x2 } then le_positive x2 x1
225
{qed}

NaN on a NaN or on 0 times an infinity; the signs

  Valid (109ms) (cvc4)
228
let ghost
mul_special
(m: mode) (x y: t) : unit
229
ensures { is_nan (fp_mul m x y) <-> is_nan x \/ is_nan y
230
\/ (is_zero x /\ is_infinity y) \/ (is_infinity x /\ is_zero y) }
231
ensures { is_not_nan x /\ is_not_nan y ->
232
(is_infinity x /\ not is_zero y) \/ (is_infinity y /\ not is_zero x) ->
233
fp_mul m x y =
234
if mul_zneg x y then minus_infinity (fmt x) else plus_infinity (fmt x) }
235
ensures { is_not_nan x /\ is_not_nan y ->
236
(is_zero x /\ not is_infinity y) \/ (is_zero y /\ not is_infinity x) ->
237
is_zero (fp_mul m x y) /\ (is_positive (fp_mul m x y) <-> not mul_zneg x y) }
238
= {proof…}
239
plus_infinity_unique (plus_infinity (fmt x));
240
minus_infinity_unique (minus_infinity (fmt x));
241
if is_not_nan x && is_not_nan y then begin
242
ext_sign x; ext_sign y;
243
round_f_not_nan (fmt x) m (mul_zneg x y) (emul (ext x) (ext y))
244
end
245
{qed}

The product is increasing in the magnitudes, in a quadrant

  Valid (421ms) (cvc5)
248
let ghost
mul_mag
(m: mode) (p q: bool) (x1 x2 y1 y2: t) : unit
249
requires { mag_le p x1 x2 /\ mag_le q y1 y2 }
250
requires { is_not_nan (fp_mul m x1 y1) /\ is_not_nan (fp_mul m x2 y2) }
251
ensures { if p = q then le_dz (fp_mul m x1 y1) (fp_mul m x2 y2)
252
else le_dz (fp_mul m x2 y2) (fp_mul m x1 y1) }
253
= {proof…}
254
mag_le_sign p x1 x2; mag_le_sign q y1 y2;
255
ext_sign x1; ext_sign x2; ext_sign y1; ext_sign y2;
256
assert { mul_zneg x1 y1 = mul_zneg x2 y2 };
257
emul_mag p q (ext x1) (ext x2) (ext y1) (ext y2)
258
{qed}

Division

NaN on a NaN, on 0/0 and on inf/inf; the signs

  Valid (522ms) (colibri2 7) (cvc4) (cvc5 2) (split_vc) (depth 1)
263
let ghost
div_special
(m: mode) (x y: t) : unit
264
ensures { is_nan (fp_div m x y) <-> is_nan x \/ is_nan y
265
\/ (is_zero x /\ is_zero y) \/ (is_infinity x /\ is_infinity y) }
266
ensures { is_not_nan x /\ is_not_nan y ->
267
(is_infinity x /\ not is_infinity y) \/ (is_zero y /\ not is_zero x) ->
268
fp_div m x y =
269
if mul_zneg x y then minus_infinity (fmt x) else plus_infinity (fmt x) }
270
ensures { is_not_nan x /\ is_not_nan y ->
271
(is_zero x /\ not is_zero y) \/ (is_infinity y /\ not is_infinity x) ->
272
is_zero (fp_div m x y) /\ (is_positive (fp_div m x y) <-> not mul_zneg x y) }
273
= {proof…}
274
plus_infinity_unique (plus_infinity (fmt x));
275
minus_infinity_unique (minus_infinity (fmt x));
276
if is_not_nan x && is_not_nan y then begin
277
ext_sign x; ext_sign y;
278
round_f_not_nan (fmt x) m (mul_zneg x y) (ediv (ext x) (ext y));
279
match ext y with
280
| Fin c -> if pure { c <> 0.0 } then begin
281
if pure { c >. 0.0 } then assert { 1.0 /. c >. 0.0 }
282
else assert { 1.0 /. c <. 0.0 }
283
end
284
| _ -> ()
285
end;
286
match ext x with
287
| Fin c -> assert { c *. 0.0 = 0.0 }
288
| _ -> ()
289
end
290
end
291
{qed}

The quotient is increasing in the magnitude of the dividend and decreasing in the magnitude of the divisor, in a quadrant

  Valid (805ms) (cvc5)
295
let ghost
div_mag
(m: mode) (p q: bool) (x1 x2 y1 y2: t) : unit
296
requires { mag_le p x1 x2 /\ mag_le q y1 y2 }
297
requires { is_not_nan (fp_div m x1 y2) /\ is_not_nan (fp_div m x2 y1) }
298
ensures { if p = q then le_dz (fp_div m x1 y2) (fp_div m x2 y1)
299
else le_dz (fp_div m x2 y1) (fp_div m x1 y2) }
300
= {proof…}
301
mag_le_sign p x1 x2; mag_le_sign q y1 y2;
302
ext_sign x1; ext_sign x2; ext_sign y1; ext_sign y2;
303
div_special m x1 y2; div_special m x2 y1;
304
let ghost r1 = fp_div m x1 y2 in
305
let ghost r2 = fp_div m x2 y1 in
306
if is_zero y1 then begin
307
if pure { p = q } then begin
308
if pure { r1 <> plus_infinity (fmt x1) } then begin
309
lt_plus_infinity r1; lt_le r1 r2 end
310
else le_refl r1
311
end else begin
312
if pure { r1 <> minus_infinity (fmt x1) } then begin
313
minus_infinity_lt r1; lt_le r2 r1 end
314
else le_refl r1
315
end
316
end else begin
317
assert { mul_zneg x1 y2 = mul_zneg x2 y1 };
318
einv_mag q (ext y1) (ext y2);
319
emul_mag p q (ext x1) (ext x2) (einv (ext y2)) (einv (ext y1))
320
end
321
{qed}

Square root

  Valid (39ms) (colibri2)
325
let ghost
sqrt_special
(m: mode) (x: t) : unit
326
ensures { is_nan (fp_sqrt m x) <->
327
is_nan x \/ (not is_positive x /\ not is_zero x) }
328
= {proof…}
329
if is_not_nan x then
330
round_f_not_nan (fmt x) m (if is_positive x then false else true) (esqrt (ext x))
331
{qed}

Increasing where it is not NaN

  Valid (47ms) (cvc5)
334
let ghost
sqrt_le
(m: mode) (x1 x2: t) : unit
335
requires { le_dz x1 x2 }
336
requires { is_not_nan (fp_sqrt m x1) /\ is_not_nan (fp_sqrt m x2) }
337
ensures { le_dz (fp_sqrt m x1) (fp_sqrt m x2) }
338
= {proof…}
339
le_not_nan x1 x2; sqrt_special m x1; sqrt_special m x2;
340
ext_sign x1; ext_sign x2; le_positive x1 x2;
341
esqrt_le (ext x1) (ext x2)
342
{qed}

The square root of a positive float is a positive float

  Valid (38ms) (colibri2)
345
let ghost
sqrt_positive
(m: mode) (x: t) : unit
346
requires { is_not_nan x /\ is_positive x }
347
ensures { is_not_nan (fp_sqrt m x) /\ is_positive (fp_sqrt m x) }
348
= {proof…}
349
let ghost fm = fmt x in
350
ext_sign x; sqrt_special m x;
351
esqrt_le (Fin 0.0) (ext x);
352
round_f_le fm m false false (Fin 0.0) (esqrt (ext x));
353
le_positive (round_f fm m false (Fin 0.0)) (fp_sqrt m x)
354
{qed}

The positive x whose square root is at least a are above pa * pa rounded down, for a positive pa below a

  Valid (1.1s) (cvc5)
358
let ghost
sqrt_lower
(m: mode) (pa a x: t) : unit
359
requires { fmt pa = fmt a /\ fmt x = fmt a }
360
requires { is_not_nan pa /\ is_positive pa /\ lt_dz pa a }
361
requires { is_not_nan x /\ is_positive x }
362
requires { le_dz a (fp_sqrt m x) }
363
ensures { lt_dz (fp_mul rtn pa pa) x }
364
= {proof…}
365
let ghost fm = fmt a in
366
ext_sign pa; ext_sign x;
367
mul_special rtn pa pa;
368
let ghost l = fp_mul rtn pa pa in
369
assert { l = round_f fm rtn false (emul (ext pa) (ext pa)) };
370
round_f_not_nan fm rtn false (emul (ext pa) (ext pa));
371
round_f_down fm false (emul (ext pa) (ext pa));
372
round_f_le fm rtn false false (Fin 0.0) (emul (ext pa) (ext pa));
373
le_positive (round_f fm rtn false (Fin 0.0)) l;
374
ext_sign l;
375
total l x;
376
if pure { le_dz x l } then begin
377
le_not_nan a (fp_sqrt m x);
378
sqrt_special m l;
379
sqrt_le m x l;
380
esqrt_le_sq (ext l) (ext pa);
381
round_f_exact m pa;
382
round_f_le fm m false false (esqrt (ext l)) (ext pa);
383
le_trans (fp_sqrt m x) (fp_sqrt m l) pa;
384
le_lt_trans (fp_sqrt m x) pa a;
385
lt_not_le (fp_sqrt m x) a;
386
absurd
387
end
388
{qed}

The positive x whose square root is at most b are below sb * sb rounded up, for a positive sb above b

  Valid (268ms) (colibri2 14) (cvc4 3) (cvc5 3) (split_vc) (depth 1)
392
let ghost
sqrt_upper
(m: mode) (sb b x: t) : unit
393
requires { fmt sb = fmt b /\ fmt x = fmt b }
394
requires { is_not_nan sb /\ is_positive sb /\ lt_dz b sb }
395
requires { is_not_nan x /\ is_positive x }
396
requires { le_dz (fp_sqrt m x) b }
397
ensures { lt_dz x (fp_mul rtp sb sb) }
398
= {proof…}
399
let ghost fm = fmt b in
400
ext_sign sb; ext_sign x;
401
mul_special rtp sb sb;
402
let ghost u = fp_mul rtp sb sb in
403
assert { u = round_f fm rtp false (emul (ext sb) (ext sb)) };
404
round_f_not_nan fm rtp false (emul (ext sb) (ext sb));
405
round_f_up fm false (emul (ext sb) (ext sb));
406
round_f_le fm rtp false false (Fin 0.0) (emul (ext sb) (ext sb));
407
le_positive (round_f fm rtp false (Fin 0.0)) u;
408
ext_sign u;
409
total x u;
410
if pure { le_dz u x } then begin
411
le_not_nan (fp_sqrt m x) b;
412
sqrt_special m u;
413
sqrt_le m u x;
414
esqrt_ge_sq (ext u) (ext sb);
415
round_f_exact m sb;
416
round_f_le fm m false false (ext sb) (esqrt (ext u));
417
le_trans sb (fp_sqrt m u) (fp_sqrt m x);
418
lt_le_trans b sb (fp_sqrt m x);
419
lt_not_le b (fp_sqrt m x);
420
absurd
421
end
422
{qed}

The product is commutative

  Valid (47ms) (cvc5)
425
let ghost
mul_comm
(m: mode) (x y: t) : unit
426
requires { fmt x = fmt y }
427
ensures { fp_mul m x y = fp_mul m y x }
428
= {proof…}
429
assert { mul_zneg x y = mul_zneg y x };
430
assert { emul (ext x) (ext y) = emul (ext y) (ext x) }
431
{qed}

The format of a product and of a quotient is the one of the first argument

  Valid (44ms) (cvc5)
435
let ghost
mul_div_fmt
(m: mode) (x y: t) : unit
436
ensures { fmt (fp_mul m x y) = fmt x /\ fmt (fp_div m x y) = fmt x }
437
= {proof…}
438
round_f_not_nan (fmt x) m (mul_zneg x y) (emul (ext x) (ext y));
439
round_f_not_nan (fmt x) m (mul_zneg x y) (ediv (ext x) (ext y))
440
{qed}

Conversion

  Valid (18ms) (colibri2)
444
let ghost
convert_not_nan
(fm: format) (m: mode) (x: t) : unit
445
requires { is_not_nan x }
446
ensures { is_not_nan (fp_convert fm m x) /\ fmt (fp_convert fm m x) = fm }
447
= {proof…}
448
round_f_not_nan fm m (if is_positive x then false else true) (ext x)
449
{qed}

Rounding to an integral float

  Valid (20ms) (colibri2)
453
let ghost
rti_not_nan
(m: mode) (x: t) : unit
454
requires { is_not_nan x }
455
ensures { is_not_nan (fp_rti m x) /\ fmt (fp_rti m x) = fmt x }
456
= {proof…}
457
round_f_not_nan (fmt x) m (if is_positive x then false else true)
458
(eround_int m (ext x))
459
{qed}

Increasing

  Valid (363ms) (cvc5)
462
let ghost
rti_le
(m: mode) (x1 x2: t) : unit
463
requires { le_dz x1 x2 }
464
ensures { le_dz (fp_rti m x1) (fp_rti m x2) }
465
= {proof…}
466
le_not_nan x1 x2; le_positive x1 x2;
467
assert { ele (eround_int m (ext x1)) (eround_int m (ext x2)) }
468
{qed}

Increasing

  Valid (58ms) (colibri2)
471
let ghost
convert_le
(fm: format) (m: mode) (x1 x2: t) : unit
472
requires { le_dz x1 x2 }
473
ensures { le_dz (fp_convert fm m x1) (fp_convert fm m x2) }
474
= {proof…}
475
le_not_nan x1 x2; le_positive x1 x2
476
{qed}

Backward addition

  Valid (44ms) (cvc4)
480
let ghost
add_comm
(m: mode) (x y: t) : unit
481
requires { fmt x = fmt y }
482
ensures { fp_add m x y = fp_add m y x }
483
= {proof…}
484
assert { opposite (ext x) (ext y) <-> opposite (ext y) (ext x) };
485
assert { add_zneg m x y = add_zneg m y x };
486
assert { eadd (ext x) (ext y) = eadd (ext y) (ext x) }
487
{qed}

Adding –inf (resp. +inf) gives –inf (resp. +inf), or NaN

  Valid (45ms) (cvc4)
490
let ghost
add_minus_infinity
(m: mode) (x y: t) : unit
491
requires { fmt x = fmt y /\ is_minus_infinity y /\ is_not_nan x /\ not is_plus_infinity x }
492
ensures { fp_add m x y = minus_infinity (fmt x) }
493
= {proof…}
494
assert { ext y = MInf };
495
assert { eadd (ext x) MInf = MInf };
496
add_special m x y
497
{qed}
498
Valid (266ms) (cvc4)
499
let ghost
add_plus_infinity
(m: mode) (x y: t) : unit
500
requires { fmt x = fmt y /\ is_plus_infinity y /\ is_not_nan x /\ not is_minus_infinity x }
501
ensures { fp_add m x y = plus_infinity (fmt x) }
502
= {proof…}
503
assert { ext y = PInf };
504
assert { eadd (ext x) PInf = PInf };
505
add_special m x y
506
{qed}

The x such that x + y is at least a for some y <= d, d finite, are above pa - d rounded down, where pa is below a and not –0

  Valid (246ms) (colibri2 15) (cvc4 2) (cvc5 2) (split_vc) (depth 1)
511
let ghost
add_lower
(m: mode) (pa a d x y: t) : unit
512
requires { fmt pa = fmt a /\ fmt d = fmt a /\ fmt x = fmt a /\ fmt y = fmt a }
513
requires { is_not_nan pa /\ lt_dz pa a /\ (is_zero pa -> is_positive pa) }
514
requires { is_not_nan d /\ not is_infinity d }
515
requires { le_dz y d /\ is_not_nan x }
516
requires { le_dz a (fp_add m x y) }
517
ensures { lt_dz (fp_add rtn pa (neg d)) x }
518
= {proof…}
519
let ghost fm = fmt a in
520
let ghost nd = neg d in
521
assert { is_not_nan nd /\ fmt nd = fm };
522
let ghost v = match ext d with Fin v -> v | _ -> absurd end in
523
assert { ext d = Fin v /\ ext nd = Fin (-. v) };
524
add_special rtn pa nd;
525
let ghost l = fp_add rtn pa nd in
526
assert { l = round_f fm rtn (add_zneg rtn pa nd) (eadd (ext pa) (Fin (-. v))) };
527
assert { ele (ext l) (eadd (ext pa) (Fin (-. v))) };
528
round_f_not_nan fm rtn (add_zneg rtn pa nd) (eadd (ext pa) (Fin (-. v)));
529
total l x;
530
if pure { le_dz x l } then begin
531
le_not_nan a (fp_add m x y);
532
add_special m l d;
533
add_box m x l y d;
534
eadd_sub_le (ext l) (ext pa) v;
535
let ghost zpa = if is_positive pa then false else true in
536
assert { round_f fm m zpa (ext pa) = pa };
537
round_f_le fm m (add_zneg m l d) zpa (eadd (ext l) (Fin v)) (ext pa);
538
assert { fp_add m l d = round_f fm m (add_zneg m l d) (eadd (ext l) (Fin v)) };
539
le_trans (fp_add m x y) (fp_add m l d) pa;
540
le_lt_trans (fp_add m x y) pa a;
541
lt_not_le (fp_add m x y) a;
542
absurd
543
end
544
{qed}
545
Valid (286ms) (colibri2 14) (cvc4) (cvc5 4) (split_vc) (depth 1)
546
let ghost
add_upper
(m: mode) (sb b c x y: t) : unit
547
requires { fmt sb = fmt b /\ fmt c = fmt b /\ fmt x = fmt b /\ fmt y = fmt b }
548
requires { is_not_nan sb /\ lt_dz b sb /\ (is_zero sb -> not is_positive sb) }
549
requires { is_not_nan c /\ not is_infinity c }
550
requires { le_dz c y /\ is_not_nan x }
551
requires { le_dz (fp_add m x y) b }
552
ensures { lt_dz x (fp_add rtp sb (neg c)) }
553
= {proof…}
554
let ghost fm = fmt b in
555
let ghost nc = neg c in
556
assert { is_not_nan nc /\ fmt nc = fm };
557
let ghost v = match ext c with Fin v -> v | _ -> absurd end in
558
assert { ext c = Fin v /\ ext nc = Fin (-. v) };
559
add_special rtp sb nc;
560
let ghost u = fp_add rtp sb nc in
561
assert { u = round_f fm rtp (add_zneg rtp sb nc) (eadd (ext sb) (Fin (-. v))) };
562
assert { ele (eadd (ext sb) (Fin (-. v))) (ext u) };
563
round_f_not_nan fm rtp (add_zneg rtp sb nc) (eadd (ext sb) (Fin (-. v)));
564
total x u;
565
if pure { le_dz u x } then begin
566
le_not_nan (fp_add m x y) b;
567
add_special m u c;
568
add_box m u x c y;
569
eadd_sub_ge (ext u) (ext sb) v;
570
let ghost zsb = if is_positive sb then false else true in
571
assert { round_f fm m zsb (ext sb) = sb };
572
round_f_le fm m zsb (add_zneg m u c) (ext sb) (eadd (ext u) (Fin v));
573
assert { fp_add m u c = round_f fm m (add_zneg m u c) (eadd (ext u) (Fin v)) };
574
le_trans sb (fp_add m u c) (fp_add m x y);
575
lt_le_trans b sb (fp_add m x y);
576
lt_not_le b (fp_add m x y);
577
absurd
578
end
579
{qed}

A float converted to its own format

  Valid (15ms) (colibri2)
582
let ghost
convert_exact
(m: mode) (x: t) : unit
583
requires { is_not_nan x }
584
ensures { fp_convert (fmt x) m x = x }
585
= ()

The conversion down to fm of a float p of another format is below p: converted back, it is below p

  Valid (41ms) (colibri2)
589
let ghost
convert_down_back
(fm: format) (m: mode) (p: t) : unit
590
requires { is_not_nan p }
591
ensures { le_dz (fp_convert (fmt p) m (fp_convert fm rtn p)) p }
592
= {proof…}
593
let ghost zp = if is_positive p then false else true in
594
let ghost l = fp_convert fm rtn p in
595
convert_not_nan fm rtn p;
596
assert { l = round_f fm rtn zp (ext p) };
597
assert { ele (ext l) (ext p) };
598
let ghost zl = if is_positive l then false else true in
599
let ghost cl = fp_convert (fmt p) m l in
600
assert { cl = round_f (fmt p) m zl (ext l) };
601
ext_sign p; ext_sign l;
602
if pure { zp /\ is_positive l } then begin
603
assert { ele (ext l) (Fin 0.0) };
604
assert { is_zero l };
605
absurd
606
end;
607
assert { round_f (fmt p) m zp (ext p) = p };
608
round_f_le (fmt p) m zl zp (ext l) (ext p)
609
{qed}
610
Valid (35ms) (colibri2)
611
let ghost
convert_up_back
(fm: format) (m: mode) (p: t) : unit
612
requires { is_not_nan p }
613
ensures { le_dz p (fp_convert (fmt p) m (fp_convert fm rtp p)) }
614
= {proof…}
615
let ghost zp = if is_positive p then false else true in
616
let ghost u = fp_convert fm rtp p in
617
convert_not_nan fm rtp p;
618
assert { u = round_f fm rtp zp (ext p) };
619
assert { ele (ext p) (ext u) };
620
let ghost zu = if is_positive u then false else true in
621
let ghost cu = fp_convert (fmt p) m u in
622
assert { cu = round_f (fmt p) m zu (ext u) };
623
ext_sign p; ext_sign u;
624
if pure { zu /\ is_positive p } then begin
625
assert { ele (Fin 0.0) (ext u) };
626
assert { is_zero u };
627
absurd
628
end;
629
assert { round_f (fmt p) m zp (ext p) = p };
630
round_f_le (fmt p) m zp zu (ext p) (ext u)
631
{qed}

The x of the format fm whose conversion to the format of a is at least a are above the conversion down of the predecessor of a

  Valid (281ms) (cvc5)
635
let ghost
convert_lower
(fm: format) (m: mode) (a x: t) : unit
636
requires { is_not_nan a /\ not is_minus_infinity a }
637
requires { fmt x = fm /\ is_not_nan x }
638
requires { le_dz a (fp_convert (fmt a) m x) }
639
ensures { lt_dz (fp_convert fm rtn (pred_dz a)) x }
640
= {proof…}
641
let ghost pa = pred_dz a in
642
pred_lt a;
643
let ghost l = fp_convert fm rtn pa in
644
convert_not_nan fm rtn pa;
645
total l x;
646
if pure { le_dz x l } then begin
647
convert_le (fmt a) m x l;
648
convert_down_back fm m pa;
649
le_trans (fp_convert (fmt a) m x) (fp_convert (fmt a) m l) pa;
650
le_lt_trans (fp_convert (fmt a) m x) pa a;
651
lt_not_le (fp_convert (fmt a) m x) a;
652
absurd
653
end
654
{qed}
655
Valid (37ms) (cvc5)
656
let ghost
convert_upper
(fm: format) (m: mode) (b x: t) : unit
657
requires { is_not_nan b /\ not is_plus_infinity b }
658
requires { fmt x = fm /\ is_not_nan x }
659
requires { le_dz (fp_convert (fmt b) m x) b }
660
ensures { lt_dz x (fp_convert fm rtp (succ_dz b)) }
661
= {proof…}
662
let ghost sb = succ_dz b in
663
succ_gt b;
664
let ghost u = fp_convert fm rtp sb in
665
convert_not_nan fm rtp sb;
666
total x u;
667
if pure { le_dz u x } then begin
668
convert_le (fmt b) m u x;
669
convert_up_back fm m sb;
670
le_trans sb (fp_convert (fmt b) m u) (fp_convert (fmt b) m x);
671
lt_le_trans b sb (fp_convert (fmt b) m x);
672
lt_not_le b (fp_convert (fmt b) m x);
673
absurd
674
end
675
{qed}

The format with one more bit

  Valid (149ms) (colibri2 2) (cvc5) (split_vc) (depth 1)
679
let ghost
widen_nb_sign
(fm fm': format) : unit
680
requires { widens fm fm' }
681
ensures { nb_sign fm' = 2 * nb_sign fm - 1 }
682
= {proof…}
683
assert { power 2 (sb fm' - 1) = 2 * power 2 (sb fm - 1)
684
by sb fm' - 1 = (sb fm - 1) + 1 /\ 0 <= sb fm - 1
685
so power 2 ((sb fm - 1) + 1) = power 2 (sb fm - 1) * power 2 1 };
686
let ghost q = power 2 (sb fm - 1) in
687
let ghost e = power 2 (eb fm) - 1 in
688
assert { nb_sign fm = e * q + 1 /\ nb_sign fm' = e * (2 * q) + 1 }
689
{qed}

The conversion to the format with one more bit is exact, at windex

  Valid (207ms) (colibri2)
693
let ghost
convert_widen
(fm': format) (m: mode) (x: t) : unit
694
requires { widens (fmt x) fm' /\ is_not_nan x }
695
ensures { - nb_sign fm' <= windex (index x) < nb_sign fm' }
696
ensures { fp_convert fm' m x = of_index fm' (windex (index x)) }
697
ensures { ext (fp_convert fm' m x) = ext x }
698
= {proof…}
699
let ghost fm = fmt x in
700
let ghost i = index x in
701
index_range x; widen_nb_sign fm fm';
702
of_index_range fm' (windex i);
703
let ghost y = of_index fm' (windex i) in
704
assert { ext y = ext x by ext y = ext (of_index fm i) /\ of_index fm i = x };
705
assert { is_positive y <-> is_positive x };
706
assert { round_f fm' m (if is_positive y then false else true) (ext y) = y }
707
{qed}

The value of the rounding does not depend on the sign of zero

  Valid (347ms) (cvc5)
710
let ghost
round_f_val
(fm: format) (m: mode) (z1 z2: bool) (e: ereal) : unit
711
ensures { ext (round_f fm m z1 e) = ext (round_f fm m z2 e) }
712
= {proof…}
713
let ghost r1 = round_f fm m z1 e in
714
let ghost r2 = round_f fm m z2 e in
715
if pure { is_zero r1 /\ is_zero r2 } then
716
assert { ext r1 = Fin 0.0 /\ ext r2 = Fin 0.0 }
717
else begin
718
assert { le_dz r1 r2 /\ le_dz r2 r1 };
719
assert { ele (ext r1) (ext r2) /\ ele (ext r2) (ext r1) }
720
end
721
{qed}

Increasing in value

  Valid (148ms) (cvc5)
724
let ghost
round_f_ele
(fm: format) (m: mode) (z1 z2: bool) (e1 e2: ereal) : unit
725
requires { ele e1 e2 }
726
ensures { ele (ext (round_f fm m z1 e1)) (ext (round_f fm m z2 e2)) }
727
= {proof…}
728
assert { le_dz (round_f fm m z1 e1) (round_f fm m z1 e2) };
729
round_f_val fm m z1 z2 e2
730
{qed}

The order of the values is the order of the floats, but –0 and +0

  Valid (166ms) (colibri2)
733
let ghost
ele_le
(x y: t) : unit
734
requires { fmt x = fmt y /\ is_not_nan x /\ is_not_nan y /\ ele (ext x) (ext y) }
735
requires { is_zero x /\ is_zero y -> is_positive x -> is_positive y }
736
ensures { le_dz x y }
737
= {proof…}
738
total x y;
739
if pure { lt_dz y x } then begin
740
if pure { is_zero x /\ is_zero y } then begin
741
index_range x; index_range y; absurd
742
end;
743
absurd
744
end
745
{qed}
746
end