Common — library colibrilib.fp_conv — module RealConv

The conversions between floats and reals

fp.to_real and to_fp of a real, on the domains.

879
module RealConv
880
use int.Int
881
use list.List
882
use option.Option
883
use real.RealInfix
884
use colibrilib.ring.Atom
885
use colibrilib.fp.Ereal
886
use colibrilib.fbin.Fp
887
use colibrilib.fp_facts.Facts
888
use colibrilib.stda.StdA as A
889
use colibrilib.fp_interval.Intervals
890
use colibrilib.fp_interval.FpInterval
891
use Env

updr, or the contradiction for the empty domain

  Valid (16ms) (colibri2)
894
let
updr_dom
(d: env) (n: Atom.t) (l: rdom) : unit
895
requires { live d -> rmem (d.mr n) l }
896
= match l with
897
| Nil -> contradiction d
898
| _ -> updr d n l
899
end

fp.to_real, forward

The reals of the floats of the domain, when it holds no NaN and no infinity (fp.to_real of those is unspecified): None is no information.

  Valid (1.2s) (colibri2 10) (cvc5 2) (split_vc 2) (depth 2)
906
let rec
to_real_u
(ghost fm: format) (minf pinf: t) (l: list (t, t)) : option rdom
907
requires { ok_u l /\ fmt_u fm l }
908
requires { fmt minf = fm /\ fmt pinf = fm /\ minf = minus_infinity fm /\ pinf = plus_infinity fm }
909
ensures { match result with
910
| Some r -> forall x. mem_u x l -> is_not_nan x /\ not (is_inf x) /\ rmem (to_real x) r
911
| None -> true
912
end }
913
variant { l }
914
= match l with
915
| Nil -> Some Nil
916
| Cons (a, b) l' ->
917
if is_inf_f fm minf pinf a || is_inf_f fm minf pinf b then None
918
else begin
919
match to_real_u fm minf pinf l' with
920
| None -> None
921
| Some r ->
922
Some (Cons (RInter (BLarge (to_a a)) (BLarge (to_a b))) r)
923
end
924
end
925
end
926
Valid (32ms) (colibri2)
927
let
to_real_fwd
(ghost fm: format) (minf pinf: t) (d: dom) : option rdom
928
requires { d.fm = fm }
929
requires { fmt minf = fm /\ fmt pinf = fm /\ minf = minus_infinity fm /\ pinf = plus_infinity fm }
930
ensures { match result with
931
| Some r -> forall x. mem x d -> is_not_nan x /\ not (is_inf x) /\ rmem (to_real x) r
932
| None -> true
933
end }
934
= if d.nan then None else to_real_u fm minf pinf d.u

fp.to_real, backward

The finite floats whose real is in a real domain.

f is finite of value a

  Valid (21ms) (colibri2)
941
let
exact
(minf pinf: t) (a: A.t) (f: t) : bool
942
requires { fmt minf = fmt f /\ fmt pinf = fmt f }
943
requires { minf = minus_infinity (fmt f) /\ pinf = plus_infinity (fmt f) }
944
ensures { result <-> is_not_nan f /\ not (is_inf f) /\ to_real f = A.real a }
945
= if is_nan f then false
946
else if is_inf_f (fmt f) minf pinf f then false
947
else a_eq a (to_a f)

The least finite float at or above (strictly when strict) a

  Valid (41ms) (colibri2)
950
let
lo_of
(fm: format) (minf pinf: t) (strict: bool) (a: A.t) : t
951
requires { fmt minf = fm /\ fmt pinf = fm /\ minf = minus_infinity fm /\ pinf = plus_infinity fm }
952
ensures { fmt result = fm }
953
ensures { forall v. fmt v = fm -> is_not_nan v -> not (is_inf v) ->
954
(if strict then A.real a <. to_real v else A.real a <=. to_real v) -> le_dz result v }
955
= let f = ceil_f fm a in
956
float_lo f strict (exact minf pinf a f)
957
Valid (51ms) (colibri2)
958
let
hi_of
(fm: format) (minf pinf: t) (strict: bool) (a: A.t) : t
959
requires { fmt minf = fm /\ fmt pinf = fm /\ minf = minus_infinity fm /\ pinf = plus_infinity fm }
960
ensures { fmt result = fm }
961
ensures { forall v. fmt v = fm -> is_not_nan v -> not (is_inf v) ->
962
(if strict then to_real v <. A.real a else to_real v <=. A.real a) -> le_dz v result }
963
= let f = floor_f fm a in
964
float_hi f strict (exact minf pinf a f)

[l, h], or the empty domain

  Valid (95ms) (cvc5)
967
let
interval_o
(fm: format) (l h: t) : dom
968
requires { fmt l = fm /\ fmt h = fm }
969
ensures { result.fm = fm }
970
ensures { forall v. fmt v = fm -> is_not_nan v -> le_dz l v -> le_dz v h -> mem v result }
971
= if is_nan l || is_nan h then empty_dom fm
972
else if le_diff_zero l h then interval fm l h
973
else begin
974
{proof…} let lemma pt (v: t) : unit
975
requires { le_dz l v /\ le_dz v h } ensures { false } = le_trans l v h in {qed}
976
empty_dom fm
977
end
978
Valid (171ms) (colibri2)
979
let
of_riv
(fm: format) (minf pinf: t) (i: riv) : dom
980
requires { fmt minf = fm /\ fmt pinf = fm /\ minf = minus_infinity fm /\ pinf = plus_infinity fm }
981
ensures { result.fm = fm }
982
ensures { forall v. fmt v = fm -> is_not_nan v -> not (is_inf v) ->
983
rmem_iv (to_real v) i -> mem v result }
984
= match i with
985
| RSing a -> interval_o fm (lo_of fm minf pinf false a) (hi_of fm minf pinf false a)
986
| RInter rl rh ->
987
let l = match rl with
988
| BInf -> minf
989
| BLarge a -> lo_of fm minf pinf false a
990
| BStrict a -> lo_of fm minf pinf true a
991
end in
992
let h = match rh with
993
| BInf -> pinf
994
| BLarge a -> hi_of fm minf pinf false a
995
| BStrict a -> hi_of fm minf pinf true a
996
end in
997
{proof…}
998
let lemma pt (v: t) : unit
999
requires { fmt v = fm /\ is_not_nan v /\ not (is_inf v) /\ rmem_iv (to_real v) i }
1000
ensures { le_dz l v /\ le_dz v h }
1001
= match rl with BInf -> lt_le minf v | _ -> () end;
1002
match rh with BInf -> lt_le v pinf | _ -> () end in
1003
{qed}
1004
interval_o fm l h
1005
end
1006
Valid (380ms) (colibri2)
1007
let rec
of_rdom
(fm: format) (minf pinf: t) (l: rdom) : dom
1008
requires { fmt minf = fm /\ fmt pinf = fm /\ minf = minus_infinity fm /\ pinf = plus_infinity fm }
1009
ensures { result.fm = fm }
1010
ensures { forall v. fmt v = fm -> is_not_nan v -> not (is_inf v) ->
1011
rmem (to_real v) l -> mem v result }
1012
variant { l }
1013
= match l with
1014
| Nil -> empty_dom fm
1015
| Cons i l' -> union fm (of_riv fm minf pinf i) (of_rdom fm minf pinf l')
1016
end

The floats of va that are NaN, infinite, or whose real is in vr; None for none

  Valid (638ms) (cvc5)
1020
let
to_real_back
(fm: format) (minf pinf: t) (va: dom) (vr: rdom) : option dom
1021
requires { fmt minf = fm /\ fmt pinf = fm /\ minf = minus_infinity fm /\ pinf = plus_infinity fm }
1022
requires { va.fm = fm }
1023
ensures { match result with Some r -> r.fm = fm | None -> true end }
1024
ensures { forall v. mem v va -> (is_not_nan v /\ not (is_inf v) -> rmem (to_real v) vr) ->
1025
match result with Some r -> mem v r | None -> false end }
1026
= let ex = union fm (nan_dom fm) (infinites fm minf pinf) in
1027
let u = of_rdom fm minf pinf vr in
1028
match inter fm va (union fm ex u) with
1029
| None -> None
1030
| Some r -> Some r
1031
end

to_fp of a real, forward

round_x fm md x is to_fp of SMT–LIB: a zero result is –0 when x < 0.

1037
function
round_x
(fm: format) (md: mode) (x: real) : t =
1038
round_f fm md (x <. 0.0) (Fin x)
1039
Valid (41ms) (colibri2)
1040
let ghost
minf_le
(fm: format) (v: t) : unit
1041
requires { fmt v = fm /\ is_not_nan v }
1042
ensures { le_dz (minus_infinity fm) v }
1043
= if is_minus_infinity v then le_refl v else lt_le (minus_infinity fm) v
1044
Valid (15ms) (colibri2)
1045
let ghost
le_pinf
(fm: format) (v: t) : unit
1046
requires { fmt v = fm /\ is_not_nan v }
1047
ensures { le_dz v (plus_infinity fm) }
1048
= if is_plus_infinity v then le_refl v else lt_le v (plus_infinity fm)
1049
Valid (466ms) (colibri2 17) (cvc5 2) (split_vc 3) (depth 2)
1050
let
of_riv1
(fm: format) (minf pinf: t) (md: mode) (i: riv) : dom
1051
requires { fmt minf = fm /\ fmt pinf = fm /\ minf = minus_infinity fm /\ pinf = plus_infinity fm }
1052
ensures { result.fm = fm }
1053
ensures { forall x. rmem_iv x i -> mem (round_x fm md x) result }
1054
= match i with
1055
| RSing a ->
1056
(* not `singleton`, renamed in `Fp_interval_gen` *)
1057
let x = round_a fm md a in
1058
{proof…} le_refl x; {qed}
1059
interval_o fm x x
1060
| RInter rl rh ->
1061
let l = match rl with
1062
| BInf -> minf
1063
| BLarge a | BStrict a -> round_a fm md a
1064
end in
1065
let h = match rh with
1066
| BInf -> pinf
1067
| BLarge a | BStrict a -> round_a fm md a
1068
end in
1069
{proof…}
1070
let lemma pt (x: real) : unit
1071
requires { rmem_iv x i }
1072
ensures { le_dz l (round_x fm md x) /\ le_dz (round_x fm md x) h }
1073
= minf_le fm (round_x fm md x); le_pinf fm (round_x fm md x);
1074
(match rl with
1075
| BInf -> ()
1076
| BLarge a | BStrict a ->
1077
round_f_le fm md (A.real a <. 0.0) (x <. 0.0) (Fin (A.real a)) (Fin x)
1078
end);
1079
match rh with
1080
| BInf -> ()
1081
| BLarge a | BStrict a ->
1082
round_f_le fm md (x <. 0.0) (A.real a <. 0.0) (Fin x) (Fin (A.real a))
1083
end in
1084
{qed}
1085
interval_o fm l h
1086
end
1087
Valid (340ms) (colibri2)
1088
let rec
of_real_u
(fm: format) (minf pinf: t) (md: mode) (l: rdom) : dom
1089
requires { fmt minf = fm /\ fmt pinf = fm /\ minf = minus_infinity fm /\ pinf = plus_infinity fm }
1090
ensures { result.fm = fm }
1091
ensures { forall x. rmem x l -> mem (round_x fm md x) result }
1092
variant { l }
1093
= match l with
1094
| Nil -> empty_dom fm
1095
| Cons i l' -> union fm (of_riv1 fm minf pinf md i) (of_real_u fm minf pinf md l')
1096
end

In the mode, or in any mode when it is unknown

  Valid (621ms) (cvc5)
1099
let
of_real_fwd
(fm: format) (minf pinf: t) (om: option mode) (l: rdom) : dom
1100
requires { fmt minf = fm /\ fmt pinf = fm /\ minf = minus_infinity fm /\ pinf = plus_infinity fm }
1101
ensures { result.fm = fm }
1102
ensures { forall md x. (om = None \/ om = Some md) -> rmem x l -> mem (round_x fm md x) result }
1103
= match om with
1104
| Some md -> of_real_u fm minf pinf md l
1105
| None ->
1106
let r1 = of_real_u fm minf pinf RNE l in
1107
let r2 = of_real_u fm minf pinf RNA l in
1108
let r3 = of_real_u fm minf pinf RTP l in
1109
let r4 = of_real_u fm minf pinf RTN l in
1110
let r5 = of_real_u fm minf pinf RTZ l in
1111
union fm r1 (union fm r2 (union fm r3 (union fm r4 r5)))
1112
end

to_fp of a real, backward

The reals whose rounding is in a float domain, by real_lo and real_hi in the format fm' with one more bit.

  Valid (41ms) (colibri2)
1118
let rec
app
(l1 l2: rdom) : rdom
1119
ensures { forall x. rmem x result <-> rmem x l1 \/ rmem x l2 }
1120
variant { l1 }
1121
= match l1 with Nil -> l2 | Cons i l -> Cons i (app l l2) end
1122
Valid (1.6s) (colibri2 23) (cvc4) (cvc5 4) (split_vc 3) (depth 3)
1123
let
real_iv
(fm fm': format) (c c': (t, t, t, t)) (md: mode) (a b: t) : rdom
1124
requires { widens fm fm' /\ consts_ok fm c /\ consts_ok fm' c' }
1125
requires { fmt a = fm /\ fmt b = fm /\ is_not_nan a /\ is_not_nan b }
1126
ensures { forall x. in_iv (round_x fm md x) a b -> rmem x result }
1127
= let (minf, pinf, nz, pz) = c in
1128
let (minf', pinf', _, _) = c' in
1129
let lo = real_lo fm fm' minf nz pz md a in
1130
let (hi, strict) = real_hi fm fm' pinf nz pz md b in
1131
if is_inf_f fm' minf' pinf' lo && le_diff_zero pinf' lo then Nil
1132
else if is_inf_f fm' minf' pinf' hi && le_diff_zero hi minf' then Nil
1133
else begin
1134
let rl = if is_inf_f fm' minf' pinf' lo then BInf else BLarge (to_a lo) in
1135
let rh = if is_inf_f fm' minf' pinf' hi then BInf
1136
else if strict then BStrict (to_a hi) else BLarge (to_a hi) in
1137
{proof…}
1138
let lemma pt (x: real) : unit
1139
requires { in_iv (round_x fm md x) a b }
1140
ensures { rmem_iv x (RInter rl rh) }
1141
= assert { le_dz a (round_f fm md (x <. 0.0) (Fin x)) };
1142
assert { le_dz (round_f fm md (x <. 0.0) (Fin x)) b };
1143
assert { ele (ext lo) (Fin x) };
1144
assert { if strict then Fin x <> ext hi /\ ele (Fin x) (ext hi)
1145
else ele (Fin x) (ext hi) };
1146
assert { rmem_lo x rl }; assert { rmem_hi x rh } in
1147
{qed}
1148
Cons (RInter rl rh) Nil
1149
end
1150
Valid (87ms) (cvc5)
1151
let rec
real_u
(fm fm': format) (c c': (t, t, t, t)) (md: mode) (l: list (t, t)) : rdom
1152
requires { widens fm fm' /\ consts_ok fm c /\ consts_ok fm' c' }
1153
requires { ok_u l /\ fmt_u fm l }
1154
ensures { forall x. mem_u (round_x fm md x) l -> rmem x result }
1155
variant { l }
1156
= match l with
1157
| Nil -> Nil
1158
| Cons (a, b) l' -> app (real_iv fm fm' c c' md a b) (real_u fm fm' c c' md l')
1159
end

In the mode, or in any mode when it is unknown; None when the format has no wider format

  Valid (1.2s) (cvc4)
1163
let
of_real_back
(fm: format) (om: option mode) (d: dom) : option rdom
1164
requires { d.fm = fm }
1165
ensures { match result with
1166
| Some l -> forall md x. (om = None \/ om = Some md) -> mem (round_x fm md x) d -> rmem x l
1167
| None -> true
1168
end }
1169
= match widen fm with
1170
| None -> None
1171
| Some fm' ->
1172
let c = consts fm in
1173
let c' = consts fm' in
1174
match om with
1175
| Some md -> Some (real_u fm fm' c c' md d.u)
1176
| None ->
1177
let r1 = real_u fm fm' c c' RNE d.u in
1178
let r2 = real_u fm fm' c c' RNA d.u in
1179
let r3 = real_u fm fm' c c' RTP d.u in
1180
let r4 = real_u fm fm' c c' RTN d.u in
1181
let r5 = real_u fm fm' c c' RTZ d.u in
1182
Some (app r1 (app r2 (app r3 (app r4 r5))))
1183
end
1184
end
1185
end