Common — library colibrilib.fp_dyadic — module Rules
10
module Rules
11
use int.Int
12
use int.Power
13
use option.Option
14
use real.RealInfix
15
use colibrilib.pow2r.Pow2r
16
use colibrilib.fp.Ereal
17
use colibrilib.fbin.Fp
18
use colibrilib.fp_facts.Facts
19
use colibrilib.dyadic.Dyadic as D
20
21
predicate
finite
(x: t) =
22
is_not_nan x /\ not is_plus_infinity x /\ not is_minus_infinity x

The dyadic domain of a float node: the real of the float, when it is finite

26
predicate
fmem
(x: t) (d: D.t) = finite x -> D.mem (to_real x) d

The floats of a format: multiples of 2^umin with psb bits

29
let function
float_dom
(umin psb: int) : D.t = D.mk (Some umin) None (Some psb)
30
Valid (49ms) (colibri2)
31
let ghost
float_mem
(x: t) : unit
32
ensures { fmem x (float_dom (ulp_min (fmt x)) (sb (fmt x))) }
33
= {proof…} if pure { finite x } then float_dyadic x {qed}

The rounding forward

lo (rnd r) >= max (umin, min (lo r, umax)) (the rounding keeps the multiples of 2^e, e <= umax), prec (rnd r) <= sb.

  Valid (402ms) (colibri2)
39
let
round_fwd0
(ghost fm: format) (umin umax psb: int) (d: D.t) : D.t
40
requires { umin = ulp_min fm /\ umax = ulp_max fm /\ psb = sb fm }
41
ensures { forall m z r. D.mem r d -> finite (round_f fm m z (Fin r)) ->
42
D.mem (to_real (round_f fm m z (Fin r))) result }
43
= let l = match d.D.lo with
44
| None -> umin
45
| Some k ->
46
let k = if k <= umax then k else umax in
47
if k <= umin then umin else k
48
end in
49
{proof…}
50
let lemma fwd (m: mode) (z: bool) (r: real)
51
requires { D.mem r d /\ finite (round_f fm m z (Fin r)) }
52
ensures { D.mem (to_real (round_f fm m z (Fin r))) (D.mk (Some l) None (Some psb)) }
53
= let x = round_f fm m z (Fin r) in
54
float_dyadic x;
55
match d.D.lo with
56
| None -> ()
57
| Some k ->
58
let k' = if k <= umax then k else umax in
59
D.fix_mono r k' k;
60
round_fix fm m z r k'
61
end in
62
{qed}
63
D.mk (Some l) None (Some psb)

The rounding backward

A nonzero r that rounds to zero is below 2^umin, so not a multiple of 2^umin; one that rounds to a nonzero float keeps the multiples of 2^e, e <= umax: hi r <= max (hi (rnd r), umin - 1) when this bound plus one is at most umax.

  Valid (221ms) (colibri2)
71
let
round_back
(ghost fm: format) (umin umax: int) (dr: D.t) : D.t
72
requires { umin = ulp_min fm /\ umax = ulp_max fm }
73
ensures { forall m z r. finite (round_f fm m z (Fin r)) ->
74
D.mem (to_real (round_f fm m z (Fin r))) dr -> D.mem r result }
75
= match dr.D.hi with
76
| None -> D.top
77
| Some h ->
78
let k = if h <= umin - 1 then umin - 1 else h in
79
if k + 1 <= umax then begin
80
{proof…}
81
let lemma back (m: mode) (z: bool) (r: real)
82
requires { finite (round_f fm m z (Fin r)) }
83
requires { D.mem (to_real (round_f fm m z (Fin r))) dr }
84
ensures { D.mem_hi r (Some k) }
85
= let x = round_f fm m z (Fin r) in
86
if pure { r <> 0.0 /\ D.fix r (k + 1) } then begin
87
if is_zero x then begin
88
round_zero_small fm m z r;
89
D.fix_mono r umin (k + 1);
90
D.fix_nz_ge r umin;
91
absurd
92
end else begin
93
assert { ext x = Fin (to_real x) };
94
assert { to_real x <> 0.0 };
95
round_fix fm m z r (k + 1);
96
D.fix_mono (to_real x) (h + 1) (k + 1);
97
absurd
98
end
99
end in
100
{qed}
101
D.mk None (Some k) None
102
end else D.top
103
end

The exact roundings

The values of d are multiples of 2^umin with psb bits

  Valid (127ms) (colibri2)
108
let
is_exact
(umin psb: int) (d: D.t) : bool
109
ensures { result -> forall r. D.mem r d -> D.fix r umin /\ D.flt r psb }
110
= match d.D.lo, d.D.prec with
111
| Some l, Some p ->
112
if umin <= l && 0 <= p && p <= psb then begin
113
{proof…} D.fix_mono_all umin l; D.flt_mono_all p psb; {qed}
114
true
115
end else false
116
| _ -> false
117
end

Such a real, at most the largest finite float, rounds to itself (Flocq's round_generic, src/Core/Generic_fmt.v)

  Valid (745ms) (colibri2)
121
let ghost
round_exact
(fm: format) (m: mode) (z: bool) (r: real) : unit
122
requires { D.fix r (ulp_min fm) /\ D.flt r (sb fm) }
123
requires { -. to_real (of_index fm (nb_sign fm - 2)) <=. r <=.
124
to_real (of_index fm (nb_sign fm - 2)) }
125
ensures { finite (round_f fm m z (Fin r)) }
126
ensures { to_real (round_f fm m z (Fin r)) = r }
127
= {proof…}
128
let y = dyadic_exact fm r in
129
let zy = if is_positive y then false else true in
130
assert { round_f fm m zy (ext y) = y };
131
round_f_val fm m z zy (Fin r);
132
assert { ext (round_f fm m z (Fin r)) = Fin r }
133
{qed}

The values of d are floats of the format below 2^(umax+sb-1): the rounding is exact (Gappa's EQL(rnd(a), a)), the result keeps the domain of d

  Valid (83ms) (cvc5)
138
let
round_fwd
(ghost fm: format) (umin umax psb: int) (d: D.t) : D.t
139
requires { umin = ulp_min fm /\ umax = ulp_max fm /\ psb = sb fm }
140
ensures { forall m z r. D.mem r d -> finite (round_f fm m z (Fin r)) ->
141
D.mem (to_real (round_f fm m z (Fin r))) result }
142
= let b = round_fwd0 fm umin umax psb d in
143
let small = match d.D.hi, d.D.prec with
144
| Some h, Some p -> 0 <= p && h + p <= umax + psb - 1
145
| _ -> false end in
146
if small && is_exact umin psb d then begin
147
{proof…}
148
let lemma ex (m: mode) (z: bool) (r: real)
149
requires { D.mem r d /\ finite (round_f fm m z (Fin r)) }
150
ensures { to_real (round_f fm m z (Fin r)) = r }
151
= max_float_ge fm;
152
if pure { r <> 0.0 } then begin
153
D.mag r d;
154
match d.D.hi, d.D.prec with
155
| Some h, Some p -> pow2r_le (h + p) (umax + psb - 1)
156
| _ -> absurd
157
end
158
end;
159
round_exact fm m z r in
160
{qed}
161
D.inter b d
162
end else b
163
end