Common — library colibrilib.fp_interval — module Rules

The rules of fp_converter.ml on the sign and the magnitude

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

6825
module Rules
6826
use int.Int
6827
use list.List
6828
use real.RealInfix
6829
use colibrilib.fp.Ereal
6830
use colibrilib.fbin.Fp
6831
use colibrilib.fp_facts.Facts
6832
use Intervals
6833
use FpInterval
6834
6835
type
summary
= {
6836
s_neg
: bool;
s_zero
: bool;
s_pos
: bool;
6837
s_lt1
: bool;
s_one
: bool;
s_gt1
: bool }
6838
6839
predicate
all
(s: summary) =
6840
s.s_neg /\ s.s_zero /\ s.s_pos /\ s.s_lt1 /\ s.s_one /\ s.s_gt1
6841
6842
predicate
covers
(s: summary) (x: t) =
6843
if is_nan x \/ is_infinity x then all s
6844
else let r = to_real x in
6845
(r <. 0.0 -> s.s_neg) /\ (r = 0.0 -> s.s_zero) /\ (0.0 <. r -> s.s_pos) /\
6846
(-1.0 <. r <. 1.0 -> s.s_lt1) /\ (r = 1.0 \/ r = -1.0 -> s.s_one) /\
6847
(r <. -1.0 \/ 1.0 <. r -> s.s_gt1)
6848
6849
let function
top_s
: summary =
6850
{ s_neg = true; s_zero = true; s_pos = true; s_lt1 = true; s_one = true; s_gt1 = true }
6851
6852
let function
none_s
: summary =
6853
{ s_neg = false; s_zero = false; s_pos = false; s_lt1 = false; s_one = false; s_gt1 = false }
6854
Valid (49ms) (cvc5)
6855
let
join
(s1 s2: summary) : summary
6856
ensures { forall x. covers s1 x \/ covers s2 x -> covers result x }
6857
= { s_neg = s1.s_neg || s2.s_neg; s_zero = s1.s_zero || s2.s_zero;
6858
s_pos = s1.s_pos || s2.s_pos; s_lt1 = s1.s_lt1 || s2.s_lt1;
6859
s_one = s1.s_one || s2.s_one; s_gt1 = s1.s_gt1 || s2.s_gt1 }

The constants of the format: the infinities, the zeros, –1 and 1

6862
predicate
consts
(fm: format) (minf pinf nz pz m1 p1: t) =
6863
minf = minus_infinity fm /\ pinf = plus_infinity fm /\
6864
at_index fm nz (-1) /\ at_index fm pz 0 /\
6865
fmt m1 = fm /\ fmt p1 = fm /\ is_not_nan m1 /\ is_not_nan p1 /\
6866
ext m1 = Fin (-1.0) /\ ext p1 = Fin 1.0

c is finite of value v; x is compared to it by its value

  Valid (31ms) (colibri2)
6869
let ghost
by_value
(x c: t) (v: real) : unit
6870
requires { is_not_nan x /\ not is_infinity x /\ is_not_nan c /\ fmt x = fmt c }
6871
requires { ext c = Fin v }
6872
ensures { to_real x <. v -> lt_dz x c }
6873
ensures { v <. to_real x -> lt_dz c x }
6874
ensures { v <> 0.0 -> to_real x = v -> index x = index c }
6875
ensures { ext x = Fin (to_real x) }
6876
= {proof…}
6877
total x c;
6878
if pure { le_dz c x } then ext_le c x;
6879
if pure { le_dz x c } then ext_le x c;
6880
if pure { lt_dz x c /\ not (is_zero x /\ is_zero c) } then ext_lt x c;
6881
if pure { lt_dz c x /\ not (is_zero x /\ is_zero c) } then ext_lt c x;
6882
ext_zero c; ext_zero x
6883
{qed}
6884
Valid (545ms) (colibri2 35) (cvc4 7) (cvc5 2) (split_vc 17) (depth 5)
6885
let
summary_iv
(ghost fm: format) (minf pinf nz pz m1 p1: t) (a b: t) : summary
6886
requires { consts fm minf pinf nz pz m1 p1 }
6887
requires { fmt a = fm /\ fmt b = fm /\ is_not_nan a /\ is_not_nan b }
6888
ensures { forall x. in_iv x a b -> covers result x }
6889
= if le_diff_zero a minf || le_diff_zero pinf b then top_s
6890
else begin
6891
let s = {
6892
s_neg = lt_diff_zero a nz;
6893
s_zero = le_diff_zero a pz && le_diff_zero nz b;
6894
s_pos = lt_diff_zero pz b;
6895
s_lt1 = lt_diff_zero a p1 && lt_diff_zero m1 b;
6896
s_one = (le_diff_zero a p1 && le_diff_zero p1 b)
6897
|| (le_diff_zero a m1 && le_diff_zero m1 b);
6898
s_gt1 = lt_diff_zero a m1 || lt_diff_zero p1 b } in
6899
{proof…}
6900
ext_zero nz; ext_zero pz;
6901
let lemma pt (x: t) : unit
6902
requires { in_iv x a b } ensures { covers s x }
6903
= index_range x; index_range a; index_range b;
6904
if pure { is_minus_infinity x } then begin
6905
minus_infinity_unique x; assert { index a <= index minf }; absurd
6906
end;
6907
if pure { is_plus_infinity x } then begin
6908
plus_infinity_unique x; assert { index pinf <= index b }; absurd
6909
end;
6910
assert { is_not_nan x /\ fmt x = fm /\ not is_infinity x };
6911
by_value x nz 0.0; by_value x pz 0.0;
6912
by_value x m1 (-1.0); by_value x p1 1.0;
6913
if pure { to_real x = 0.0 } then begin
6914
ext_zero x; assert { index x = 0 \/ index x = -1 }
6915
end in
6916
{qed}
6917
s
6918
end
6919
Valid (49ms) (cvc5)
6920
let rec
summary_u
(ghost fm: format) (minf pinf nz pz m1 p1: t) (l: list (t, t)) : summary
6921
requires { consts fm minf pinf nz pz m1 p1 /\ ok_u l /\ fmt_u fm l }
6922
ensures { forall x. mem_u x l -> covers result x }
6923
variant { l }
6924
= match l with
6925
| Nil -> none_s
6926
| Cons (a, b) r ->
6927
join (summary_iv fm minf pinf nz pz m1 p1 a b) (summary_u fm minf pinf nz pz m1 p1 r)
6928
end
6929
Valid (29ms) (colibri2)
6930
let
summary
(ghost fm: format) (minf pinf nz pz m1 p1: t) (d: dom) : summary
6931
requires { consts fm minf pinf nz pz m1 p1 /\ d.fm = fm }
6932
ensures { forall x. mem x d -> covers result x }
6933
= if d.nan then top_s else summary_u fm minf pinf nz pz m1 p1 d.u

The rounding is increasing for fp_le, whatever the signs of zero

  Valid (16ms) (colibri2)
6936
let ghost
round_fp_le
(fm: format) (m: mode) (z1 z2: bool) (e1 e2: ereal) : unit
6937
requires { ele e1 e2 }
6938
ensures { fp_le (round_f fm m z1 e1) (round_f fm m z2 e2) }
6939
= {proof…}
6940
round_f_not_nan fm m z1 e1; round_f_not_nan fm m z2 e2;
6941
if pure { not (is_zero (round_f fm m z1 e1) /\ is_zero (round_f fm m z2 e2)) } then
6942
round_f_le fm m z1 z2 e1 e2
6943
{qed}

x is the rounding of its value, with any sign of zero when it is not zero

  Valid (44ms) (colibri2)
6947
let ghost
exact_any
(m: mode) (z: bool) (x: t) : unit
6948
requires { is_not_nan x }
6949
ensures { fp_eq (round_f (fmt x) m z (ext x)) x }
6950
ensures { not is_zero x -> round_f (fmt x) m z (ext x) = x }
6951
= {proof…}
6952
let zx = if is_positive x then false else true in
6953
round_f_exact m x;
6954
let y = round_f (fmt x) m z (ext x) in
6955
round_fp_le (fmt x) m z zx (ext x) (ext x);
6956
round_fp_le (fmt x) m zx z (ext x) (ext x);
6957
round_f_not_nan (fmt x) m z (ext x);
6958
if pure { not is_zero x } then begin
6959
assert { le_dz y x /\ le_dz x y };
6960
assert { index y = index x };
6961
index_inj x; index_inj y
6962
end
6963
{qed}
6964
6965
type
decision
=
DNone
|
DMerge
|
DEq
|
DLeB
|
DLeR

The rule of a + b, from the summary of a: a a zero gives b

  Valid (1.1s) (cvc4)
6968
let
add_rule
(ghost fm: format) (minf pinf nz pz m1 p1: t) (da db: dom) : decision
6969
requires { consts fm minf pinf nz pz m1 p1 /\ da.fm = fm /\ db.fm = fm }
6970
ensures { forall m a b. mem a da -> mem b db ->
6971
fp_add m b a = fp_add m a b /\
6972
match result with
6973
| DNone -> true
6974
| DMerge -> fp_add m a b = b
6975
| DEq -> fp_eq (fp_add m a b) b
6976
| DLeB -> fp_le b (fp_add m a b)
6977
| DLeR -> fp_le (fp_add m a b) b
6978
end }
6979
= let sa = summary fm minf pinf nz pz m1 p1 da in
6980
let sb = summary fm minf pinf nz pz m1 p1 db in
6981
let res =
6982
if not (sa.s_neg || sa.s_pos) then
6983
if sb.s_zero then (if db.nan then DNone else DEq) else DMerge
6984
else if db.nan || (sa.s_neg && sa.s_pos) then DNone
6985
else if sa.s_neg then DLeR else DLeB in
6986
{proof…}
6987
let lemma pt (m: mode) (a b: t) : unit
6988
requires { mem a da /\ mem b db }
6989
ensures { fp_add m b a = fp_add m a b }
6990
ensures { match res with
6991
| DNone -> true
6992
| DMerge -> fp_add m a b = b
6993
| DEq -> fp_eq (fp_add m a b) b
6994
| DLeB -> fp_le b (fp_add m a b)
6995
| DLeR -> fp_le (fp_add m a b) b
6996
end }
6997
= add_comm m a b;
6998
assert { covers sa a /\ covers sb b };
6999
match res with
7000
| DNone -> ()
7001
| DMerge | DEq ->
7002
assert { is_not_nan a /\ not is_infinity a /\ to_real a = 0.0 };
7003
assert { is_not_nan b };
7004
assert { ext a = Fin 0.0 };
7005
assert { eadd (ext a) (ext b) = ext b };
7006
assert { fp_add m a b = round_f fm m (add_zneg m a b) (ext b) };
7007
exact_any m (add_zneg m a b) b;
7008
if pure { res = DMerge } then begin
7009
assert { not is_infinity b };
7010
assert { to_real b <> 0.0 };
7011
ext_zero b
7012
end
7013
| DLeB | DLeR ->
7014
assert { is_not_nan a /\ not is_infinity a /\ is_not_nan b };
7015
assert { ext a = Fin (to_real a) };
7016
round_f_exact m b;
7017
let zb = if is_positive b then false else true in
7018
if pure { res = DLeB } then begin
7019
assert { 0.0 <=. to_real a };
7020
assert { ele (ext b) (eadd (ext a) (ext b)) };
7021
round_fp_le fm m zb (add_zneg m a b) (ext b) (eadd (ext a) (ext b))
7022
end else begin
7023
assert { to_real a <=. 0.0 };
7024
assert { ele (eadd (ext a) (ext b)) (ext b) };
7025
round_fp_le fm m (add_zneg m a b) zb (eadd (ext a) (ext b)) (ext b)
7026
end
7027
end in
7028
{qed}
7029
res
7030
Valid (149ms) (colibri2)
7031
let ghost
mul_le
(x y: real) : unit
7032
ensures { 0.0 <=. x <=. 1.0 -> 0.0 <=. y -> x *. y <=. y }
7033
ensures { 0.0 <=. x <=. 1.0 -> y <=. 0.0 -> y <=. x *. y }
7034
ensures { 1.0 <=. x -> 0.0 <=. y -> y <=. x *. y }
7035
ensures { 1.0 <=. x -> y <=. 0.0 -> x *. y <=. y }
7036
= {proof…}
7037
assert { x *. y -. y = (x -. 1.0) *. y }
7038
{qed}
7039
Valid (29ms) (colibri2)
7040
let ghost
div_le
(x y: real) : unit
7041
requires { 0.0 <. y }
7042
ensures { y <=. 1.0 -> 0.0 <=. x -> x <=. x *. (1.0 /. y) }
7043
ensures { y <=. 1.0 -> x <=. 0.0 -> x *. (1.0 /. y) <=. x }
7044
ensures { 1.0 <=. y -> 0.0 <=. x -> x *. (1.0 /. y) <=. x }
7045
ensures { 1.0 <=. y -> x <=. 0.0 -> x <=. x *. (1.0 /. y) }
7046
= {proof…}
7047
let i = 1.0 /. y in
7048
assert { 0.0 <. i /\ i *. y = 1.0 };
7049
assert { y <=. 1.0 -> 1.0 <=. i by i *. y <=. i *. 1.0 };
7050
assert { 1.0 <=. y -> i <=. 1.0 by i *. 1.0 <=. i *. y };
7051
mul_le i x;
7052
assert { x *. i = i *. x }
7053
{qed}

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)
7057
let
mul_rule
(ghost fm: format) (minf pinf nz pz m1 p1: t) (da db: dom) : decision
7058
requires { consts fm minf pinf nz pz m1 p1 /\ da.fm = fm /\ db.fm = fm }
7059
ensures { forall m a b. mem a da -> mem b db ->
7060
fp_mul m b a = fp_mul m a b /\
7061
match result with
7062
| DNone | DEq -> true
7063
| DMerge -> fp_mul m a b = b
7064
| DLeB -> fp_le b (fp_mul m a b)
7065
| DLeR -> fp_le (fp_mul m a b) b
7066
end }
7067
= let sa = summary fm minf pinf nz pz m1 p1 da in
7068
let sb = summary fm minf pinf nz pz m1 p1 db in
7069
let res =
7070
if not (sa.s_neg || sa.s_lt1 || sa.s_gt1) then DMerge
7071
else if (sb.s_pos && sb.s_neg) || sa.s_neg then DNone
7072
else if sa.s_lt1 && sa.s_gt1 then DNone
7073
else if (if sa.s_gt1 then sb.s_neg else not sb.s_neg) then DLeR else DLeB in
7074
{proof…}
7075
let lemma pt (m: mode) (a b: t) : unit
7076
requires { mem a da /\ mem b db }
7077
ensures { fp_mul m b a = fp_mul m a b }
7078
ensures { match res with
7079
| DNone | DEq -> true
7080
| DMerge -> fp_mul m a b = b
7081
| DLeB -> fp_le b (fp_mul m a b)
7082
| DLeR -> fp_le (fp_mul m a b) b
7083
end }
7084
= mul_comm m a b;
7085
assert { covers sa a /\ covers sb b };
7086
match res with
7087
| DNone | DEq -> ()
7088
| DMerge ->
7089
assert { is_not_nan a /\ not is_infinity a /\ to_real a = 1.0 };
7090
ext_sign a;
7091
assert { ext a = Fin 1.0 /\ is_positive a /\ not is_zero a };
7092
if pure { is_nan b } then begin
7093
nan_unique b; mul_special m a b
7094
end else begin
7095
assert { emul (ext a) (ext b) = ext b };
7096
assert { fp_mul m a b =
7097
round_f fm m (if is_positive b then false else true) (ext b) };
7098
round_f_exact m b
7099
end
7100
| DLeB | DLeR ->
7101
assert { is_not_nan a /\ not is_infinity a /\ is_not_nan b /\ not is_infinity b };
7102
let ra = to_real a in
7103
let rb = to_real b in
7104
assert { ext a = Fin ra /\ ext b = Fin rb };
7105
assert { 0.0 <=. ra };
7106
assert { fp_mul m a b = round_f fm m (mul_zneg a b) (Fin (ra *. rb)) };
7107
round_f_exact m b;
7108
let zb = if is_positive b then false else true in
7109
mul_le ra rb;
7110
if pure { sa.s_gt1 } then assert { 1.0 <=. ra }
7111
else assert { ra <=. 1.0 };
7112
if pure { sb.s_neg } then assert { rb <=. 0.0 }
7113
else assert { 0.0 <=. rb };
7114
if pure { res = DLeB } then
7115
round_fp_le fm m zb (mul_zneg a b) (Fin rb) (Fin (ra *. rb))
7116
else
7117
round_fp_le fm m (mul_zneg a b) zb (Fin (ra *. rb)) (Fin rb)
7118
end in
7119
{qed}
7120
res

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)
7124
let
div_rule
(ghost fm: format) (minf pinf nz pz m1 p1: t) (da db: dom) : decision
7125
requires { consts fm minf pinf nz pz m1 p1 /\ da.fm = fm /\ db.fm = fm }
7126
ensures { forall m a b. mem a da -> mem b db ->
7127
match result with
7128
| DNone | DEq -> true
7129
| DMerge -> fp_div m a b = a
7130
| DLeB -> fp_le a (fp_div m a b)
7131
| DLeR -> fp_le (fp_div m a b) a
7132
end }
7133
= let sa = summary fm minf pinf nz pz m1 p1 da in
7134
let sb = summary fm minf pinf nz pz m1 p1 db in
7135
let res =
7136
if not (sb.s_neg || sb.s_lt1 || sb.s_gt1) then DMerge
7137
else if (sa.s_pos && sa.s_neg) || sb.s_neg || sb.s_zero then DNone
7138
else if sb.s_lt1 && sb.s_gt1 then DNone
7139
else if (if sb.s_lt1 then sa.s_neg else not sa.s_neg) then DLeR else DLeB in
7140
{proof…}
7141
let lemma pt (m: mode) (a b: t) : unit
7142
requires { mem a da /\ mem b db }
7143
ensures { match res with
7144
| DNone | DEq -> true
7145
| DMerge -> fp_div m a b = a
7146
| DLeB -> fp_le a (fp_div m a b)
7147
| DLeR -> fp_le (fp_div m a b) a
7148
end }
7149
= assert { covers sa a /\ covers sb b };
7150
match res with
7151
| DNone | DEq -> ()
7152
| DMerge ->
7153
assert { is_not_nan b /\ not is_infinity b /\ to_real b = 1.0 };
7154
ext_sign b; ext_zero b;
7155
assert { ext b = Fin 1.0 /\ is_positive b /\ not is_zero b };
7156
if pure { is_nan a } then begin
7157
nan_unique a; div_special m a b
7158
end else begin
7159
assert { 1.0 /. 1.0 = 1.0 };
7160
assert { ediv (ext a) (ext b) = ext a };
7161
assert { fp_div m a b =
7162
round_f fm m (if is_positive a then false else true) (ext a) };
7163
round_f_exact m a
7164
end
7165
| DLeB | DLeR ->
7166
assert { is_not_nan a /\ not is_infinity a /\ is_not_nan b /\ not is_infinity b };
7167
let ra = to_real a in
7168
let rb = to_real b in
7169
assert { ext a = Fin ra /\ ext b = Fin rb };
7170
assert { 0.0 <. rb };
7171
ext_zero b;
7172
assert { not is_zero b };
7173
assert { fp_div m a b = round_f fm m (mul_zneg a b) (Fin (ra *. (1.0 /. rb))) };
7174
round_f_exact m a;
7175
let za = if is_positive a then false else true in
7176
div_le ra rb;
7177
if pure { sb.s_lt1 } then assert { rb <=. 1.0 }
7178
else assert { 1.0 <=. rb };
7179
if pure { sa.s_neg } then assert { ra <=. 0.0 }
7180
else assert { 0.0 <=. ra };
7181
if pure { res = DLeB } then
7182
round_fp_le fm m za (mul_zneg a b) (Fin ra) (Fin (ra *. (1.0 /. rb)))
7183
else
7184
round_fp_le fm m (mul_zneg a b) za (Fin (ra *. (1.0 /. rb))) (Fin ra)
7185
end in
7186
{qed}
7187
res

The rule of fp_monotone.ml: y <= z gives x + y <= x + z when neither is NaN

  Valid (516ms) (cvc4)
7191
let ghost
add_mono
(m: mode) (x y z: t) : unit
7192
requires { fp_le y z /\ fmt x = fmt y }
7193
requires { is_not_nan (fp_add m x y) /\ is_not_nan (fp_add m x z) }
7194
ensures { fp_le (fp_add m x y) (fp_add m x z) }
7195
= {proof…}
7196
add_special m x y; add_special m x z;
7197
assert { is_not_nan x /\ is_not_nan y /\ is_not_nan z };
7198
assert { fmt z = fmt y };
7199
if pure { le_dz y z } then ext_le y z
7200
else begin ext_zero y; ext_zero z end;
7201
assert { ele (ext y) (ext z) };
7202
assert { ele (eadd (ext x) (ext y)) (eadd (ext x) (ext z)) };
7203
round_fp_le (fmt x) m (add_zneg m x y) (add_zneg m x z)
7204
(eadd (ext x) (ext y)) (eadd (ext x) (ext z))
7205
{qed}
7206
end