library colibrilib.fp_interval — module Rulesfp_converter.ml on the sign and the magnitudeA summary of a domain over–approximates the signs and the magnitudes (below, at or above 1) of its floats; NaN and the infinities give every flag. From the summaries, a rule decides a fact on the result r of a + b, a * b or a / b: r = b (merge), fp_eq r b, b <= r or r <= b (fp_le, the zeros are equal).
module Rules6825use int.Int6826use list.List6827use real.RealInfix6828use colibrilib.fp.Ereal6829use colibrilib.fbin.Fp6830use colibrilib.fp_facts.Facts6831use Intervals6832use FpInterval68336834type summary = {6835s_neg: bool; s_zero: bool; s_pos: bool;6836s_lt1: bool; s_one: bool; s_gt1: bool }68376838predicate all (s: summary) =6839s.s_neg /\ s.s_zero /\ s.s_pos /\ s.s_lt1 /\ s.s_one /\ s.s_gt168406841predicate covers (s: summary) (x: t) =6842if is_nan x \/ is_infinity x then all s6843else let r = to_real x in6844(r <. 0.0 -> s.s_neg) /\ (r = 0.0 -> s.s_zero) /\ (0.0 <. r -> s.s_pos) /\6845(-1.0 <. r <. 1.0 -> s.s_lt1) /\ (r = 1.0 \/ r = -1.0 -> s.s_one) /\6846(r <. -1.0 \/ 1.0 <. r -> s.s_gt1)68476848let function top_s : summary =6849{ s_neg = true; s_zero = true; s_pos = true; s_lt1 = true; s_one = true; s_gt1 = true }68506851let function none_s : summary =6852{ s_neg = false; s_zero = false; s_pos = false; s_lt1 = false; s_one = false; s_gt1 = false }6853Valid (49ms) (cvc5)6854let join (s1 s2: summary) : summary6855ensures { forall x. covers s1 x \/ covers s2 x -> covers result x }6856= { s_neg = s1.s_neg || s2.s_neg; s_zero = s1.s_zero || s2.s_zero;6857s_pos = s1.s_pos || s2.s_pos; s_lt1 = s1.s_lt1 || s2.s_lt1;6858s_one = s1.s_one || s2.s_one; s_gt1 = s1.s_gt1 || s2.s_gt1 }6859
The constants of the format: the infinities, the zeros, –1 and 1
predicate consts (fm: format) (minf pinf nz pz m1 p1: t) =6862minf = minus_infinity fm /\ pinf = plus_infinity fm /\6863at_index fm nz (-1) /\ at_index fm pz 0 /\6864fmt m1 = fm /\ fmt p1 = fm /\ is_not_nan m1 /\ is_not_nan p1 /\6865ext m1 = Fin (-1.0) /\ ext p1 = Fin 1.06866
c is finite of value v; x is compared to it by its value
Valid (31ms) (colibri2)let ghost by_value (x c: t) (v: real) : unit6869requires { is_not_nan x /\ not is_infinity x /\ is_not_nan c /\ fmt x = fmt c }6870requires { ext c = Fin v }6871ensures { to_real x <. v -> lt_dz x c }6872ensures { v <. to_real x -> lt_dz c x }6873ensures { v <> 0.0 -> to_real x = v -> index x = index c }6874ensures { ext x = Fin (to_real x) }6875= {proof…}6876total x c;6877if pure { le_dz c x } then ext_le c x;6878if pure { le_dz x c } then ext_le x c;6879if pure { lt_dz x c /\ not (is_zero x /\ is_zero c) } then ext_lt x c;6880if pure { lt_dz c x /\ not (is_zero x /\ is_zero c) } then ext_lt c x;6881ext_zero c; ext_zero x6882{qed}6883Valid (545ms) (colibri2 35) (cvc4 7) (cvc5 2) (split_vc 17) (depth 5)6884let summary_iv (ghost fm: format) (minf pinf nz pz m1 p1: t) (a b: t) : summary6885requires { consts fm minf pinf nz pz m1 p1 }6886requires { fmt a = fm /\ fmt b = fm /\ is_not_nan a /\ is_not_nan b }6887ensures { forall x. in_iv x a b -> covers result x }6888= if le_diff_zero a minf || le_diff_zero pinf b then top_s6889else begin6890let s = {6891s_neg = lt_diff_zero a nz;6892s_zero = le_diff_zero a pz && le_diff_zero nz b;6893s_pos = lt_diff_zero pz b;6894s_lt1 = lt_diff_zero a p1 && lt_diff_zero m1 b;6895s_one = (le_diff_zero a p1 && le_diff_zero p1 b)6896|| (le_diff_zero a m1 && le_diff_zero m1 b);6897s_gt1 = lt_diff_zero a m1 || lt_diff_zero p1 b } in6898{proof…}6899ext_zero nz; ext_zero pz;6900let lemma pt (x: t) : unit6901requires { in_iv x a b } ensures { covers s x }6902= index_range x; index_range a; index_range b;6903if pure { is_minus_infinity x } then begin6904minus_infinity_unique x; assert { index a <= index minf }; absurd6905end;6906if pure { is_plus_infinity x } then begin6907plus_infinity_unique x; assert { index pinf <= index b }; absurd6908end;6909assert { is_not_nan x /\ fmt x = fm /\ not is_infinity x };6910by_value x nz 0.0; by_value x pz 0.0;6911by_value x m1 (-1.0); by_value x p1 1.0;6912if pure { to_real x = 0.0 } then begin6913ext_zero x; assert { index x = 0 \/ index x = -1 }6914end in6915{qed}6916s6917end6918Valid (49ms) (cvc5)6919let rec summary_u (ghost fm: format) (minf pinf nz pz m1 p1: t) (l: list (t, t)) : summary6920requires { consts fm minf pinf nz pz m1 p1 /\ ok_u l /\ fmt_u fm l }6921ensures { forall x. mem_u x l -> covers result x }6922variant { l }6923= match l with6924| Nil -> none_s6925| Cons (a, b) r ->6926join (summary_iv fm minf pinf nz pz m1 p1 a b) (summary_u fm minf pinf nz pz m1 p1 r)6927end6928Valid (29ms) (colibri2)6929let summary (ghost fm: format) (minf pinf nz pz m1 p1: t) (d: dom) : summary6930requires { consts fm minf pinf nz pz m1 p1 /\ d.fm = fm }6931ensures { forall x. mem x d -> covers result x }6932= if d.nan then top_s else summary_u fm minf pinf nz pz m1 p1 d.u6933
The rounding is increasing for fp_le, whatever the signs of zero
Valid (16ms) (colibri2)let ghost round_fp_le (fm: format) (m: mode) (z1 z2: bool) (e1 e2: ereal) : unit6936requires { ele e1 e2 }6937ensures { fp_le (round_f fm m z1 e1) (round_f fm m z2 e2) }6938= {proof…}6939round_f_not_nan fm m z1 e1; round_f_not_nan fm m z2 e2;6940if pure { not (is_zero (round_f fm m z1 e1) /\ is_zero (round_f fm m z2 e2)) } then6941round_f_le fm m z1 z2 e1 e26942{qed}6943
x is the rounding of its value, with any sign of zero when it is not zero
Valid (44ms) (colibri2)let ghost exact_any (m: mode) (z: bool) (x: t) : unit6947requires { is_not_nan x }6948ensures { fp_eq (round_f (fmt x) m z (ext x)) x }6949ensures { not is_zero x -> round_f (fmt x) m z (ext x) = x }6950= {proof…}6951let zx = if is_positive x then false else true in6952round_f_exact m x;6953let y = round_f (fmt x) m z (ext x) in6954round_fp_le (fmt x) m z zx (ext x) (ext x);6955round_fp_le (fmt x) m zx z (ext x) (ext x);6956round_f_not_nan (fmt x) m z (ext x);6957if pure { not is_zero x } then begin6958assert { le_dz y x /\ le_dz x y };6959assert { index y = index x };6960index_inj x; index_inj y6961end6962{qed}69636964type decision = DNone | DMerge | DEq | DLeB | DLeR6965
The rule of a + b, from the summary of a: a a zero gives b
Valid (1.1s) (cvc4)let add_rule (ghost fm: format) (minf pinf nz pz m1 p1: t) (da db: dom) : decision6968requires { consts fm minf pinf nz pz m1 p1 /\ da.fm = fm /\ db.fm = fm }6969ensures { forall m a b. mem a da -> mem b db ->6970fp_add m b a = fp_add m a b /\6971match result with6972| DNone -> true6973| DMerge -> fp_add m a b = b6974| DEq -> fp_eq (fp_add m a b) b6975| DLeB -> fp_le b (fp_add m a b)6976| DLeR -> fp_le (fp_add m a b) b6977end }6978= let sa = summary fm minf pinf nz pz m1 p1 da in6979let sb = summary fm minf pinf nz pz m1 p1 db in6980let res =6981if not (sa.s_neg || sa.s_pos) then6982if sb.s_zero then (if db.nan then DNone else DEq) else DMerge6983else if db.nan || (sa.s_neg && sa.s_pos) then DNone6984else if sa.s_neg then DLeR else DLeB in6985{proof…}6986let lemma pt (m: mode) (a b: t) : unit6987requires { mem a da /\ mem b db }6988ensures { fp_add m b a = fp_add m a b }6989ensures { match res with6990| DNone -> true6991| DMerge -> fp_add m a b = b6992| DEq -> fp_eq (fp_add m a b) b6993| DLeB -> fp_le b (fp_add m a b)6994| DLeR -> fp_le (fp_add m a b) b6995end }6996= add_comm m a b;6997assert { covers sa a /\ covers sb b };6998match res with6999| DNone -> ()7000| DMerge | DEq ->7001assert { is_not_nan a /\ not is_infinity a /\ to_real a = 0.0 };7002assert { is_not_nan b };7003assert { ext a = Fin 0.0 };7004assert { eadd (ext a) (ext b) = ext b };7005assert { fp_add m a b = round_f fm m (add_zneg m a b) (ext b) };7006exact_any m (add_zneg m a b) b;7007if pure { res = DMerge } then begin7008assert { not is_infinity b };7009assert { to_real b <> 0.0 };7010ext_zero b7011end7012| DLeB | DLeR ->7013assert { is_not_nan a /\ not is_infinity a /\ is_not_nan b };7014assert { ext a = Fin (to_real a) };7015round_f_exact m b;7016let zb = if is_positive b then false else true in7017if pure { res = DLeB } then begin7018assert { 0.0 <=. to_real a };7019assert { ele (ext b) (eadd (ext a) (ext b)) };7020round_fp_le fm m zb (add_zneg m a b) (ext b) (eadd (ext a) (ext b))7021end else begin7022assert { to_real a <=. 0.0 };7023assert { ele (eadd (ext a) (ext b)) (ext b) };7024round_fp_le fm m (add_zneg m a b) zb (eadd (ext a) (ext b)) (ext b)7025end7026end in7027{qed}7028res7029Valid (149ms) (colibri2)7030let ghost mul_le (x y: real) : unit7031ensures { 0.0 <=. x <=. 1.0 -> 0.0 <=. y -> x *. y <=. y }7032ensures { 0.0 <=. x <=. 1.0 -> y <=. 0.0 -> y <=. x *. y }7033ensures { 1.0 <=. x -> 0.0 <=. y -> y <=. x *. y }7034ensures { 1.0 <=. x -> y <=. 0.0 -> x *. y <=. y }7035= {proof…}7036assert { x *. y -. y = (x -. 1.0) *. y }7037{qed}7038Valid (29ms) (colibri2)7039let ghost div_le (x y: real) : unit7040requires { 0.0 <. y }7041ensures { y <=. 1.0 -> 0.0 <=. x -> x <=. x *. (1.0 /. y) }7042ensures { y <=. 1.0 -> x <=. 0.0 -> x *. (1.0 /. y) <=. x }7043ensures { 1.0 <=. y -> 0.0 <=. x -> x *. (1.0 /. y) <=. x }7044ensures { 1.0 <=. y -> x <=. 0.0 -> x <=. x *. (1.0 /. y) }7045= {proof…}7046let i = 1.0 /. y in7047assert { 0.0 <. i /\ i *. y = 1.0 };7048assert { y <=. 1.0 -> 1.0 <=. i by i *. y <=. i *. 1.0 };7049assert { 1.0 <=. y -> i <=. 1.0 by i *. 1.0 <=. i *. y };7050mul_le i x;7051assert { x *. i = i *. x }7052{qed}7053
The rule of a * b, from the summary of a: a = 1 gives b; |a| <= 1 or |a| >= 1, a >= 0, b of one sign give an order
Valid (398ms) (colibri2 27) (cvc4 2) (cvc5 7) (split_vc) (depth 1)let mul_rule (ghost fm: format) (minf pinf nz pz m1 p1: t) (da db: dom) : decision7057requires { consts fm minf pinf nz pz m1 p1 /\ da.fm = fm /\ db.fm = fm }7058ensures { forall m a b. mem a da -> mem b db ->7059fp_mul m b a = fp_mul m a b /\7060match result with7061| DNone | DEq -> true7062| DMerge -> fp_mul m a b = b7063| DLeB -> fp_le b (fp_mul m a b)7064| DLeR -> fp_le (fp_mul m a b) b7065end }7066= let sa = summary fm minf pinf nz pz m1 p1 da in7067let sb = summary fm minf pinf nz pz m1 p1 db in7068let res =7069if not (sa.s_neg || sa.s_lt1 || sa.s_gt1) then DMerge7070else if (sb.s_pos && sb.s_neg) || sa.s_neg then DNone7071else if sa.s_lt1 && sa.s_gt1 then DNone7072else if (if sa.s_gt1 then sb.s_neg else not sb.s_neg) then DLeR else DLeB in7073{proof…}7074let lemma pt (m: mode) (a b: t) : unit7075requires { mem a da /\ mem b db }7076ensures { fp_mul m b a = fp_mul m a b }7077ensures { match res with7078| DNone | DEq -> true7079| DMerge -> fp_mul m a b = b7080| DLeB -> fp_le b (fp_mul m a b)7081| DLeR -> fp_le (fp_mul m a b) b7082end }7083= mul_comm m a b;7084assert { covers sa a /\ covers sb b };7085match res with7086| DNone | DEq -> ()7087| DMerge ->7088assert { is_not_nan a /\ not is_infinity a /\ to_real a = 1.0 };7089ext_sign a;7090assert { ext a = Fin 1.0 /\ is_positive a /\ not is_zero a };7091if pure { is_nan b } then begin7092nan_unique b; mul_special m a b7093end else begin7094assert { emul (ext a) (ext b) = ext b };7095assert { fp_mul m a b =7096round_f fm m (if is_positive b then false else true) (ext b) };7097round_f_exact m b7098end7099| DLeB | DLeR ->7100assert { is_not_nan a /\ not is_infinity a /\ is_not_nan b /\ not is_infinity b };7101let ra = to_real a in7102let rb = to_real b in7103assert { ext a = Fin ra /\ ext b = Fin rb };7104assert { 0.0 <=. ra };7105assert { fp_mul m a b = round_f fm m (mul_zneg a b) (Fin (ra *. rb)) };7106round_f_exact m b;7107let zb = if is_positive b then false else true in7108mul_le ra rb;7109if pure { sa.s_gt1 } then assert { 1.0 <=. ra }7110else assert { ra <=. 1.0 };7111if pure { sb.s_neg } then assert { rb <=. 0.0 }7112else assert { 0.0 <=. rb };7113if pure { res = DLeB } then7114round_fp_le fm m zb (mul_zneg a b) (Fin rb) (Fin (ra *. rb))7115else7116round_fp_le fm m (mul_zneg a b) zb (Fin (ra *. rb)) (Fin rb)7117end in7118{qed}7119res7120
The rule of a / b, from the summary of b: b = 1 gives a; 0 < b <= 1 or b >= 1, a of one sign give an order
Valid (407ms) (colibri2 39) (cvc4 2) (cvc5 5) (split_vc) (depth 1)let div_rule (ghost fm: format) (minf pinf nz pz m1 p1: t) (da db: dom) : decision7124requires { consts fm minf pinf nz pz m1 p1 /\ da.fm = fm /\ db.fm = fm }7125ensures { forall m a b. mem a da -> mem b db ->7126match result with7127| DNone | DEq -> true7128| DMerge -> fp_div m a b = a7129| DLeB -> fp_le a (fp_div m a b)7130| DLeR -> fp_le (fp_div m a b) a7131end }7132= let sa = summary fm minf pinf nz pz m1 p1 da in7133let sb = summary fm minf pinf nz pz m1 p1 db in7134let res =7135if not (sb.s_neg || sb.s_lt1 || sb.s_gt1) then DMerge7136else if (sa.s_pos && sa.s_neg) || sb.s_neg || sb.s_zero then DNone7137else if sb.s_lt1 && sb.s_gt1 then DNone7138else if (if sb.s_lt1 then sa.s_neg else not sa.s_neg) then DLeR else DLeB in7139{proof…}7140let lemma pt (m: mode) (a b: t) : unit7141requires { mem a da /\ mem b db }7142ensures { match res with7143| DNone | DEq -> true7144| DMerge -> fp_div m a b = a7145| DLeB -> fp_le a (fp_div m a b)7146| DLeR -> fp_le (fp_div m a b) a7147end }7148= assert { covers sa a /\ covers sb b };7149match res with7150| DNone | DEq -> ()7151| DMerge ->7152assert { is_not_nan b /\ not is_infinity b /\ to_real b = 1.0 };7153ext_sign b; ext_zero b;7154assert { ext b = Fin 1.0 /\ is_positive b /\ not is_zero b };7155if pure { is_nan a } then begin7156nan_unique a; div_special m a b7157end else begin7158assert { 1.0 /. 1.0 = 1.0 };7159assert { ediv (ext a) (ext b) = ext a };7160assert { fp_div m a b =7161round_f fm m (if is_positive a then false else true) (ext a) };7162round_f_exact m a7163end7164| DLeB | DLeR ->7165assert { is_not_nan a /\ not is_infinity a /\ is_not_nan b /\ not is_infinity b };7166let ra = to_real a in7167let rb = to_real b in7168assert { ext a = Fin ra /\ ext b = Fin rb };7169assert { 0.0 <. rb };7170ext_zero b;7171assert { not is_zero b };7172assert { fp_div m a b = round_f fm m (mul_zneg a b) (Fin (ra *. (1.0 /. rb))) };7173round_f_exact m a;7174let za = if is_positive a then false else true in7175div_le ra rb;7176if pure { sb.s_lt1 } then assert { rb <=. 1.0 }7177else assert { 1.0 <=. rb };7178if pure { sa.s_neg } then assert { ra <=. 0.0 }7179else assert { 0.0 <=. ra };7180if pure { res = DLeB } then7181round_fp_le fm m za (mul_zneg a b) (Fin ra) (Fin (ra *. (1.0 /. rb)))7182else7183round_fp_le fm m (mul_zneg a b) za (Fin (ra *. (1.0 /. rb))) (Fin ra)7184end in7185{qed}7186res7187
The rule of fp_monotone.ml: y <= z gives x + y <= x + z when neither is NaN
Valid (516ms) (cvc4)let ghost add_mono (m: mode) (x y z: t) : unit7191requires { fp_le y z /\ fmt x = fmt y }7192requires { is_not_nan (fp_add m x y) /\ is_not_nan (fp_add m x z) }7193ensures { fp_le (fp_add m x y) (fp_add m x z) }7194= {proof…}7195add_special m x y; add_special m x z;7196assert { is_not_nan x /\ is_not_nan y /\ is_not_nan z };7197assert { fmt z = fmt y };7198if pure { le_dz y z } then ext_le y z7199else begin ext_zero y; ext_zero z end;7200assert { ele (ext y) (ext z) };7201assert { ele (eadd (ext x) (ext y)) (eadd (ext x) (ext z)) };7202round_fp_le (fmt x) m (add_zneg m x y) (add_zneg m x z)7203(eadd (ext x) (ext y)) (eadd (ext x) (ext z))7204{qed}7205end7206