Common — library colibrilib.fp_conv — module Linearize

The linearization of the roundings to nearest

The 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).

6052
module Linearize
6053
use list.List
6054
use list.Mem as LM
6055
use option.Option
6056
use int.Int
6057
use mach.int.Int63
6058
use real.RealInfix
6059
use real.FromInt
6060
use colibrilib.ring.Atom
6061
use colibrilib.fbin.Fp
6062
use colibrilib.fp.Ereal
6063
use colibrilib.stda.StdA as A
6064
use colibrilib.pow2r.Pow2r
6065
use colibrilib.fp_interval.Intervals
6066
use colibrilib.fp_interval.FpInterval
6067
use colibrilib.fp_interval.Export as IE
6068
use colibrilib.polynome.Lin as Lin
6069
use colibrilib.polynome.Export as P
6070
use colibrilib.spec.Eval
6071
use colibrilib.env.Linear as EL
6072
use Env
6073
use Rules
6074
use GTerm
6075
use Dolmen as D
6076
use Conv
6077
6078
predicate
finite
(x: t) = is_not_nan x /\ not (is_inf x)

The operation on the reals of a rounded operation

6081
function
lop
(o: bop) (x y: real) : real =
6082
match o with OAdd -> x +. y | OMul -> x *. y | ODiv -> x /. y end

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

6086
predicate
rounds
(md: model) (fm: format) (f m a b x tf: Atom.t) =
6087
let r = float_value md f in
6088
fmt r = fm /\
6089
(finite (float_value md a) -> finite (float_value md b) -> finite r ->
6090
real_value md tf = to_real r /\
6091
exists z. r = round_f fm (mode_value md m) z (Fin (real_value md x)))

A rounding, registered in an environment of the model gm, live when gl

  Valid (48ms) (colibri2)
6095
type
rounding
= {
6096
rf
: Atom.t;
rmode
: Atom.t;
ra
: Atom.t;
rb
: Atom.t;
6097
rx
: Atom.t;
rtf
: Atom.t;
rfm
: format;
6098
ghost
gm
: model; ghost
gl
: bool }
6099
invariant { gl -> rounds gm rfm rf rmode ra rb rx rtf }
6100
by { rf = any Atom.t; rmode = any Atom.t; ra = any Atom.t; rb = any Atom.t;
6101
rx = any Atom.t; rtf = any Atom.t; rfm = any format;
6102
gm = any model; gl = false }

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)
6106
let ghost
fop_round
(o: bop) (md: mode) (x y: t) : unit
6107
ensures { fmt y = fmt x -> finite x -> finite y -> finite (fop o md x y) ->
6108
exists z. fop o md x y =
6109
round_f (fmt x) md z (Fin (lop o (to_real x) (to_real y))) }
6110
= {proof…}
6111
if pure { fmt y = fmt x /\ finite x /\ finite y /\ finite (fop o md x y) } then begin
6112
assert { ext x = Fin (to_real x) /\ ext y = Fin (to_real y) };
6113
match o with
6114
| OAdd -> assert { fp_add md x y = round_f (fmt x) md (add_zneg md x y) (Fin (to_real x +. to_real y)) }
6115
| OMul -> assert { fp_mul md x y = round_f (fmt x) md (mul_zneg x y) (Fin (to_real x *. to_real y)) }
6116
| ODiv ->
6117
assert { not is_zero y };
6118
assert { to_real y <> 0.0 };
6119
assert { to_real x *. (1.0 /. to_real y) = to_real x /. to_real y };
6120
assert { fp_div md x y = round_f (fmt x) md (mul_zneg x y) (Fin (to_real x /. to_real y)) }
6121
end end {qed}

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)
6126
let
mk
(d: env) (e p: int63) (o: bop) (c: D.cst) (f m a b: Atom.t) : option rounding
6127
requires { o = OAdd /\ c.D.builtin = D.Add D.AReal \/
6128
o = OMul /\ c.D.builtin = D.Mul D.AReal \/
6129
o = ODiv /\ c.D.builtin = D.Div D.DReal }
6130
requires { forall fm. D.isfmt fm e p -> D.sp d (Bin o fm f m a b) }
6131
writes { d.state }
6132
ensures { match result with
6133
| Some g -> g.gm = d.model /\ g.gl = live d
6134
| None -> true end }
6135
= try
6136
let fm = fmt_ep e p in
6137
let ta = D.apply d (D.cst_to_real e p) (Cons a Nil) in
6138
let tb = D.apply d (D.cst_to_real e p) (Cons b Nil) in
6139
let tf = D.apply d (D.cst_to_real e p) (Cons f Nil) in
6140
let x = D.apply d c (Cons ta (Cons tb Nil)) in
6141
{proof…}
6142
D.means_at d (D.To_real e p) ta (Cons a Nil);
6143
D.means_at d (D.To_real e p) tb (Cons b Nil);
6144
D.means_at d (D.To_real e p) tf (Cons f Nil);
6145
D.means_at d c.D.builtin x (Cons ta (Cons tb Nil));
6146
assert { live d -> holds d (Bin o fm f m a b) };
6147
assert { live d -> finite (d.mf a) -> finite (d.mf b) -> finite (d.mf f) ->
6148
d.mr x = lop o (to_real (d.mf a)) (to_real (d.mf b))
6149
by d.mr ta = to_real (d.mf a) /\ d.mr tb = to_real (d.mf b) /\
6150
(o = ODiv -> to_real (d.mf b) <> 0.0 ->
6151
d.mr x = d.mr ta /. d.mr tb) /\
6152
(o = ODiv -> to_real (d.mf b) <> 0.0
6153
by not is_zero (fop o (d.mm m) (d.mf a) (d.mf b)) \/ true) };
6154
fop_round o (pure { d.mm m }) (pure { d.mf a }) (pure { d.mf b });
6155
assert { live d -> finite (d.mf a) -> finite (d.mf b) -> finite (d.mf f) ->
6156
exists z. d.mf f = round_f fm (d.mm m) z (Fin (d.mr x)) };
6157
{qed}
6158
register d x;
6159
Some { rf = f; rmode = m; ra = a; rb = b; rx = x; rtf = tf; rfm = fm;
6160
gm = pure { d.model }; gl = pure { live d } }
6161
with NoFormat -> None
6162
end

The rounding of the ground term g, when it is fp.add, fp.mul or fp.div

  Valid (334ms) (colibri2)
6166
let
rounding_of
(d: env) (g: ground) : option rounding
6167
writes { d.state }
6168
ensures { match result with
6169
| Some r -> r.gm = d.model /\ r.gl = live d
6170
| None -> true end }
6171
= let f = node g in
6172
match D.sem g with
6173
| None -> None
6174
| Some (bi, l) ->
6175
{proof…} D.means_at d bi f l; {qed}
6176
match bi, l with
6177
| D.Fp_add e p, Cons m (Cons a (Cons b Nil)) -> mk d e p OAdd (D.cst_radd ()) f m a b
6178
| D.Fp_mul e p, Cons m (Cons a (Cons b Nil)) -> mk d e p OMul (D.cst_rmul ()) f m a b
6179
| D.Fp_div e p, Cons m (Cons a (Cons b Nil)) -> mk d e p ODiv (D.cst_rdiv ()) f m a b
6180
| _ -> None
6181
end
6182
end

p >= 0 (true) or p <= 0 (false) in the model env

6185
predicate
bound_holds
(env: Atom.t -> real) (pk: (Lin.t, bool)) =
6186
let (p, k) = pk in if k then 0.0 <=. Lin.eval env p else Lin.eval env p <=. 0.0

The values of n in the domain of d are finite

  Valid (57ms) (colibri2)
6189
let
finite_dom
(d: env) (n: Atom.t) : bool
6190
ensures { result -> live d -> finite (d.mf n) }
6191
= match get d n with
6192
| None -> false
6193
| Some v -> IE.is_finite v
6194
end

m 2^e

  Valid (48ms) (colibri2)
6197
let
dy
(m e: int) : A.t
6198
ensures { A.real result = from_int m *. pow2r e }
6199
= A.mul (A.of_bigint m) (a_pow2 e)

to_real f - c x - k

  Valid (949ms) (colibri2 7) (cvc5) (split_vc 3) (depth 2)
6202
let
lin
(g: rounding) (c k: A.t) : Lin.t
6203
ensures { forall env. Lin.eval env result = env g.rtf -. A.real c *. env g.rx -. A.real k }
6204
= let one = A.of_int 1 in
6205
let mf = P.monome one g.rtf in
6206
let mx = P.monome one g.rx in
6207
let nc = A.neg c in
6208
let s = P.cx_p_cy one mf nc mx in
6209
let r = P.sub_cst s k in
6210
{proof…}
6211
assert { forall env. Lin.eval env mf = env g.rtf
6212
by Lin.value mf env = A.real one *. env g.rtf };
6213
assert { forall env. Lin.eval env mx = env g.rx
6214
by Lin.value mx env = A.real one *. env g.rx };
6215
assert { forall env. Lin.eval env s = A.real one *. Lin.eval env mf +. A.real nc *. Lin.eval env mx
6216
by Lin.value s env = A.real one *. Lin.value mf env +. A.real nc *. Lin.value mx env };
6217
assert { forall env. Lin.eval env s = env g.rtf -. A.real c *. env g.rx
6218
by Lin.eval env s = 1.0 *. env g.rtf +. (-. A.real c) *. env g.rx };
6219
assert { forall env. Lin.eval env r = Lin.eval env s -. A.real k
6220
by Lin.value r env = Lin.value s env -. A.real k };
6221
{qed}
6222
r

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)
6226
let
equations
(d: env) (g: rounding) : list (Lin.t, bool)
6227
requires { d.model = g.gm /\ (live d -> g.gl) }
6228
writes { d.state }
6229
ensures { live d -> forall pk. LM.mem pk result -> bound_holds d.mr pk }
6230
= match mode d g.rmode with
6231
| Some RNE | Some RNA ->
6232
if finite_dom d g.ra && finite_dom d g.rb then
6233
match get d g.rf with
6234
| None -> Nil
6235
| Some v ->
6236
if not (IE.is_finite v) then Nil else
6237
try
6238
let lo = IE.min_f v in
6239
let hi = IE.max_f v in
6240
match nearest_bounds lo hi with
6241
| None -> Nil
6242
| Some ((am, ae), ad, (bm, be), (cm, ce), cd, (dm, de)) ->
6243
let lc = A.div (dy am ae) (A.of_bigint ad) in
6244
let lk = dy bm be in
6245
let hc = A.div (dy cm ce) (A.of_bigint cd) in
6246
let hk = dy dm de in
6247
{proof…}
6248
assert { live d -> exists z.
6249
d.mf g.rf = round_f g.rfm (d.mm g.rmode) z (Fin (d.mr g.rx)) /\
6250
d.mr g.rtf = to_real (d.mf g.rf) /\
6251
le_dz lo (d.mf g.rf) /\ le_dz (d.mf g.rf) hi /\ fmt lo = g.rfm };
6252
assert { A.real lc *. from_int ad = from_int am *. pow2r ae };
6253
assert { A.real hc *. from_int cd = from_int cm *. pow2r ce };
6254
let ghost r = pure { d.mr g.rx } in
6255
let ghost t = pure { d.mr g.rtf } in
6256
assert { live d ->
6257
from_int am *. pow2r ae *. r +. from_int ad *. A.real lk
6258
<=. from_int ad *. t /\
6259
from_int cd *. t
6260
<=. from_int cm *. pow2r ce *. r +. from_int cd *. A.real hk };
6261
assert { from_int am *. pow2r ae *. r = from_int ad *. (A.real lc *. r)
6262
by from_int am *. pow2r ae *. r = (A.real lc *. from_int ad) *. r };
6263
assert { from_int cm *. pow2r ce *. r = from_int cd *. (A.real hc *. r)
6264
by from_int cm *. pow2r ce *. r = (A.real hc *. from_int cd) *. r };
6265
assert { live d ->
6266
from_int ad *. (A.real lc *. r +. A.real lk) <=. from_int ad *. t /\
6267
from_int cd *. t <=. from_int cd *. (A.real hc *. r +. A.real hk) };
6268
assert { 0.0 <. from_int ad /\ 0.0 <. from_int cd };
6269
assert { live d ->
6270
A.real lc *. r +. A.real lk <=. t /\
6271
t <=. A.real hc *. r +. A.real hk };
6272
{qed}
6273
register d g.rx;
6274
register d g.rtf;
6275
let pmin = EL.normalize d (lin g lc lk) in
6276
let pmax = EL.normalize d (lin g hc hk) in
6277
match P.is_cst pmin, P.is_cst pmax with
6278
| None, None -> Cons (pmin, true) (Cons (pmax, false) Nil)
6279
| _ -> Nil
6280
end
6281
end
6282
with Empty -> Nil
6283
end
6284
end
6285
else Nil
6286
| _ -> Nil
6287
end
6288
end