Common — library colibrilib.fp — module Ereal

The extended reals

The reals with +inf and –inf, for the values of the floats that are not NaN (as in BTRW15 §IV). The sum of +inf and –inf is not used.

16
module Ereal
17
use real.RealInfix
18
use real.Square as S
19
20
type
ereal
=
Fin
real |
PInf
|
MInf
21
22
predicate
ele
(a b: ereal) =
23
match a, b with
24
| MInf, _ | _, PInf -> true
25
| Fin x, Fin y -> x <=. y
26
| _ -> false
27
end
28
29
predicate
opposite
(a b: ereal) =
30
(a = PInf /\ b = MInf) \/ (a = MInf /\ b = PInf)
31
32
function
eadd
(a b: ereal) : ereal =
33
match a, b with
34
| Fin x, Fin y -> Fin (x +. y)
35
| PInf, MInf | MInf, PInf -> Fin 0.0
36
| PInf, _ | _, PInf -> PInf
37
| MInf, _ | _, MInf -> MInf
38
end

The product; 0 times an infinity is not used

41
function
emul
(a b: ereal) : ereal =
42
match a, b with
43
| Fin x, Fin y -> Fin (x *. y)
44
| Fin x, PInf | PInf, Fin x ->
45
if x >. 0.0 then PInf else if x <. 0.0 then MInf else Fin 0.0
46
| Fin x, MInf | MInf, Fin x ->
47
if x >. 0.0 then MInf else if x <. 0.0 then PInf else Fin 0.0
48
| PInf, PInf | MInf, MInf -> PInf
49
| PInf, MInf | MInf, PInf -> MInf
50
end
51
52
predicate
undef_mul
(a b: ereal) =
53
(a = Fin 0.0 /\ (b = PInf \/ b = MInf)) \/ (b = Fin 0.0 /\ (a = PInf \/ a = MInf))

|a1| <= |a2|, both of the sign p (true: not negative)

56
predicate
emag_le
(p: bool) (a1 a2: ereal) =
57
if p then ele (Fin 0.0) a1 /\ ele a1 a2 else ele a2 a1 /\ ele a1 (Fin 0.0)

The product is increasing in the magnitudes

  Valid (74ms) (colibri2 22) (cvc5) (split_vc) (depth 1)
60
let ghost
emul_mag
(p q: bool) (a1 a2 b1 b2: ereal) : unit
61
requires { emag_le p a1 a2 /\ emag_le q b1 b2 }
62
requires { not undef_mul a1 b1 /\ not undef_mul a2 b2 }
63
ensures { if p = q then ele (emul a1 b1) (emul a2 b2)
64
else ele (emul a2 b2) (emul a1 b1) }
65
= {proof…}
66
match a1, a2, b1, b2 with
67
| Fin x1, Fin x2, Fin y1, Fin y2 ->
68
if p then begin
69
assert { x1 *. y1 -. x2 *. y1 = (x1 -. x2) *. y1 };
70
assert { x2 *. y1 -. x2 *. y2 = x2 *. (y1 -. y2) };
71
assert { x1 *. y2 -. x2 *. y2 = (x1 -. x2) *. y2 };
72
assert { x1 *. y1 -. x1 *. y2 = x1 *. (y1 -. y2) };
73
assert { 0.0 <=. x1 <=. x2 };
74
if q then begin
75
assert { 0.0 <=. y1 <=. y2 };
76
assert { (x1 -. x2) *. y1 <=. 0.0 };
77
assert { x2 *. (y1 -. y2) <=. 0.0 }
78
end else begin
79
assert { y2 <=. y1 <=. 0.0 };
80
assert { (x1 -. x2) *. y2 >=. 0.0 };
81
assert { x1 *. (y1 -. y2) >=. 0.0 }
82
end
83
end else begin
84
assert { x1 *. y1 -. x1 *. y2 = x1 *. (y1 -. y2) };
85
assert { x1 *. y2 -. x2 *. y2 = (x1 -. x2) *. y2 };
86
assert { x1 *. y1 -. x2 *. y1 = (x1 -. x2) *. y1 };
87
assert { x2 *. y1 -. x2 *. y2 = x2 *. (y1 -. y2) };
88
assert { x2 <=. x1 <=. 0.0 };
89
if q then begin
90
assert { 0.0 <=. y1 <=. y2 };
91
assert { x1 *. (y1 -. y2) >=. 0.0 };
92
assert { (x1 -. x2) *. y2 >=. 0.0 }
93
end else begin
94
assert { y2 <=. y1 <=. 0.0 };
95
assert { (x1 -. x2) *. y1 <=. 0.0 };
96
assert { x2 *. (y1 -. y2) <=. 0.0 }
97
end
98
end
99
| _ -> ()
100
end
101
{qed}

The inverse; the inverse of 0 is not used

104
function
einv
(b: ereal) : ereal =
105
match b with Fin y -> Fin (1.0 /. y) | _ -> Fin 0.0 end

The quotient; 0/0 and inf/inf are not used

108
function
ediv
(a b: ereal) : ereal = emul a (einv b)

The inverse is decreasing in the magnitude

  Valid (145ms) (colibri2)
111
let ghost
einv_mag
(q: bool) (b1 b2: ereal) : unit
112
requires { emag_le q b1 b2 /\ b1 <> Fin 0.0 }
113
ensures { emag_le q (einv b2) (einv b1) }
114
= {proof…}
115
match b1, b2 with
116
| Fin y1, Fin y2 ->
117
assert { y1 <> 0.0 /\ y2 <> 0.0 };
118
assert { 1.0 /. y1 -. 1.0 /. y2 = (y2 -. y1) /. (y1 *. y2) };
119
assert { y1 *. y2 >. 0.0 };
120
if q then begin
121
assert { 1.0 /. y2 >. 0.0 };
122
assert { (y2 -. y1) /. (y1 *. y2) >=. 0.0 }
123
end else begin
124
assert { 1.0 /. y2 <. 0.0 };
125
assert { (y2 -. y1) /. (y1 *. y2) <=. 0.0 }
126
end
127
| Fin y1, _ ->
128
if q then assert { 1.0 /. y1 >. 0.0 } else assert { 1.0 /. y1 <. 0.0 }
129
| _ -> ()
130
end
131
{qed}

The square root; of the reals that are not negative

134
function
esqrt
(a: ereal) : ereal =
135
match a with Fin x -> Fin (S.sqrt x) | _ -> a end
136
Valid (49ms) (colibri2)
137
let ghost
esqrt_le
(a1 a2: ereal) : unit
138
requires { ele (Fin 0.0) a1 /\ ele a1 a2 }
139
ensures { ele (esqrt a1) (esqrt a2) }
140
ensures { a1 = Fin 0.0 -> esqrt a1 = Fin 0.0 }
141
= {proof…}
142
assert { S.sqrt (0.0 *. 0.0) = 0.0 }
143
{qed}

The square root below (above) p when the square of p is above (below)

  Valid (20ms) (colibri2)
147
let ghost
esqrt_le_sq
(e p: ereal) : unit
148
requires { ele (Fin 0.0) e /\ ele (Fin 0.0) p /\ ele e (emul p p) }
149
ensures { ele (esqrt e) p }
150
= {proof…}
151
match e, p with
152
| Fin x, Fin y -> assert { S.sqrt x <=. S.sqrt (y *. y) = y }
153
| _ -> ()
154
end
155
{qed}
156
Valid (24ms) (colibri2)
157
let ghost
esqrt_ge_sq
(e p: ereal) : unit
158
requires { ele (Fin 0.0) p /\ ele (emul p p) e }
159
ensures { ele p (esqrt e) }
160
= {proof…}
161
match e, p with
162
| Fin x, Fin y -> assert { y = S.sqrt (y *. y) <=. S.sqrt x }
163
| _ -> ()
164
end
165
{qed}

Increasing in both arguments, where defined

  Valid (34ms) (colibri2)
168
let ghost
eadd_le2
(a1 a2 b1 b2: ereal) : unit
169
requires { ele a1 a2 /\ ele b1 b2 }
170
requires { not opposite a1 b1 /\ not opposite a2 b2 }
171
ensures { ele (eadd a1 b1) (eadd a2 b2) }
172
= {proof…} () {qed}
173
174
function
eneg
(a: ereal) : ereal =
175
match a with Fin x -> Fin (-. x) | PInf -> MInf | MInf -> PInf end

Moving a finite term across the order

  Valid (15ms) (colibri2)
178
let ghost
eadd_sub_le
(u p: ereal) (v: real) : unit
179
requires { ele u (eadd p (Fin (-. v))) }
180
ensures { ele (eadd u (Fin v)) p }
181
= {proof…} () {qed}
182
Valid (17ms) (colibri2)
183
let ghost
eadd_sub_ge
(u p: ereal) (v: real) : unit
184
requires { ele (eadd p (Fin (-. v))) u }
185
ensures { ele p (eadd u (Fin v)) }
186
= {proof…} () {qed}
187
Valid (72ms) (colibri2)
188
let ghost
eadd_move_ge
(t u: ereal) (v: real) : unit
189
requires { ele t (eadd u (Fin v)) }
190
ensures { ele (eadd t (Fin (-. v))) u }
191
= {proof…} () {qed}
192
Valid (98ms) (colibri2)
193
let ghost
eadd_move_gt
(t u: ereal) (v: real) : unit
194
requires { ele t (eadd u (Fin v)) /\ t <> eadd u (Fin v) }
195
ensures { ele (eadd t (Fin (-. v))) u /\ eadd t (Fin (-. v)) <> u }
196
= {proof…} () {qed}
197
Valid (83ms) (colibri2)
198
let ghost
eadd_move_le
(t u: ereal) (v: real) : unit
199
requires { ele (eadd u (Fin v)) t }
200
ensures { ele u (eadd t (Fin (-. v))) }
201
= {proof…} () {qed}
202
Valid (115ms) (colibri2)
203
let ghost
eadd_move_lt
(t u: ereal) (v: real) : unit
204
requires { ele (eadd u (Fin v)) t /\ t <> eadd u (Fin v) }
205
ensures { ele u (eadd t (Fin (-. v))) /\ eadd t (Fin (-. v)) <> u }
206
= {proof…} () {qed}
207
end