library colibrilib.fp_interval — module ExportThe functions that fp_interval.ml calls, total: the domains carry their format only as ghost, so the format of a domain is read on its floats (dom_format), and a domain without float (NaN or empty) takes the format of the other argument, or of the format given. The constants of a format (the infinities, the zeros, the bounds of the classes, –1 and 1) are computed here from the format.
module Export7216use int.Int7217use int.Power7218use list.List7219use option.Option7220use real.RealInfix7221use real.FromInt7222use colibrilib.pow2r.Pow2r7223use colibrilib.fp.Widen7224use colibrilib.fp.Ereal7225use colibrilib.fbin.Fp7226use colibrilib.fp_facts.Facts7227use Intervals7228use FpInterval7229use Rules7230
Two domains with floats of two formats, or a domain with floats of another format than the one given
exception FormatMismatch7234
The floats of format fm in d, read in the format fm
predicate mem_at (fm: format) (v: t) (d: dom) =7237fmt v = fm /\ if is_nan v then d.nan else mem_u v d.u7238
d has no float of another format than fm
predicate fits (fm: format) (d: dom) = d.u <> Nil -> d.fm = fm7241
The format of two domains: the one of their floats
function pfm (d1 d2: dom) : format = if d1.u <> Nil then d1.fm else d2.fm72447245predicate mismatch (d1 d2: dom) = d1.u <> Nil /\ d2.u <> Nil /\ d1.fm <> d2.fm7246
The format of the floats of d
Valid (27ms) (colibri2)let dom_format (d: dom) : option format7249ensures { match result with7250| None -> d.u = Nil7251| Some f -> d.u <> Nil /\ f = d.fm end }7252= match d.u with Nil -> None | Cons (a, _) _ -> Some (format_of a) end7253
d in the format fm
Valid (34ms) (colibri2)let in_fmt (ghost fm: format) (d: dom) : dom7256ensures { result.u = d.u /\ result.nan = d.nan }7257ensures { fits fm d -> result.fm = fm }7258ensures { fits fm d -> forall v. mem v result <-> mem_at fm v d }7259= match d.u with7260| Nil -> { u = Nil; nan = d.nan; fm = fm }7261| Cons _ _ -> d7262end7263
d1 and d2 in their common format
Valid (76ms) (cvc5)let common (d1 d2: dom) : (dom, dom)7266raises { FormatMismatch -> mismatch d1 d2 }7267ensures { let (e1, e2) = result in7268e1.fm = pfm d1 d2 /\ e2.fm = pfm d1 d2 /\7269(forall v. mem v e1 <-> mem_at (pfm d1 d2) v d1) /\7270(forall v. mem v e2 <-> mem_at (pfm d1 d2) v d2) /\7271e1.u = d1.u /\ e2.u = d2.u /\ e1.nan = d1.nan /\ e2.nan = d2.nan }7272= match dom_format d1, dom_format d2 with7273| Some f1, Some f2 ->7274if eq_format f1 f2 then (in_fmt d1.fm d1, in_fmt d1.fm d2) else raise FormatMismatch7275| Some _, None -> (in_fmt d1.fm d1, in_fmt d1.fm d2)7276| None, _ -> (in_fmt d2.fm d1, in_fmt d2.fm d2)7277end7278
d in the format fm, or FormatMismatch
Valid (31ms) (colibri2)let check_fmt (fm: format) (d: dom) : dom7281raises { FormatMismatch -> not fits fm d }7282ensures { result.fm = fm /\ result.u = d.u /\ result.nan = d.nan }7283ensures { forall v. mem v result <-> mem_at fm v d }7284= match dom_format d with7285| Some f -> if eq_format f fm then in_fmt fm d else raise FormatMismatch7286| None -> in_fmt fm d7287end7288
Valid (38ms) (colibri2)let minf (fm: format) : t7292ensures { result = minus_infinity fm }7293= {proof…}7294let ghost x = minus_infinity fm in7295assert { is_not_nan x /\ index x = - nb_sign fm };7296assert { of_index fm (- nb_sign fm) = x by of_index (fmt x) (index x) = x };7297{qed}7298of_index_v fm (- nb_sign_v fm)7299Valid (51ms) (colibri2)7300let pinf (fm: format) : t7301ensures { result = plus_infinity fm }7302= {proof…}7303let ghost x = plus_infinity fm in7304assert { is_not_nan x /\ index x = nb_sign fm - 1 };7305assert { of_index fm (nb_sign fm - 1) = x by of_index (fmt x) (index x) = x };7306{qed}7307of_index_v fm (nb_sign_v fm - 1)7308
The float of index i
Valid (20ms) (colibri2)let at_i (fm: format) (i: int) : t7311ensures { - nb_sign fm <= i < nb_sign fm -> at_index fm result i }7312= {proof…} if pure { - nb_sign fm <= i < nb_sign fm } then of_index_range fm i; {qed}7313of_index_v fm i7314
The float 1
Valid (50ms) (colibri2 13) (split_vc) (depth 1)let one_f (fm: format) : t7317ensures { fmt result = fm /\ is_not_nan result /\ ext result = Fin 1.0 }7318= {proof…}7319max_float_ge fm;7320assert { power 2 (eb fm) = 2 * emax fm };7321assert { ulp_max fm + sb fm - 1 = emax fm - 1 };7322assert { 1 <= emax fm by power 2 (eb fm - 1) >= 1 };7323pow2r_le 0 (ulp_max fm + sb fm - 1);7324assert { pow2r 0 = 1.0 };7325assert { 2 <= power 2 (sb fm) };7326let ghost x = int_exact fm 1 in7327ext_sign x;7328assert { is_positive x };7329assert { round_f (fmt x) RNE (if is_positive x then false else true) (ext x) = x };7330assert { round_f fm RNE false (ext x) = x };7331{qed}7332of_int fm RNE false 17333Valid (412ms) (colibri2)7334let consts_of (fm: format) : (t, t, t, t, t, t)7335ensures { let (minf, pinf, nz, pz, m1, p1) = result in7336consts fm minf pinf nz pz m1 p1 }7337= {proof…} format_facts fm (); {qed}7338let p1 = one_f fm in7339(minf fm, pinf fm, at_i fm (-1), at_i fm 0, neg p1, p1)7340Valid (61ms) (cvc5)7341let specials_of (fm: format) : specials7342ensures { ok_specials fm result }7343= {proof…} format_facts fm (); {qed}7344let nb = nb_sign_v fm in7345let h = binade_v fm in7346{ minf = minf fm; nl = at_i fm (1 - nb); nf = at_i fm (-1 - h);7347nsl = at_i fm (- h); nsf = at_i fm (-2); nz = at_i fm (-1);7348pz = at_i fm 0; psf = at_i fm 1; psl = at_i fm (h - 1);7349pf = at_i fm h; pl = at_i fm (nb - 2); pinf = pinf fm }7350
exception NotInterval7354Valid (25ms) (colibri2)7355let nan_dom () : dom7356ensures { result.u = Nil /\ result.nan }7357= FpInterval.nan_dom (any format)7358Valid (369ms) (colibri2)7359let singleton (v: t) : dom7360ensures { result.fm = fmt v }7361ensures { forall w. mem w result <-> fmt w = fmt v /\7362if is_nan v then is_nan w else is_not_nan w /\ le_dz v w /\ le_dz w v }7363= FpInterval.singleton (format_of v) v7364
[a, b], for a <= b neither NaN of one format
Valid (27ms) (colibri2)let interval (a b: t) : dom7367raises { NotInterval ->7368not (is_not_nan a /\ is_not_nan b /\ fmt a = fmt b /\ le_dz a b) }7369ensures { result.fm = fmt a }7370ensures { forall v. mem v result <-> fmt v = fmt a /\ is_not_nan v /\ in_iv v a b }7371= if is_nan a || is_nan b || not (eq_format (format_of a) (format_of b))7372|| not (le_diff_zero a b)7373then raise NotInterval;7374FpInterval.interval (format_of a) a b7375Valid (30ms) (colibri2)7376let top (fm: format) : dom7377ensures { result.fm = fm }7378ensures { forall v. mem v result <-> fmt v = fm }7379= FpInterval.top fm (minf fm) (pinf fm)7380Valid (31ms) (colibri2)7381let except (f: t) : dom7382ensures { result.fm = fmt f }7383ensures { forall v. mem v result <->7384fmt v = fmt f /\ if is_nan f then not (is_nan v) else v <> f }7385= let fm = format_of f in FpInterval.except fm (minf fm) (pinf fm) f7386Valid (23ms) (colibri2)7387let normal (fm: format) : dom7388ensures { result.fm = fm }7389ensures { forall v. mem v result <-> fmt v = fm /\ is_normal v }7390= let s = specials_of fm in FpInterval.normal fm s.nl s.nf s.pf s.pl7391Valid (32ms) (colibri2)7392let subnormal (fm: format) : dom7393ensures { result.fm = fm }7394ensures { forall v. mem v result <-> fmt v = fm /\ is_subnormal v }7395= let s = specials_of fm in FpInterval.subnormal fm s.nsl s.nsf s.psf s.psl7396Valid (28ms) (colibri2)7397let zeros (fm: format) : dom7398ensures { result.fm = fm }7399ensures { forall v. mem v result <-> fmt v = fm /\ is_zero v }7400= FpInterval.zeros fm (at_i fm (-1)) (at_i fm 0)7401Valid (28ms) (colibri2)7402let infinites (fm: format) : dom7403ensures { result.fm = fm }7404ensures { forall v. mem v result <-> fmt v = fm /\ is_inf v }7405= FpInterval.infinites fm (minf fm) (pinf fm)7406Valid (36ms) (colibri2)7407let finites (fm: format) : dom7408ensures { result.fm = fm }7409ensures { forall v. mem v result <-> fmt v = fm /\ is_not_nan v /\ not (is_inf v) }7410= let s = specials_of fm in FpInterval.finites fm s.nl s.pl7411Valid (50ms) (colibri2)7412let negatives (fm: format) : dom7413ensures { result.fm = fm }7414ensures { forall v. mem v result <-> fmt v = fm /\ is_not_nan v /\ not (is_positive v) }7415= FpInterval.negatives fm (minf fm) (at_i fm (-1))7416Valid (27ms) (colibri2)7417let positives (fm: format) : dom7418ensures { result.fm = fm }7419ensures { forall v. mem v result <-> fmt v = fm /\ is_not_nan v /\ is_positive v }7420= FpInterval.positives fm (at_i fm 0) (pinf fm)7421
Valid (45ms) (colibri2)let union (d1 d2: dom) : dom7425raises { FormatMismatch -> mismatch d1 d2 }7426ensures { result.fm = pfm d1 d2 }7427ensures { forall v. mem v result <-> mem_at (pfm d1 d2) v d1 \/ mem_at (pfm d1 d2) v d2 }7428= let (e1, e2) = common d1 d2 in FpInterval.union e1.fm e1 e27429Valid (70ms) (cvc5)7430let inter (d1 d2: dom) : option dom7431raises { FormatMismatch -> mismatch d1 d2 }7432ensures { match result with7433| None -> forall v. not (mem_at (pfm d1 d2) v d1 /\ mem_at (pfm d1 d2) v d2)7434| Some d -> d.fm = pfm d1 d2 /\ not (is_bot d) /\7435forall v. mem v d <-> mem_at (pfm d1 d2) v d1 /\ mem_at (pfm d1 d2) v d27436end }7437= let (e1, e2) = common d1 d2 in FpInterval.inter e1.fm e1 e27438Valid (94ms) (cvc4)7439let diff (d1 d2: dom) : option dom7440raises { FormatMismatch -> mismatch d1 d2 }7441ensures { match result with7442| None -> forall v. not (mem_at (pfm d1 d2) v d1 /\ not mem_at (pfm d1 d2) v d2)7443| Some d -> d.fm = pfm d1 d2 /\ not (is_bot d) /\7444forall v. mem v d <-> mem_at (pfm d1 d2) v d1 /\ not mem_at (pfm d1 d2) v d27445end }7446= let (e1, e2) = common d1 d2 in FpInterval.diff e1.fm e1 e27447Valid (82ms) (cvc4)7448let complement (fm: format) (d: dom) : option dom7449raises { FormatMismatch -> not fits fm d }7450ensures { match result with7451| None -> forall v. fmt v = fm -> mem_at fm v d7452| Some c -> c.fm = fm /\ not (is_bot c) /\7453forall v. mem v c <-> fmt v = fm /\ not mem_at fm v d7454end }7455= let e = check_fmt fm d in FpInterval.complement fm (minf fm) (pinf fm) e7456
The floats x of format fm with roundToIntegral m x in d (FpInterval.rti_back)
Valid (79ms) (cvc4)let rti_back (fm: format) (m: mode) (d: dom) : dom7460raises { FormatMismatch -> not fits fm d }7461ensures { result.fm = fm }7462ensures { forall x. fmt x = fm -> mem_at fm (fp_rti m x) d -> mem x result }7463= let e = check_fmt fm d in7464{proof…}7465let lemma pt (x: t) : unit7466requires { fmt x = fm } ensures { fmt (fp_rti m x) = fm }7467= if is_nan x then () else rti_not_nan m x in7468{qed}7469FpInterval.rti_back fm (minf fm) (pinf fm) m e7470
The floats x of format fm with x * y in r for some y of d (FpInterval.mul_back)
Valid (356ms) (cvc4)let mul_back (fm: format) (m: mode) (r d: dom) : dom7474raises { FormatMismatch -> not fits fm r \/ not fits fm d }7475ensures { result.fm = fm }7476ensures { forall x y. fmt x = fm -> mem_at fm y d -> mem_at fm (fp_mul m x y) r -> mem x result }7477= let er = check_fmt fm r in7478let ed = check_fmt fm d in7479{proof…} format_facts fm (); {qed}7480FpInterval.mul_back fm (minf fm) (pinf fm) (at_i fm (-1)) (at_i fm 0) m er ed7481
The floats x of format fm with x / y in r for some y of d (FpInterval.div_back_num)
Valid (86ms) (cvc5)let div_back_num (fm: format) (m: mode) (r d: dom) : dom7485raises { FormatMismatch -> not fits fm r \/ not fits fm d }7486ensures { result.fm = fm }7487ensures { forall x y. fmt x = fm -> mem_at fm y d -> mem_at fm (fp_div m x y) r -> mem x result }7488= let er = check_fmt fm r in7489let ed = check_fmt fm d in7490{proof…} format_facts fm (); {qed}7491FpInterval.div_back_num fm (minf fm) (pinf fm) (at_i fm (-1)) (at_i fm 0) m er ed7492
The floats y of format fm with x / y in r for some x of n (FpInterval.div_back_den)
Valid (81ms) (cvc5)let div_back_den (fm: format) (m: mode) (r n: dom) : dom7496raises { FormatMismatch -> not fits fm r \/ not fits fm n }7497ensures { result.fm = fm }7498ensures { forall x y. fmt y = fm -> mem_at fm x n -> mem_at fm (fp_div m x y) r -> mem y result }7499= let er = check_fmt fm r in7500let en = check_fmt fm n in7501{proof…} format_facts fm (); {qed}7502FpInterval.div_back_den fm (minf fm) (pinf fm) (at_i fm (-1)) (at_i fm 0) m er en7503Valid (346ms) (colibri2)7504let is_included (d1 d2: dom) : bool7505raises { FormatMismatch -> mismatch d1 d2 }7506ensures { result <-> forall v. mem_at (pfm d1 d2) v d1 -> mem_at (pfm d1 d2) v d2 }7507= let (e1, e2) = common d1 d2 in FpInterval.is_included e1.fm e1 e27508Valid (364ms) (colibri2)7509let is_distinct (d1 d2: dom) : bool7510raises { FormatMismatch -> mismatch d1 d2 }7511ensures { result <-> forall v. not (mem_at (pfm d1 d2) v d1 /\ mem_at (pfm d1 d2) v d2) }7512= let (e1, e2) = common d1 d2 in FpInterval.is_distinct e1.fm e1 e27513Valid (308ms) (cvc5)7514let is_distinct_or_included (d1 d2: dom) : comparison7515raises { FormatMismatch -> mismatch d1 d2 }7516ensures { result = Included <->7517forall v. mem_at (pfm d1 d2) v d1 -> mem_at (pfm d1 d2) v d2 }7518ensures { result = Disjoint <->7519(forall v. not (mem_at (pfm d1 d2) v d1 /\ mem_at (pfm d1 d2) v d2)) /\7520not (forall v. mem_at (pfm d1 d2) v d1 -> mem_at (pfm d1 d2) v d2) }7521= let (e1, e2) = common d1 d2 in FpInterval.is_distinct_or_included e1.fm e1 e27522Valid (30ms) (colibri2) (cvc5) (split_vc) (depth 1)7523let is_singleton (d: dom) : singleton7524ensures { match result with7525| NaN -> forall v. mem v d <-> fmt v = d.fm /\ is_nan v7526| Sin a -> not (is_nan a) /\ forall v. mem v d <-> v = a7527| No -> not (forall v. mem v d <-> fmt v = d.fm /\ is_nan v) /\7528forall a. not (forall v. mem v d <-> v = a)7529end }7530= FpInterval.is_singleton d.fm d7531Valid (12ms) (colibri2)7532let min_f (d: dom) : t7533raises { Empty -> d.u = Nil }7534ensures { fmt result = d.fm }7535ensures { mem_u result d.u /\ forall v. mem_u v d.u -> le_dz result v }7536= FpInterval.min_f d.fm d7537Valid (20ms) (colibri2)7538let max_f (d: dom) : t7539raises { Empty -> d.u = Nil }7540ensures { fmt result = d.fm }7541ensures { mem_u result d.u /\ forall v. mem_u v d.u -> le_dz v result }7542= FpInterval.max_f d.fm d7543Valid (38ms) (colibri2)7544let is_finite (d: dom) : bool7545ensures { result <-> forall v. mem v d -> not (is_nan v) /\ not (is_inf v) }7546= match dom_format d with7547| None ->7548{proof…} assert { d.nan -> mem (not_a_number d.fm) d }; {qed}7549not d.nan7550| Some fm -> FpInterval.is_finite fm (minf fm) (pinf fm) d7551end7552Valid (91ms) (cvc4)7553let classify (d: dom) : classify7554ensures { result.clnan <-> d.nan }7555ensures { result.neg_infinity <-> mem (minus_infinity d.fm) d }7556ensures { result.neg_normal <->7557exists v. mem v d /\ is_normal v /\ not is_positive v }7558ensures { result.neg_subnormal <->7559exists v. mem v d /\ is_subnormal v /\ not is_positive v }7560ensures { result.clzeros <-> exists v. mem v d /\ is_zero v }7561ensures { result.pos_subnormal <->7562exists v. mem v d /\ is_subnormal v /\ is_positive v }7563ensures { result.pos_normal <->7564exists v. mem v d /\ is_normal v /\ is_positive v }7565ensures { result.pos_infinity <-> mem (plus_infinity d.fm) d }7566= match dom_format d with7567| None ->7568{proof…}7569assert { forall v. mem v d -> is_nan v };7570assert { forall v. is_nan v -> not (is_normal v \/ is_subnormal v \/ is_zero v) };7571{qed}7572{ clnan = d.nan; neg_infinity = false; neg_normal = false;7573neg_subnormal = false; clzeros = false; pos_subnormal = false;7574pos_normal = false; pos_infinity = false }7575| Some fm -> FpInterval.classify_dom fm (specials_of fm) d7576end7577
Valid (48ms) (cvc5)let add_rule (fm: format) (da db: dom) : decision7581raises { FormatMismatch -> not (fits fm da /\ fits fm db) }7582ensures { forall m a b. mem_at fm a da -> mem_at fm b db ->7583fp_add m b a = fp_add m a b /\7584match result with7585| DNone -> true7586| DMerge -> fp_add m a b = b7587| DEq -> fp_eq (fp_add m a b) b7588| DLeB -> fp_le b (fp_add m a b)7589| DLeR -> fp_le (fp_add m a b) b7590end }7591= let ea = check_fmt fm da in7592let eb = check_fmt fm db in7593let (minf, pinf, nz, pz, m1, p1) = consts_of fm in7594Rules.add_rule fm minf pinf nz pz m1 p1 ea eb7595Valid (43ms) (cvc5)7596let mul_rule (fm: format) (da db: dom) : decision7597raises { FormatMismatch -> not (fits fm da /\ fits fm db) }7598ensures { forall m a b. mem_at fm a da -> mem_at fm b db ->7599fp_mul m b a = fp_mul m a b /\7600match result with7601| DNone | DEq -> true7602| DMerge -> fp_mul m a b = b7603| DLeB -> fp_le b (fp_mul m a b)7604| DLeR -> fp_le (fp_mul m a b) b7605end }7606= let ea = check_fmt fm da in7607let eb = check_fmt fm db in7608let (minf, pinf, nz, pz, m1, p1) = consts_of fm in7609Rules.mul_rule fm minf pinf nz pz m1 p1 ea eb7610Valid (53ms) (cvc5)7611let div_rule (fm: format) (da db: dom) : decision7612raises { FormatMismatch -> not (fits fm da /\ fits fm db) }7613ensures { forall m a b. mem_at fm a da -> mem_at fm b db ->7614match result with7615| DNone | DEq -> true7616| DMerge -> fp_div m a b = a7617| DLeB -> fp_le a (fp_div m a b)7618| DLeR -> fp_le (fp_div m a b) a7619end }7620= let ea = check_fmt fm da in7621let eb = check_fmt fm db in7622let (minf, pinf, nz, pz, m1, p1) = consts_of fm in7623Rules.div_rule fm minf pinf nz pz m1 p1 ea eb7624end7625