Common — library colibrilib.fbin_ieee — module Equiv

The rounding of fbin.mlw is the rounding of Flocq

round_fin fm m z r (fbin.Float) is Flocq's round radix2 (FLT_exp (qmin fm) (sb fm)) in the mode m (colibrilib.flocq.Round, realized in Rocq from Flocq's definitions and lemmas) when the magnitude of that rounding is below 2^emax. Otherwise it is the overflow of IEEE 754 §7.4, as in Flocq's binary_overflow. The sign of a zero result is not Flocq's business: it is z.

The other operations of fbin.Impl are specified with round_f, which is round_fin on the finite reals.

13
module Equiv
14
use int.Int
15
use int.Power
16
use int.EuclideanDivision
17
use real.RealInfix
18
use real.FromInt
19
use real.Abs
20
use colibrilib.fp.Widen
21
use colibrilib.fbin.Pow2r
22
use colibrilib.fbin.Format
23
use colibrilib.fbin.Float
24
use colibrilib.flocq.Round as F

Flocq's rounding in the mode m, for the format fm

27
function
flocq
(fm: format) (m: mode) (r: real) : real =
28
match m with
29
| RTN -> F.rnd_dn (sb fm) (qmin fm) r
30
| RTP -> F.rnd_up (sb fm) (qmin fm) r
31
| RTZ -> F.rnd_zr (sb fm) (qmin fm) r
32
| RNE -> F.rnd_ne (sb fm) (qmin fm) r
33
| RNA -> F.rnd_na (sb fm) (qmin fm) r
34
end

The largest exponent: 2^emax is the least magnitude that overflows

38
function
emax
(fm: format) : int = power 2 (eb fm - 1)

Flocq's overflow_to_inf

41
predicate
overflow_to_inf
(m: mode) (neg: bool) =
42
match m with
43
| RNE | RNA -> true
44
| RTP -> not neg
45
| RTN -> neg
46
| RTZ -> false
47
end

Flocq's binary_overflow: the infinity, or the largest finite float

51
function
overflow
(fm: format) (m: mode) (neg: bool) : value =
52
if overflow_to_inf m neg then (if neg then MinusInf else PlusInf)
53
else Finite neg (nb_sign fm - 2)

The floats of Flocq are the values of the magnitudes

  Valid (19ms) (colibri2)
57
let ghost
pow2_pow2r
(e: int) : unit
58
ensures { F.pow2 e = pow2r e }
59
= ()
60
Valid (28ms) (colibri2)
61
let ghost
binade_2
(fm: format) : unit
62
ensures { power 2 (sb fm) = 2 * binade fm }
63
= {proof…} assert { power 2 (sb fm) = power 2 ((sb fm - 1) + 1) } {qed}
64
Valid (25ms) (colibri2)
65
let ghost
vom_mono
(fm: format) (k l: int) : unit
66
requires { 0 <= k <= l }
67
ensures { vom fm k <=. vom fm l }
68
= {proof…} if k < l then vom_lt fm k l {qed}
69
Valid (26ms) (colibri2)
70
let ghost
vom_generic
(fm: format) (k: int) : unit
71
requires { 0 <= k }
72
ensures { F.generic (sb fm) (qmin fm) (vom fm k) }
73
= {proof…}
74
vom_dec fm k; binade_2 fm; pow2_pow2r (uexp fm k);
75
assert { vom fm k = from_int (sig fm k) *. F.pow2 (uexp fm k) }
76
{qed}

The magnitude of m * 2^e

  Valid (43ms) (colibri2)
79
let rec ghost function
norm
(fm: format) (m e: int) : int
80
requires { qmin fm <= e /\ 0 <= m < 2 * binade fm }
81
ensures { 0 <= result /\ vom fm result = from_int m *. pow2r e }
82
variant { e - qmin fm }
83
= if pure { e = qmin fm \/ binade fm <= m } then begin
84
{proof…}
85
vom_s fm e m;
86
assert { 0 <= (e - qmin fm) * binade fm };
87
{qed}
88
pure { (e - qmin fm) * binade fm + m }
89
end else begin
90
{proof…} pow2r_succ (e - 1); {qed}
91
norm fm (2 * m) (e - 1)
92
end
93
Valid (45ms) (colibri2)
94
let ghost
generic_vom
(fm: format) (x: real) : int
95
requires { F.generic (sb fm) (qmin fm) x /\ 0.0 <=. x }
96
ensures { 0 <= result /\ vom fm result = x }
97
= let (m, e) = any (int, int) ensures { let (m, e) = result in
98
qmin fm <= e /\ - power 2 (sb fm) < m < power 2 (sb fm) /\
99
x = from_int m *. F.pow2 e } in
100
{proof…}
101
pow2_pow2r e; pow2r_pos e; binade_2 fm;
102
assert { 0 <= m by m < 0 -> from_int m *. pow2r e <. 0.0 };
103
{qed}
104
norm fm m e
105
Valid (31ms) (colibri2 2) (cvc5) (split_vc) (depth 1)
106
let ghost
generic_neg
(p q: int) (x: real) : unit
107
requires { F.generic p q x }
108
ensures { F.generic p q (-. x) }
109
= {proof…}
110
let (m, e) = any (int, int) ensures { let (m, e) = result in
111
q <= e /\ - power 2 p < m < power 2 p /\ x = from_int m *. F.pow2 e } in
112
assert { -. x = from_int (- m) *. F.pow2 e }
113
{qed}
114
Valid (21ms) (colibri2)
115
let lemma
generic_neg_l
(p q: int) (x: real)
116
requires { F.generic p q x }
117
ensures { F.generic p q (-. x) }
118
= generic_neg p q x
119
Valid (69ms) (colibri2 2) (cvc5) (split_vc) (depth 1)
120
let ghost
even_repr_neg
(p q: int) (x: real) : unit
121
requires { F.even_repr p q (-. x) }
122
ensures { F.even_repr p q x }
123
= {proof…}
124
let (m, e, h) = any (int, int, int) ensures { let (m, e, h) = result in
125
q <= e /\ - power 2 p < m < power 2 p /\ -. x = from_int m *. F.pow2 e /\
126
m = 2 * h } in
127
assert { x = from_int (- m) *. F.pow2 e /\ - m = 2 * (- h) }
128
{qed}

The floats are not strictly between the neighbours of a real

  Valid (100ms) (colibri2)
131
let ghost
neighbours
(fm: format) (k: int) (r g: real) : unit
132
requires { between fm k r /\ F.generic (sb fm) (qmin fm) g }
133
ensures { g <=. vom fm k \/ vom fm (k + 1) <=. g }
134
= {proof…}
135
vom_zero fm; vom_mono fm 0 k;
136
if pure { 0.0 <=. g } then begin
137
let j = generic_vom fm g in
138
if j <= k then vom_mono fm j k else vom_mono fm (k + 1) j
139
end
140
{qed}
141
Valid (17ms) (colibri2)
142
let lemma
neighbours_l
(fm: format) (k: int) (r g: real)
143
requires { between fm k r /\ F.generic (sb fm) (qmin fm) g }
144
ensures { g <=. vom fm k \/ vom fm (k + 1) <=. g }
145
= neighbours fm k r g

The parity of the magnitude is the parity of the significand

  Valid (24ms) (colibri2)
149
let ghost
scale_eq
(a b x y: int) : unit
150
requires { x <= y /\ from_int a *. pow2r x = from_int b *. pow2r y }
151
ensures { a = b * power 2 (y - x) }
152
= {proof…}
153
pow2r_add x (y - x); pow2r_int (y - x); pow2r_pos x;
154
assert { from_int a *. pow2r x = from_int (b * power 2 (y - x)) *. pow2r x };
155
scale_cmp a (b * power 2 (y - x)) (pow2r x)
156
{qed}
157
Valid (30ms) (colibri2)
158
let ghost
parity
(j t: int) : unit
159
ensures { j = 2 * t -> mod j 2 = 0 }
160
ensures { j = 2 * t + 1 -> mod j 2 = 1 }
161
= {proof…}
162
assert { mod (2 * t + 0) 2 = mod 0 2 };
163
assert { mod (2 * t + 1) 2 = mod 1 2 }
164
{qed}
165
Valid (391ms) (colibri2 15) (cvc4) (cvc5) (split_vc) (depth 1)
166
let ghost
even_vom
(fm: format) (j: int) : unit
167
requires { 0 <= j /\ F.even_repr (sb fm) (qmin fm) (vom fm j) }
168
ensures { mod j 2 = 0 }
169
= {proof…}
170
let (_m, e, q) = any (int, int, int) ensures { let (m, e, q) = result in
171
qmin fm <= e /\ - power 2 (sb fm) < m < power 2 (sb fm) /\
172
vom fm j = from_int m *. F.pow2 e /\ m = 2 * q } in
173
pow2_pow2r e; pow2r_succ e; pow2r_pos e; binade_2 fm; binade_ge_2 fm;
174
vom_dec fm j; vom_zero fm; vom_mono fm 0 j;
175
let u = pure { uexp fm j } in
176
let s = pure { sig fm j } in
177
assert { vom fm j = from_int q *. pow2r (e + 1) };
178
assert { 0 <= q by q < 0 -> from_int q *. pow2r (e + 1) <. 0.0 };
179
assert { q < binade fm };
180
assert { binade fm = 2 * power 2 (sb fm - 2)
181
by power 2 (sb fm - 1) = power 2 ((sb fm - 2) + 1) };
182
if u <= e then begin
183
scale_eq s q u (e + 1);
184
assert { power 2 (e + 1 - u) = 2 * power 2 (e - u) };
185
let t = pure { (u - qmin fm) * power 2 (sb fm - 2) + q * power 2 (e - u) } in
186
assert { s = 2 * (q * power 2 (e - u)) };
187
assert { (u - qmin fm) * binade fm = 2 * ((u - qmin fm) * power 2 (sb fm - 2)) };
188
assert { j = 2 * t };
189
parity j t
190
end else begin
191
scale_eq q s (e + 1) u;
192
assert { 1 <= power 2 (u - (e + 1)) };
193
assert { s <= s * power 2 (u - (e + 1)) };
194
absurd
195
end
196
{qed}

The rounding between two neighbours

  Valid (7.8s) (colibri2 15) (cvc5 2) (split_vc 3) (depth 2)
200
let ghost
between_round
(p q: int) (lo hi r: real) : unit
201
requires { 1 < p }
202
requires { F.generic p q lo /\ F.generic p q hi /\ lo <. r <. hi }
203
requires { forall g. F.generic p q g -> g <=. lo \/ hi <=. g }
204
ensures { F.rnd_dn p q r = lo /\ F.rnd_up p q r = hi }
205
ensures { r -. lo <. hi -. r -> F.rnd_ne p q r = lo /\ F.rnd_na p q r = lo }
206
ensures { hi -. r <. r -. lo -> F.rnd_ne p q r = hi /\ F.rnd_na p q r = hi }
207
ensures { r -. lo = hi -. r ->
208
(F.rnd_ne p q r = lo /\ F.even_repr p q lo) \/
209
(F.rnd_ne p q r = hi /\ F.even_repr p q hi) }
210
ensures { r -. lo = hi -. r ->
211
(F.rnd_na p q r = lo /\ abs hi <=. abs lo) \/
212
(F.rnd_na p q r = hi /\ abs lo <=. abs hi) }
213
= {proof…}
214
assert { F.rnd_dn p q r = lo };
215
assert { F.rnd_up p q r = hi };
216
assert { F.rnd_ne p q r = lo \/ F.rnd_ne p q r = hi
217
by abs (F.rnd_ne p q r -. r) <=. abs (lo -. r) /\
218
abs (F.rnd_ne p q r -. r) <=. abs (hi -. r) /\
219
(F.rnd_ne p q r <=. lo \/ hi <=. F.rnd_ne p q r) };
220
assert { F.rnd_na p q r = lo \/ F.rnd_na p q r = hi
221
by abs (F.rnd_na p q r -. r) <=. abs (lo -. r) /\
222
abs (F.rnd_na p q r -. r) <=. abs (hi -. r) /\
223
(F.rnd_na p q r <=. lo \/ hi <=. F.rnd_na p q r) };
224
if pure { r -. lo = hi -. r } then begin
225
assert { F.nearest p q r lo };
226
assert { F.nearest p q r hi }
227
end
228
{qed}
229
Valid (379ms) (colibri2 10) (split_vc) (depth 1)
230
let ghost
flocq_exact
(fm: format) (m: mode) (x: real) : unit
231
requires { F.generic (sb fm) (qmin fm) x }
232
ensures { flocq fm m x = x }
233
= {proof…}
234
let p = sb fm in
235
let q = qmin fm in
236
match m with
237
| RNE ->
238
assert { 1 < p };
239
assert { F.nearest p q x (F.rnd_ne p q x) };
240
assert { abs (F.rnd_ne p q x -. x) <=. abs (x -. x) }
241
| RNA ->
242
assert { 1 < p };
243
assert { F.nearest p q x (F.rnd_na p q x) };
244
assert { abs (F.rnd_na p q x -. x) <=. abs (x -. x) }
245
| RTN -> assert { F.rnd_dn p q x = x }
246
| RTP -> assert { F.rnd_up p q x = x }
247
| RTZ -> assert { F.rnd_dn p q x = x /\ F.rnd_up p q x = x }
248
end
249
{qed}

The rounding of a real r >= 0

  Valid (9.1s) (colibri2 18) (split_vc 5) (depth 4)
252
let ghost
flocq_pos
(fm: format) (m: mode) (r: real) : unit
253
requires { 0.0 <=. r }
254
ensures { flocq fm m r = vom fm (round_mag fm m r) }
255
= {proof…}
256
let k = kdn fm r in
257
vom_generic fm k;
258
if pure { vom fm k = r } then flocq_exact fm m r
259
else begin
260
vom_generic fm (k + 1);
261
vom_zero fm; vom_mono fm 0 k; vom_lt fm k (k + 1);
262
let lo = pure { vom fm k } in
263
let hi = pure { vom fm (k + 1) } in
264
assert { forall g. F.generic (sb fm) (qmin fm) g -> g <=. lo \/ hi <=. g };
265
between_round (sb fm) (qmin fm) lo hi r;
266
if pure { F.even_repr (sb fm) (qmin fm) lo } then even_vom fm k;
267
if pure { F.even_repr (sb fm) (qmin fm) hi } then even_vom fm (k + 1);
268
assert { mod (k + 1) 2 = 0 -> mod k 2 <> 0 }
269
end
270
{qed}

The rounding of a real r < 0

  Valid (697ms) (colibri2 36) (split_vc 7) (depth 4)
273
let ghost
flocq_neg
(fm: format) (m: mode) (r: real) : unit
274
requires { r <. 0.0 }
275
ensures { flocq fm m r = -. vom fm (round_mag fm (mirror m) (-. r)) }
276
= {proof…}
277
let k = kdn fm (-. r) in
278
vom_generic fm k;
279
generic_neg (sb fm) (qmin fm) (vom fm k);
280
if pure { vom fm k = -. r } then flocq_exact fm m r
281
else begin
282
vom_generic fm (k + 1);
283
generic_neg (sb fm) (qmin fm) (vom fm (k + 1));
284
vom_zero fm; vom_mono fm 0 k; vom_lt fm k (k + 1);
285
let lo = pure { -. vom fm (k + 1) } in
286
let hi = pure { -. vom fm k } in
287
assert { forall g. F.generic (sb fm) (qmin fm) g -> g <=. lo \/ hi <=. g
288
by F.generic (sb fm) (qmin fm) (-. g) };
289
between_round (sb fm) (qmin fm) lo hi r;
290
if pure { F.even_repr (sb fm) (qmin fm) hi } then begin
291
even_repr_neg (sb fm) (qmin fm) (vom fm k); even_vom fm k
292
end;
293
if pure { F.even_repr (sb fm) (qmin fm) lo } then begin
294
even_repr_neg (sb fm) (qmin fm) (vom fm (k + 1)); even_vom fm (k + 1)
295
end;
296
assert { mod (k + 1) 2 = 0 -> mod k 2 <> 0 };
297
let mid = pure { (vom fm k +. vom fm (k + 1)) /. 2.0 } in
298
assert { r -. lo <. hi -. r <-> mid <. -. r };
299
assert { hi -. r <. r -. lo <-> -. r <. mid };
300
assert { r -. lo = hi -. r <-> -. r = mid };
301
assert { abs hi <. abs lo };
302
match m with
303
| RNE -> assert { mirror m = RNE }
304
| RNA -> assert { mirror m = RNA }
305
| RTN -> assert { mirror m = RTP }
306
| RTP -> assert { mirror m = RTN }
307
| RTZ -> assert { mirror m = RTZ }
308
end
309
end
310
{qed}

The overflow

  Valid (48ms) (colibri2)
314
let ghost
vom_max
(fm: format) : unit
315
ensures { vom fm (nb_sign fm - 1) = pow2r (emax fm) }
316
ensures { 2 <= nb_sign fm - 1 }
317
= {proof…}
318
binade_ge_2 fm;
319
assert { power 2 (eb fm) = 2 * power 2 (eb fm - 1)
320
by power 2 (eb fm) = power 2 ((eb fm - 1) + 1) };
321
assert { 2 <= power 2 (eb fm - 1)
322
by power 2 (eb fm - 1) = 2 * power 2 (eb fm - 2)
323
by power 2 (eb fm - 1) = power 2 ((eb fm - 2) + 1) };
324
let u = pure { qmin fm + power 2 (eb fm) - 2 } in
325
vom_s fm u (binade fm);
326
assert { nb_sign fm - 1 = (u - qmin fm) * binade fm + binade fm };
327
pow2r_int (sb fm - 1); pow2r_add (sb fm - 1) u;
328
assert { sb fm - 1 + u = emax fm }
329
{qed}

The theorem

  Valid (2.7s) (colibri2 17) (cvc4 5) (cvc5 10) (split_vc 9) (depth 5)
333
let ghost
round_fin_flocq
(fm: format) (m: mode) (z: bool) (r: real) : unit
334
ensures { let x = round_fin fm m z r in
335
let f = flocq fm m r in
336
if abs f <. pow2r (emax fm) then
337
(exists ng k. x.value = Finite ng k) /\ to_real x = f
338
else x.value = overflow fm m (r <. 0.0) }
339
= {proof…}
340
vom_max fm; vom_zero fm;
341
let n = pure { nb_sign fm - 1 } in
342
let x = pure { round_fin fm m z r } in
343
if pure { 0.0 <=. r } then begin
344
flocq_pos fm m r;
345
let k = pure { round_mag fm m r } in
346
assert { 0 <= k };
347
if k = 0 then assert { x.value = Finite z 0 }
348
else if k < n then begin
349
vom_lt fm k n; vom_mono fm 0 k;
350
assert { abs (flocq fm m r) <. pow2r (emax fm) };
351
assert { x.value = Finite false k }
352
end else begin
353
vom_mono fm n k;
354
match m with
355
| RTN | RTZ -> assert { x.value = Finite false (nb_sign fm - 2) }
356
| _ -> assert { x.value = PlusInf }
357
end
358
end
359
end else begin
360
flocq_neg fm m r;
361
let k = pure { round_mag fm (mirror m) (-. r) } in
362
assert { 0 <= k };
363
if k = 0 then assert { x.value = Finite z 0 }
364
else if k < n then begin
365
vom_lt fm k n; vom_mono fm 0 k;
366
assert { abs (flocq fm m r) <. pow2r (emax fm) };
367
assert { x.value = Finite true k }
368
end else begin
369
vom_mono fm n k;
370
match m with
371
| RTP | RTZ -> assert { x.value = Finite true (nb_sign fm - 2) }
372
| _ -> assert { x.value = MinusInf }
373
end
374
end
375
end
376
{qed}
377
end