library colibrilib.fp — module ErealThe 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.
module Ereal16use real.RealInfix17use real.Square as S1819type ereal = Fin real | PInf | MInf2021predicate ele (a b: ereal) =22match a, b with23| MInf, _ | _, PInf -> true24| Fin x, Fin y -> x <=. y25| _ -> false26end2728predicate opposite (a b: ereal) =29(a = PInf /\ b = MInf) \/ (a = MInf /\ b = PInf)3031function eadd (a b: ereal) : ereal =32match a, b with33| Fin x, Fin y -> Fin (x +. y)34| PInf, MInf | MInf, PInf -> Fin 0.035| PInf, _ | _, PInf -> PInf36| MInf, _ | _, MInf -> MInf37end38
The product; 0 times an infinity is not used
function emul (a b: ereal) : ereal =41match a, b with42| Fin x, Fin y -> Fin (x *. y)43| Fin x, PInf | PInf, Fin x ->44if x >. 0.0 then PInf else if x <. 0.0 then MInf else Fin 0.045| Fin x, MInf | MInf, Fin x ->46if x >. 0.0 then MInf else if x <. 0.0 then PInf else Fin 0.047| PInf, PInf | MInf, MInf -> PInf48| PInf, MInf | MInf, PInf -> MInf49end5051predicate undef_mul (a b: ereal) =52(a = Fin 0.0 /\ (b = PInf \/ b = MInf)) \/ (b = Fin 0.0 /\ (a = PInf \/ a = MInf))53
|a1| <= |a2|, both of the sign p (true: not negative)
predicate emag_le (p: bool) (a1 a2: ereal) =56if p then ele (Fin 0.0) a1 /\ ele a1 a2 else ele a2 a1 /\ ele a1 (Fin 0.0)57
The product is increasing in the magnitudes
Valid (74ms) (colibri2 22) (cvc5) (split_vc) (depth 1)let ghost emul_mag (p q: bool) (a1 a2 b1 b2: ereal) : unit60requires { emag_le p a1 a2 /\ emag_le q b1 b2 }61requires { not undef_mul a1 b1 /\ not undef_mul a2 b2 }62ensures { if p = q then ele (emul a1 b1) (emul a2 b2)63else ele (emul a2 b2) (emul a1 b1) }64= {proof…}65match a1, a2, b1, b2 with66| Fin x1, Fin x2, Fin y1, Fin y2 ->67if p then begin68assert { x1 *. y1 -. x2 *. y1 = (x1 -. x2) *. y1 };69assert { x2 *. y1 -. x2 *. y2 = x2 *. (y1 -. y2) };70assert { x1 *. y2 -. x2 *. y2 = (x1 -. x2) *. y2 };71assert { x1 *. y1 -. x1 *. y2 = x1 *. (y1 -. y2) };72assert { 0.0 <=. x1 <=. x2 };73if q then begin74assert { 0.0 <=. y1 <=. y2 };75assert { (x1 -. x2) *. y1 <=. 0.0 };76assert { x2 *. (y1 -. y2) <=. 0.0 }77end else begin78assert { y2 <=. y1 <=. 0.0 };79assert { (x1 -. x2) *. y2 >=. 0.0 };80assert { x1 *. (y1 -. y2) >=. 0.0 }81end82end else begin83assert { x1 *. y1 -. x1 *. y2 = x1 *. (y1 -. y2) };84assert { x1 *. y2 -. x2 *. y2 = (x1 -. x2) *. y2 };85assert { x1 *. y1 -. x2 *. y1 = (x1 -. x2) *. y1 };86assert { x2 *. y1 -. x2 *. y2 = x2 *. (y1 -. y2) };87assert { x2 <=. x1 <=. 0.0 };88if q then begin89assert { 0.0 <=. y1 <=. y2 };90assert { x1 *. (y1 -. y2) >=. 0.0 };91assert { (x1 -. x2) *. y2 >=. 0.0 }92end else begin93assert { y2 <=. y1 <=. 0.0 };94assert { (x1 -. x2) *. y1 <=. 0.0 };95assert { x2 *. (y1 -. y2) <=. 0.0 }96end97end98| _ -> ()99end100{qed}101
The inverse; the inverse of 0 is not used
function einv (b: ereal) : ereal =104match b with Fin y -> Fin (1.0 /. y) | _ -> Fin 0.0 end105
The quotient; 0/0 and inf/inf are not used
function ediv (a b: ereal) : ereal = emul a (einv b)108
The inverse is decreasing in the magnitude
Valid (145ms) (colibri2)let ghost einv_mag (q: bool) (b1 b2: ereal) : unit111requires { emag_le q b1 b2 /\ b1 <> Fin 0.0 }112ensures { emag_le q (einv b2) (einv b1) }113= {proof…}114match b1, b2 with115| Fin y1, Fin y2 ->116assert { y1 <> 0.0 /\ y2 <> 0.0 };117assert { 1.0 /. y1 -. 1.0 /. y2 = (y2 -. y1) /. (y1 *. y2) };118assert { y1 *. y2 >. 0.0 };119if q then begin120assert { 1.0 /. y2 >. 0.0 };121assert { (y2 -. y1) /. (y1 *. y2) >=. 0.0 }122end else begin123assert { 1.0 /. y2 <. 0.0 };124assert { (y2 -. y1) /. (y1 *. y2) <=. 0.0 }125end126| Fin y1, _ ->127if q then assert { 1.0 /. y1 >. 0.0 } else assert { 1.0 /. y1 <. 0.0 }128| _ -> ()129end130{qed}131
The square root; of the reals that are not negative
function esqrt (a: ereal) : ereal =134match a with Fin x -> Fin (S.sqrt x) | _ -> a end135Valid (49ms) (colibri2)136let ghost esqrt_le (a1 a2: ereal) : unit137requires { ele (Fin 0.0) a1 /\ ele a1 a2 }138ensures { ele (esqrt a1) (esqrt a2) }139ensures { a1 = Fin 0.0 -> esqrt a1 = Fin 0.0 }140= {proof…}141assert { S.sqrt (0.0 *. 0.0) = 0.0 }142{qed}143
The square root below (above) p when the square of p is above (below)
Valid (20ms) (colibri2)let ghost esqrt_le_sq (e p: ereal) : unit147requires { ele (Fin 0.0) e /\ ele (Fin 0.0) p /\ ele e (emul p p) }148ensures { ele (esqrt e) p }149= {proof…}150match e, p with151| Fin x, Fin y -> assert { S.sqrt x <=. S.sqrt (y *. y) = y }152| _ -> ()153end154{qed}155Valid (24ms) (colibri2)156let ghost esqrt_ge_sq (e p: ereal) : unit157requires { ele (Fin 0.0) p /\ ele (emul p p) e }158ensures { ele p (esqrt e) }159= {proof…}160match e, p with161| Fin x, Fin y -> assert { y = S.sqrt (y *. y) <=. S.sqrt x }162| _ -> ()163end164{qed}165
Increasing in both arguments, where defined
Valid (34ms) (colibri2)let ghost eadd_le2 (a1 a2 b1 b2: ereal) : unit168requires { ele a1 a2 /\ ele b1 b2 }169requires { not opposite a1 b1 /\ not opposite a2 b2 }170ensures { ele (eadd a1 b1) (eadd a2 b2) }171= {proof…} () {qed}172173function eneg (a: ereal) : ereal =174match a with Fin x -> Fin (-. x) | PInf -> MInf | MInf -> PInf end175
Moving a finite term across the order
Valid (15ms) (colibri2)let ghost eadd_sub_le (u p: ereal) (v: real) : unit178requires { ele u (eadd p (Fin (-. v))) }179ensures { ele (eadd u (Fin v)) p }180= {proof…} () {qed}181Valid (17ms) (colibri2)182let ghost eadd_sub_ge (u p: ereal) (v: real) : unit183requires { ele (eadd p (Fin (-. v))) u }184ensures { ele p (eadd u (Fin v)) }185= {proof…} () {qed}186Valid (72ms) (colibri2)187let ghost eadd_move_ge (t u: ereal) (v: real) : unit188requires { ele t (eadd u (Fin v)) }189ensures { ele (eadd t (Fin (-. v))) u }190= {proof…} () {qed}191Valid (98ms) (colibri2)192let ghost eadd_move_gt (t u: ereal) (v: real) : unit193requires { ele t (eadd u (Fin v)) /\ t <> eadd u (Fin v) }194ensures { ele (eadd t (Fin (-. v))) u /\ eadd t (Fin (-. v)) <> u }195= {proof…} () {qed}196Valid (83ms) (colibri2)197let ghost eadd_move_le (t u: ereal) (v: real) : unit198requires { ele (eadd u (Fin v)) t }199ensures { ele u (eadd t (Fin (-. v))) }200= {proof…} () {qed}201Valid (115ms) (colibri2)202let ghost eadd_move_lt (t u: ereal) (v: real) : unit203requires { ele (eadd u (Fin v)) t /\ t <> eadd u (Fin v) }204ensures { ele u (eadd t (Fin (-. v))) /\ eadd t (Fin (-. v)) <> u }205= {proof…} () {qed}206end207