library colibrilib.fp_conv — module LinearizeThe rounding f = fp.add m a b (resp. fp.mul, fp.div) of the real x = to_real a + to_real b (resp. *, /) gives to the simplex of LRA the bounds c x + k <= to_real f <= c' x + k' of Intf.nearest_bounds, from the domain of f, when the mode is to nearest and a, b and f are finite (the hook of colibri2/theories/FP/fp_to_real.ml). A rounding is registered with the model and the liveness of its registration, as the propagators (Rules.reg).
module Linearize6052use list.List6053use list.Mem as LM6054use option.Option6055use int.Int6056use mach.int.Int636057use real.RealInfix6058use real.FromInt6059use colibrilib.ring.Atom6060use colibrilib.fbin.Fp6061use colibrilib.fp.Ereal6062use colibrilib.stda.StdA as A6063use colibrilib.pow2r.Pow2r6064use colibrilib.fp_interval.Intervals6065use colibrilib.fp_interval.FpInterval6066use colibrilib.fp_interval.Export as IE6067use colibrilib.polynome.Lin as Lin6068use colibrilib.polynome.Export as P6069use colibrilib.spec.Eval6070use colibrilib.env.Linear as EL6071use Env6072use Rules6073use GTerm6074use Dolmen as D6075use Conv60766077predicate finite (x: t) = is_not_nan x /\ not (is_inf x)6078
The operation on the reals of a rounded operation
function lop (o: bop) (x y: real) : real =6081match o with OAdd -> x +. y | OMul -> x *. y | ODiv -> x /. y end6082
The meaning of the rounding f of the real node x in the model md, tf being fp.to_real f: when a, b and f are finite
predicate rounds (md: model) (fm: format) (f m a b x tf: Atom.t) =6086let r = float_value md f in6087fmt r = fm /\6088(finite (float_value md a) -> finite (float_value md b) -> finite r ->6089real_value md tf = to_real r /\6090exists z. r = round_f fm (mode_value md m) z (Fin (real_value md x)))6091
A rounding, registered in an environment of the model gm, live when gl
Valid (48ms) (colibri2)type rounding = {6095rf: Atom.t; rmode: Atom.t; ra: Atom.t; rb: Atom.t;6096rx: Atom.t; rtf: Atom.t; rfm: format;6097ghost gm: model; ghost gl: bool }6098invariant { gl -> rounds gm rfm rf rmode ra rb rx rtf }6099by { rf = any Atom.t; rmode = any Atom.t; ra = any Atom.t; rb = any Atom.t;6100rx = any Atom.t; rtf = any Atom.t; rfm = any format;6101gm = any model; gl = false }6102
An operation on finite floats with a finite result is the rounding of the operation on their reals
Valid (1.2s) (colibri2 8) (cvc5 3) (split_vc 3) (depth 3)let ghost fop_round (o: bop) (md: mode) (x y: t) : unit6106ensures { fmt y = fmt x -> finite x -> finite y -> finite (fop o md x y) ->6107exists z. fop o md x y =6108round_f (fmt x) md z (Fin (lop o (to_real x) (to_real y))) }6109= {proof…}6110if pure { fmt y = fmt x /\ finite x /\ finite y /\ finite (fop o md x y) } then begin6111assert { ext x = Fin (to_real x) /\ ext y = Fin (to_real y) };6112match o with6113| OAdd -> assert { fp_add md x y = round_f (fmt x) md (add_zneg md x y) (Fin (to_real x +. to_real y)) }6114| OMul -> assert { fp_mul md x y = round_f (fmt x) md (mul_zneg x y) (Fin (to_real x *. to_real y)) }6115| ODiv ->6116assert { not is_zero y };6117assert { to_real y <> 0.0 };6118assert { to_real x *. (1.0 /. to_real y) = to_real x /. to_real y };6119assert { fp_div md x y = round_f (fmt x) md (mul_zneg x y) (Fin (to_real x /. to_real y)) }6120end end {qed}6121
The rounding of the term f of operation o of m, a, b, the real operation being c: the nodes of fp.to_real of a, b, f and of the real x = to_real a o to_real b
Valid (4.5s) (colibri2 17) (cvc5 2) (split_vc 2) (depth 2)let mk (d: env) (e p: int63) (o: bop) (c: D.cst) (f m a b: Atom.t) : option rounding6126requires { o = OAdd /\ c.D.builtin = D.Add D.AReal \/6127o = OMul /\ c.D.builtin = D.Mul D.AReal \/6128o = ODiv /\ c.D.builtin = D.Div D.DReal }6129requires { forall fm. D.isfmt fm e p -> D.sp d (Bin o fm f m a b) }6130writes { d.state }6131ensures { match result with6132| Some g -> g.gm = d.model /\ g.gl = live d6133| None -> true end }6134= try6135let fm = fmt_ep e p in6136let ta = D.apply d (D.cst_to_real e p) (Cons a Nil) in6137let tb = D.apply d (D.cst_to_real e p) (Cons b Nil) in6138let tf = D.apply d (D.cst_to_real e p) (Cons f Nil) in6139let x = D.apply d c (Cons ta (Cons tb Nil)) in6140{proof…}6141D.means_at d (D.To_real e p) ta (Cons a Nil);6142D.means_at d (D.To_real e p) tb (Cons b Nil);6143D.means_at d (D.To_real e p) tf (Cons f Nil);6144D.means_at d c.D.builtin x (Cons ta (Cons tb Nil));6145assert { live d -> holds d (Bin o fm f m a b) };6146assert { live d -> finite (d.mf a) -> finite (d.mf b) -> finite (d.mf f) ->6147d.mr x = lop o (to_real (d.mf a)) (to_real (d.mf b))6148by d.mr ta = to_real (d.mf a) /\ d.mr tb = to_real (d.mf b) /\6149(o = ODiv -> to_real (d.mf b) <> 0.0 ->6150d.mr x = d.mr ta /. d.mr tb) /\6151(o = ODiv -> to_real (d.mf b) <> 0.06152by not is_zero (fop o (d.mm m) (d.mf a) (d.mf b)) \/ true) };6153fop_round o (pure { d.mm m }) (pure { d.mf a }) (pure { d.mf b });6154assert { live d -> finite (d.mf a) -> finite (d.mf b) -> finite (d.mf f) ->6155exists z. d.mf f = round_f fm (d.mm m) z (Fin (d.mr x)) };6156{qed}6157register d x;6158Some { rf = f; rmode = m; ra = a; rb = b; rx = x; rtf = tf; rfm = fm;6159gm = pure { d.model }; gl = pure { live d } }6160with NoFormat -> None6161end6162
The rounding of the ground term g, when it is fp.add, fp.mul or fp.div
Valid (334ms) (colibri2)let rounding_of (d: env) (g: ground) : option rounding6166writes { d.state }6167ensures { match result with6168| Some r -> r.gm = d.model /\ r.gl = live d6169| None -> true end }6170= let f = node g in6171match D.sem g with6172| None -> None6173| Some (bi, l) ->6174{proof…} D.means_at d bi f l; {qed}6175match bi, l with6176| D.Fp_add e p, Cons m (Cons a (Cons b Nil)) -> mk d e p OAdd (D.cst_radd ()) f m a b6177| D.Fp_mul e p, Cons m (Cons a (Cons b Nil)) -> mk d e p OMul (D.cst_rmul ()) f m a b6178| D.Fp_div e p, Cons m (Cons a (Cons b Nil)) -> mk d e p ODiv (D.cst_rdiv ()) f m a b6179| _ -> None6180end6181end6182
p >= 0 (true) or p <= 0 (false) in the model env
predicate bound_holds (env: Atom.t -> real) (pk: (Lin.t, bool)) =6185let (p, k) = pk in if k then 0.0 <=. Lin.eval env p else Lin.eval env p <=. 0.06186
The values of n in the domain of d are finite
Valid (57ms) (colibri2)let finite_dom (d: env) (n: Atom.t) : bool6189ensures { result -> live d -> finite (d.mf n) }6190= match get d n with6191| None -> false6192| Some v -> IE.is_finite v6193end6194
m 2^e
Valid (48ms) (colibri2)let dy (m e: int) : A.t6197ensures { A.real result = from_int m *. pow2r e }6198= A.mul (A.of_bigint m) (a_pow2 e)6199
to_real f - c x - k
Valid (949ms) (colibri2 7) (cvc5) (split_vc 3) (depth 2)let lin (g: rounding) (c k: A.t) : Lin.t6202ensures { forall env. Lin.eval env result = env g.rtf -. A.real c *. env g.rx -. A.real k }6203= let one = A.of_int 1 in6204let mf = P.monome one g.rtf in6205let mx = P.monome one g.rx in6206let nc = A.neg c in6207let s = P.cx_p_cy one mf nc mx in6208let r = P.sub_cst s k in6209{proof…}6210assert { forall env. Lin.eval env mf = env g.rtf6211by Lin.value mf env = A.real one *. env g.rtf };6212assert { forall env. Lin.eval env mx = env g.rx6213by Lin.value mx env = A.real one *. env g.rx };6214assert { forall env. Lin.eval env s = A.real one *. Lin.eval env mf +. A.real nc *. Lin.eval env mx6215by Lin.value s env = A.real one *. Lin.value mf env +. A.real nc *. Lin.value mx env };6216assert { forall env. Lin.eval env s = env g.rtf -. A.real c *. env g.rx6217by Lin.eval env s = 1.0 *. env g.rtf +. (-. A.real c) *. env g.rx };6218assert { forall env. Lin.eval env r = Lin.eval env s -. A.real k6219by Lin.value r env = Lin.value s env -. A.real k };6220{qed}6221r6222
The bounds of a registered rounding, true in the model of d; the nodes x and fp.to_real f are registered
Valid (1.2s) (colibri2 38) (cvc5 4) (split_vc 5) (depth 3)let equations (d: env) (g: rounding) : list (Lin.t, bool)6226requires { d.model = g.gm /\ (live d -> g.gl) }6227writes { d.state }6228ensures { live d -> forall pk. LM.mem pk result -> bound_holds d.mr pk }6229= match mode d g.rmode with6230| Some RNE | Some RNA ->6231if finite_dom d g.ra && finite_dom d g.rb then6232match get d g.rf with6233| None -> Nil6234| Some v ->6235if not (IE.is_finite v) then Nil else6236try6237let lo = IE.min_f v in6238let hi = IE.max_f v in6239match nearest_bounds lo hi with6240| None -> Nil6241| Some ((am, ae), ad, (bm, be), (cm, ce), cd, (dm, de)) ->6242let lc = A.div (dy am ae) (A.of_bigint ad) in6243let lk = dy bm be in6244let hc = A.div (dy cm ce) (A.of_bigint cd) in6245let hk = dy dm de in6246{proof…}6247assert { live d -> exists z.6248d.mf g.rf = round_f g.rfm (d.mm g.rmode) z (Fin (d.mr g.rx)) /\6249d.mr g.rtf = to_real (d.mf g.rf) /\6250le_dz lo (d.mf g.rf) /\ le_dz (d.mf g.rf) hi /\ fmt lo = g.rfm };6251assert { A.real lc *. from_int ad = from_int am *. pow2r ae };6252assert { A.real hc *. from_int cd = from_int cm *. pow2r ce };6253let ghost r = pure { d.mr g.rx } in6254let ghost t = pure { d.mr g.rtf } in6255assert { live d ->6256from_int am *. pow2r ae *. r +. from_int ad *. A.real lk6257<=. from_int ad *. t /\6258from_int cd *. t6259<=. from_int cm *. pow2r ce *. r +. from_int cd *. A.real hk };6260assert { from_int am *. pow2r ae *. r = from_int ad *. (A.real lc *. r)6261by from_int am *. pow2r ae *. r = (A.real lc *. from_int ad) *. r };6262assert { from_int cm *. pow2r ce *. r = from_int cd *. (A.real hc *. r)6263by from_int cm *. pow2r ce *. r = (A.real hc *. from_int cd) *. r };6264assert { live d ->6265from_int ad *. (A.real lc *. r +. A.real lk) <=. from_int ad *. t /\6266from_int cd *. t <=. from_int cd *. (A.real hc *. r +. A.real hk) };6267assert { 0.0 <. from_int ad /\ 0.0 <. from_int cd };6268assert { live d ->6269A.real lc *. r +. A.real lk <=. t /\6270t <=. A.real hc *. r +. A.real hk };6271{qed}6272register d g.rx;6273register d g.rtf;6274let pmin = EL.normalize d (lin g lc lk) in6275let pmax = EL.normalize d (lin g hc hk) in6276match P.is_cst pmin, P.is_cst pmax with6277| None, None -> Cons (pmin, true) (Cons (pmax, false) Nil)6278| _ -> Nil6279end6280end6281with Empty -> Nil6282end6283end6284else Nil6285| _ -> Nil6286end6287end6288