library colibrilib.fbin — module Implfp.IntfThe definitions of the symbols of Intf, and its axioms as lemmas for the clone at the end.
module Impl485use int.Int486use int.Power487use int.EuclideanDivision488use real.RealInfix489use real.FromInt490use real.Truncate491use option.Option492use colibrilib.fp.Widen493use colibrilib.fp.Ereal494use colibrilib.zarith.Zbit495use colibrilib.zbit.ZbitInt496use colibrilib.zarith.Z as Zarith497use real.Square as S498use Pow2r499use Format500use Float501use Round502Valid (23ms) (colibri2)503let format_of (x: t) : format504ensures { result = x.fmt }505= x.fmt506Valid (25ms) (colibri2)507let widen (fm: format) : option format508ensures { match result with509| None -> false510| Some fm' -> fm'.eb = fm.eb /\ fm'.sb = fm.sb + 1 end }511= Some { eb = fm.eb; sb = fm.sb + 1 }512
let predicate is_nan (x: t) = match x.value with NaN -> true | _ -> false end516predicate is_plus_infinity (x: t) = x.value = PlusInf517predicate is_minus_infinity (x: t) = x.value = MinusInf518let predicate is_zero (x: t) = match x.value with Finite _ k -> k = 0 | _ -> false end519let predicate is_positive (x: t) =520match x.value with Finite neg _ -> not neg | PlusInf -> true | _ -> false end521predicate is_subnormal (x: t) =522match x.value with Finite _ k -> 0 < k < binade x.fmt | _ -> false end523predicate is_normal (x: t) =524match x.value with Finite _ k -> binade x.fmt <= k | _ -> false end525526function not_a_number (fm: format) : t = mk fm NaN527function plus_infinity (fm: format) : t = mk fm PlusInf528function minus_infinity (fm: format) : t = mk fm MinusInf529
function index (x: t) : int =533match x.value with534| Finite neg k -> if neg then -1 - k else k535| PlusInf -> nb_sign x.fmt - 1536| MinusInf -> - nb_sign x.fmt537| NaN -> 0538end539540function of_index (fm: format) (i: int) : t =541if 0 <= i < nb_sign fm - 1 then mk fm (Finite false i)542else if - nb_sign fm < i < 0 then mk fm (Finite true (-1 - i))543else if i = nb_sign fm - 1 then mk fm PlusInf544else if i = - nb_sign fm then mk fm MinusInf545else mk fm NaN546547predicate le_dz (x y: t) =548not is_nan x /\ not is_nan y /\ x.fmt = y.fmt /\ index x <= index y549predicate lt_dz (x y: t) =550not is_nan x /\ not is_nan y /\ x.fmt = y.fmt /\ index x < index y551Valid (30ms) (colibri2 5) (split_vc) (depth 1)552let ghost nb_sign_ge (fm: format) : unit553ensures { 2 * binade fm + 1 <= nb_sign fm }554= {proof…}555binade_ge_2 fm;556assert { power 2 (fm.eb - 1) = 2 * power 2 (fm.eb - 2) /\ 1 <= power 2 (fm.eb - 2) };557assert { power 2 fm.eb = 2 * power 2 (fm.eb - 1) };558assert { 3 <= power 2 fm.eb - 1 };559assert { 3 * binade fm <= (power 2 fm.eb - 1) * binade fm }560{qed}561Valid (27ms) (colibri2)562let index_p (x: t) : int563requires { not is_nan x }564ensures { result = index x }565= match x.value with566| Finite neg k -> if neg then -1 - k else k567| PlusInf -> nb_sign_p x.fmt - 1568| MinusInf -> - nb_sign_p x.fmt569| NaN -> absurd570end571Valid (28ms) (colibri2)572let eq_format (a b: format) : bool573ensures { result <-> a = b }574= {proof…} if a.eb = b.eb && a.sb = b.sb then assert { format'eq a b }; {qed}575a.eb = b.eb && a.sb = b.sb576Valid (30ms) (colibri2)577let le_diff_zero (x y: t) : bool578ensures { result <-> le_dz x y }579= not (is_nan x) && not (is_nan y) && eq_format x.fmt y.fmt && index_p x <= index_p y580Valid (27ms) (colibri2)581let lt_diff_zero (x y: t) : bool582ensures { result <-> lt_dz x y }583= not (is_nan x) && not (is_nan y) && eq_format x.fmt y.fmt && index_p x < index_p y584Valid (38ms) (colibri2)585let ghost index_range (x: t) : unit586requires { not is_nan x }587ensures { - nb_sign x.fmt <= index x < nb_sign x.fmt }588= ()589Valid (1.6s) (colibri2) (cvc4 2) (split_vc 2) (depth 2)590let ghost of_index_range (fm: format) (i: int) : unit591requires { - nb_sign fm <= i < nb_sign fm }592ensures { not is_nan (of_index fm i) /\ index (of_index fm i) = i }593ensures { (of_index fm i).fmt = fm }594= ()595
Two floats are equal when their formats and values are
Valid (20ms) (colibri2)let ghost t_ext (x y: t) : unit598requires { x.fmt = y.fmt /\ x.value = y.value }599ensures { x = y }600= {proof…} assert { t'eq x y } {qed}601Valid (82ms) (colibri2)602let ghost index_inj (x: t) : unit603requires { not is_nan x }604ensures { of_index x.fmt (index x) = x }605= {proof…}606let i = index x in607of_index_range x.fmt i;608match x.value with609| Finite neg k -> if neg then assert { (of_index x.fmt i).value = Finite true k }610| _ -> ()611end;612t_ext (of_index x.fmt i) x613{qed}614Valid (27ms) (colibri2)615let ghost nan_unique (x: t) : unit616requires { is_nan x }617ensures { x = not_a_number x.fmt }618= {proof…} t_ext x (not_a_number x.fmt) {qed}619Valid (28ms) (colibri2)620let ghost plus_infinity_unique (x: t) : unit621requires { is_plus_infinity x }622ensures { x = plus_infinity x.fmt }623= {proof…} t_ext x (plus_infinity x.fmt) {qed}624Valid (27ms) (colibri2)625let ghost minus_infinity_unique (x: t) : unit626requires { is_minus_infinity x }627ensures { x = minus_infinity x.fmt }628= {proof…} t_ext x (minus_infinity x.fmt) {qed}629
The bits of a float of fm: the sign bit, then the eb bits of the biased exponent and the sb - 1 bits of the significand, that is the magnitude k. The magnitude nb_sign fm - 1 is the infinity, the larger ones are NaNs. Only the eb + sb lowest bits of b count.
function half_bits (fm: format) : int = power 2 (fm.eb + fm.sb - 1)638639function of_bits (fm: format) (b: int) : t =640let c = mod b (2 * half_bits fm) in641let neg = half_bits fm <= c in642let k = if neg then c - half_bits fm else c in643if k < nb_sign fm - 1 then mk fm (Finite neg k)644else if k = nb_sign fm - 1 then mk fm (if neg then MinusInf else PlusInf)645else mk fm NaN646
NaN is the quiet NaN with the sign bit
function to_bits (x: t) : int =649match x.value with650| Finite neg k -> if neg then half_bits x.fmt + k else k651| PlusInf -> nb_sign x.fmt - 1652| MinusInf -> half_bits x.fmt + nb_sign x.fmt - 1653| NaN -> half_bits x.fmt + nb_sign x.fmt - 1 + power 2 (x.fmt.sb - 2)654end655Valid (109ms) (colibri2)656let ghost half_bits_nb_sign (fm: format) : unit657ensures { half_bits fm = nb_sign fm - 1 + binade fm }658ensures { 2 * power 2 (fm.sb - 2) = binade fm }659= {proof…}660assert { half_bits fm = power 2 fm.eb * binade fm };661assert { binade fm = 2 * power 2 (fm.sb - 2) }662{qed}663Valid (62ms) (colibri2)664let ghost to_bits_range (x: t) : unit665ensures { 0 <= to_bits x < 2 * half_bits x.fmt }666= half_bits_nb_sign x.fmt667Valid (676ms) (colibri2)668let ghost of_to_bits (x: t) : unit669ensures { of_bits x.fmt (to_bits x) = x }670= {proof…}671let fm = x.fmt in672half_bits_nb_sign fm;673to_bits_range x;674assert { mod (to_bits x) (2 * half_bits fm) = to_bits x };675t_ext (of_bits fm (to_bits x)) x676{qed}677Valid (1.4s) (colibri2 3) (cvc4) (cvc5) (split_vc 2) (depth 2)678let ghost to_of_bits (fm: format) (b: int) : unit679requires { not is_nan (of_bits fm b) }680ensures { to_bits (of_bits fm b) = mod b (2 * half_bits fm) }681= half_bits_nb_sign fm;682{proof…}683let ghost c = mod b (2 * half_bits fm) in684let ghost k = if half_bits fm <= c then c - half_bits fm else c in685if k < nb_sign fm - 1 then686assert { (of_bits fm b).value = Finite (half_bits fm <= c) k }687else assert { k = nb_sign fm - 1 }688{qed}689Valid (81ms) (colibri2)690let of_bits_p (fm: format) (b: int) : t691ensures { result = of_bits fm b }692= let h = pow2_int (fm.eb + fm.sb - 1) in693let q = Zarith.fdiv b (2 * h) in694let c = b - q * (2 * h) in695{proof…}696assert { 0 <= c < 2 * h };697assert { b = q * (2 * h) + c };698assert { div b (2 * h) = q /\ mod b (2 * h) = c };699{qed}700let neg = h <= c in701let k = if neg then c - h else c in702let n1 = nb_sign_p fm - 1 in703if k < n1 then mk fm (Finite neg k)704else if k = n1 then mk fm (if neg then MinusInf else PlusInf)705else mk fm NaN706Valid (39ms) (colibri2)707let to_bits_p (x: t) : int708ensures { result = to_bits x }709= let fm = x.fmt in710let h = pow2_int (fm.eb + fm.sb - 1) in711match x.value with712| Finite neg k -> if neg then h + k else k713| PlusInf -> nb_sign_p fm - 1714| MinusInf -> h + nb_sign_p fm - 1715| NaN -> h + nb_sign_p fm - 1 + pow2_int (fm.sb - 2)716end717
predicate ieee_eq (x y: t) =721not is_nan x /\ not is_nan y /\ (is_zero x /\ is_zero y \/ index x = index y)722predicate ieee_lt (x y: t) =723not is_nan x /\ not is_nan y /\ not (is_zero x /\ is_zero y) /\ index x < index y724predicate ieee_le (x y: t) = ieee_lt x y \/ ieee_eq x y725Valid (43ms) (colibri2)726let ieee_eq_p (x y: t) : bool727ensures { result <-> ieee_eq x y }728= not (is_nan x) && not (is_nan y)729&& (is_zero x && is_zero y || index_p x = index_p y)730Valid (43ms) (colibri2)731let ieee_lt_p (x y: t) : bool732ensures { result <-> ieee_lt x y }733= not (is_nan x) && not (is_nan y) && not (is_zero x && is_zero y)734&& index_p x < index_p y735Valid (34ms) (colibri2)736let ieee_le_p (x y: t) : bool737ensures { result <-> ieee_le x y }738= ieee_lt_p x y || ieee_eq_p x y739
Valid (37ms) (colibri2)let function neg (x: t) : t =743match x.value with744| NaN -> x745| PlusInf -> mk x.fmt MinusInf746| MinusInf -> mk x.fmt PlusInf747| Finite b k -> mk x.fmt (Finite (not b) k)748end749Valid (1.1s) (colibri2)750let ghost index_neg (x: t) : unit751requires { not is_nan x }752ensures { not is_nan (neg x) /\ (neg x).fmt = x.fmt }753ensures { index (neg x) = -1 - index x }754ensures { is_finite x -> is_finite (neg x) }755= ()756Valid (34ms) (colibri2)757let function abs (x: t) : t =758match x.value with759| MinusInf -> mk x.fmt PlusInf760| Finite _ k -> mk x.fmt (Finite false k)761| _ -> x762end763764function min (x y: t) : t =765if is_nan x then y else if is_nan y then x766else if le_dz x y then x else y767function max (x y: t) : t =768if is_nan x then y else if is_nan y then x769else if le_dz x y then y else x770
function ext (x: t) : ereal =774match x.value with775| PlusInf -> PInf776| MinusInf -> MInf777| _ -> Fin (to_real x)778end779Valid (31ms) (colibri2)780let ghost vom_le (fm: format) (k l: int) : unit781requires { 0 <= k <= l }782ensures { vom fm k <=. vom fm l }783= {proof…} if k < l then vom_lt fm k l {qed}784Valid (23ms) (colibri2)785let ghost vom_pos (fm: format) (k: int) : unit786requires { 0 < k }787ensures { 0.0 <. vom fm k }788= {proof…} vom_zero fm; vom_lt fm 0 k {qed}789Valid (372ms) (colibri2 5) (split_vc) (depth 1)790let ghost ext_le (x y: t) : unit791requires { le_dz x y }792ensures { ele (ext x) (ext y) }793= {proof…}794let fm = x.fmt in795match x.value, y.value with796| Finite nx k, Finite ny l ->797vom_zero fm;798if not nx && not ny then vom_le fm k l799else if nx && ny then vom_le fm l k800else begin vom_le fm 0 k; vom_le fm 0 l end801| _ -> ()802end803{qed}804Valid (1.0s) (colibri2 7) (split_vc) (depth 1)805let ghost ext_lt (x y: t) : unit806requires { lt_dz x y /\ not (is_zero x /\ is_zero y) }807ensures { not ele (ext y) (ext x) }808= {proof…}809let fm = x.fmt in810vom_zero fm;811match x.value, y.value with812| Finite nx k, Finite ny l ->813if not nx && not ny then vom_lt fm k l814else if nx && ny then vom_lt fm l k815else begin816vom_le fm 0 k; vom_le fm 0 l;817if k > 0 then vom_pos fm k else if l > 0 then vom_pos fm l818end819| _ -> ()820end821{qed}822Valid (83ms) (colibri2)823let ghost ext_zero (x: t) : unit824requires { not is_nan x }825ensures { is_zero x <-> ext x = Fin 0.0 }826= {proof…}827vom_zero x.fmt;828match x.value with829| Finite _ k -> if k > 0 then vom_pos x.fmt k830| _ -> ()831end832{qed}833Valid (1.4s) (colibri2)834let ghost ext_neg (x: t) : unit835requires { not is_nan x }836ensures { ext (neg x) = eneg (ext x) }837= ()838
Valid (23ms) (colibri2)let lemma nan_unique_l (x: t)842requires { is_nan x } ensures { x = not_a_number x.fmt }843= nan_unique x844Valid (19ms) (colibri2)845let lemma plus_infinity_unique_l (x: t)846requires { is_plus_infinity x } ensures { x = plus_infinity x.fmt }847= plus_infinity_unique x848Valid (22ms) (colibri2)849let lemma minus_infinity_unique_l (x: t)850requires { is_minus_infinity x } ensures { x = minus_infinity x.fmt }851= minus_infinity_unique x852Valid (20ms) (colibri2)853let lemma index_inj_l (x: t)854requires { not is_nan x } ensures { of_index x.fmt (index x) = x }855= index_inj x856Valid (24ms) (colibri2)857let lemma nb_sign_ge_l (fm: format)858ensures { 2 * binade fm + 1 <= nb_sign fm }859= nb_sign_ge fm860Valid (25ms) (colibri2)861let lemma ext_le_l (x y: t)862requires { le_dz x y } ensures { ele (ext x) (ext y) }863= ext_le x y864Valid (26ms) (colibri2)865let lemma ext_lt_l (x y: t)866requires { lt_dz x y /\ not (is_zero x /\ is_zero y) }867ensures { not ele (ext y) (ext x) }868= ext_lt x y869Valid (25ms) (colibri2)870let lemma ext_zero_l (x: t)871requires { not is_nan x } ensures { is_zero x <-> ext x = Fin 0.0 }872= ext_zero x873
Valid (41ms) (colibri2)let ghost kdn_mono (fm: format) (r1 r2: real) : unit877requires { 0.0 <=. r1 <=. r2 }878ensures { kdn fm r1 <= kdn fm r2 }879= {proof…}880let k1 = kdn fm r1 in881let k2 = kdn fm r2 in882if k2 < k1 then vom_le fm (k2 + 1) k1883{qed}884Valid (63ms) (colibri2)885let ghost round_mag_range (fm: format) (m: mode) (r: real) : unit886requires { 0.0 <=. r }887ensures { 0 <= kdn fm r <= round_mag fm m r <= kdn fm r + 1 }888ensures { vom fm (kdn fm r) = r -> round_mag fm m r = kdn fm r }889ensures { m = RTN \/ m = RTZ -> round_mag fm m r = kdn fm r }890ensures { m = RTP -> vom fm (kdn fm r) <> r -> round_mag fm m r = kdn fm r + 1 }891= {proof…} let _ = kdn fm r in () {qed}892Valid (351ms) (colibri2)893let ghost round_mag_mono (fm: format) (m: mode) (r1 r2: real) : unit894requires { 0.0 <=. r1 <=. r2 }895ensures { round_mag fm m r1 <= round_mag fm m r2 }896= {proof…}897kdn_mono fm r1 r2; round_mag_range fm m r1; round_mag_range fm m r2;898let k1 = kdn fm r1 in899let k2 = kdn fm r2 in900if k1 = k2 then901if pure { vom fm k1 <> r1 } then assert { vom fm k2 <> r2 }902{qed}903Valid (33ms) (colibri2)904let ghost round_mag_exact (fm: format) (m: mode) (k: int) : unit905requires { 0 <= k }906ensures { round_mag fm m (vom fm k) = k }907= {proof…}908vom_lt fm k (k + 1); vom_zero fm; vom_le fm 0 k; kdn_unique fm k (vom fm k)909{qed}910
The magnitude of the result of of_mag, for k >= 1
function cmag (fm: format) (m: mode) (k: int) : int =913if k < nb_sign fm - 1 then k914else match m with RTN | RTZ -> nb_sign fm - 2 | _ -> nb_sign fm - 1 end915Valid (830ms) (colibri2 5) (cvc4 2) (split_vc) (depth 1)916let ghost of_mag_index (fm: format) (m: mode) (neg: bool) (k: int) : unit917requires { 1 <= k }918ensures { not is_nan (of_mag fm m neg k) /\ (of_mag fm m neg k).fmt = fm }919ensures { 1 <= cmag fm m k <= nb_sign fm - 1 }920ensures { index (of_mag fm m neg k) = if neg then -1 - cmag fm m k else cmag fm m k }921ensures { not is_zero (of_mag fm m neg k) }922ensures { is_positive (of_mag fm m neg k) <-> not neg }923ensures { cmag fm m k < nb_sign fm - 1 ->924to_real (of_mag fm m neg k) =925if neg then -. vom fm (cmag fm m k) else vom fm (cmag fm m k) }926ensures { cmag fm m k = nb_sign fm - 1 ->927ext (of_mag fm m neg k) = if neg then MInf else PInf }928= {proof…} nb_sign_ge fm {qed}929Valid (987ms) (cvc5)930let ghost round_fin_facts (fm: format) (m: mode) (z: bool) (r: real) : unit931ensures { not is_nan (round_fin fm m z r) /\ (round_fin fm m z r).fmt = fm }932ensures { is_zero (round_fin fm m z r) ->933(is_positive (round_fin fm m z r) <-> not z) }934= {proof…}935nb_sign_ge fm;936if pure { 0.0 <=. r } then begin937round_mag_range fm m r;938let k = round_mag fm m r in939if k <> 0 then of_mag_index fm m false k940end else begin941round_mag_range fm (mirror m) (-. r);942let k = round_mag fm (mirror m) (-. r) in943if k <> 0 then of_mag_index fm (mirror m) true k944end945{qed}946Valid (2.0s) (colibri2 18) (cvc4 2) (cvc5 5) (split_vc 8) (depth 4)947let ghost round_fin_le (fm: format) (m: mode) (z1 z2: bool) (r1 r2: real) : unit948requires { r1 <=. r2 }949requires { is_zero (round_fin fm m z1 r1) /\ is_zero (round_fin fm m z2 r2) -> z2 -> z1 }950ensures { le_dz (round_fin fm m z1 r1) (round_fin fm m z2 r2) }951= {proof…}952round_fin_facts fm m z1 r1; round_fin_facts fm m z2 r2;953nb_sign_ge fm;954if pure { 0.0 <=. r1 } then begin955round_mag_range fm m r1; round_mag_range fm m r2;956round_mag_mono fm m r1 r2;957let k1 = round_mag fm m r1 in958let k2 = round_mag fm m r2 in959if k1 >= 1 then begin960of_mag_index fm m false k1; of_mag_index fm m false k2961end else if k2 >= 1 then of_mag_index fm m false k2962end else if pure { 0.0 <=. r2 } then begin963round_mag_range fm (mirror m) (-. r1); round_mag_range fm m r2;964let k1 = round_mag fm (mirror m) (-. r1) in965let k2 = round_mag fm m r2 in966if k1 >= 1 then of_mag_index fm (mirror m) true k1;967if k2 >= 1 then of_mag_index fm m false k2968end else begin969round_mag_range fm (mirror m) (-. r1); round_mag_range fm (mirror m) (-. r2);970round_mag_mono fm (mirror m) (-. r2) (-. r1);971let k1 = round_mag fm (mirror m) (-. r1) in972let k2 = round_mag fm (mirror m) (-. r2) in973if k2 >= 1 then begin974of_mag_index fm (mirror m) true k1; of_mag_index fm (mirror m) true k2975end else if k1 >= 1 then of_mag_index fm (mirror m) true k1976end977{qed}978Valid (1.2s) (colibri2 5) (cvc5) (split_vc 2) (depth 2)979let ghost round_f_le (fm: format) (m: mode) (z1 z2: bool) (e1 e2: ereal) : unit980requires { ele e1 e2 }981requires { is_zero (round_f fm m z1 e1) /\ is_zero (round_f fm m z2 e2) -> z2 -> z1 }982ensures { le_dz (round_f fm m z1 e1) (round_f fm m z2 e2) }983= {proof…}984nb_sign_ge fm;985match e1, e2 with986| Fin r1, Fin r2 -> round_fin_le fm m z1 z2 r1 r2987| Fin r1, _ -> round_fin_facts fm m z1 r1988| _, Fin r2 -> round_fin_facts fm m z2 r2989| _ -> ()990end991{qed}992Valid (1.0s) (colibri2 10) (split_vc) (depth 1)993let ghost round_f_exact (m: mode) (x: t) : unit994requires { not is_nan x }995ensures { round_f x.fmt m (if is_positive x then false else true) (ext x) = x }996= {proof…}997let fm = x.fmt in998vom_zero fm;999match x.value with1000| Finite neg k ->1001if neg then begin1002if k = 0 then round_mag_exact fm m 01003else begin1004vom_pos fm k;1005assert { -. (-. vom fm k) = vom fm k };1006round_mag_exact fm (mirror m) k1007end1008end else begin1009round_mag_exact fm m k;1010if k > 0 then vom_pos fm k;1011assert { ext x = Fin (vom fm k) /\ 0.0 <=. vom fm k }1012end;1013t_ext (round_f fm m (if is_positive x then false else true) (ext x)) x1014| _ -> t_ext (round_f fm m (if is_positive x then false else true) (ext x)) x1015end1016{qed}1017Valid (1.0s) (colibri2 7) (cvc4) (cvc5 3) (split_vc 4) (depth 3)1018let ghost round_fin_down (fm: format) (z: bool) (r: real) : unit1019ensures { ele (ext (round_fin fm RTN z r)) (Fin r) }1020= {proof…}1021vom_zero fm; nb_sign_ge fm;1022if pure { 0.0 <=. r } then begin1023round_mag_range fm RTN r;1024let k = round_mag fm RTN r in1025if k <> 0 then begin1026of_mag_index fm RTN false k; vom_le fm (cmag fm RTN k) k1027end1028end else begin1029round_mag_range fm RTP (-. r);1030let k = round_mag fm RTP (-. r) in1031assert { k <> 0 };1032of_mag_index fm RTP true k;1033if k < nb_sign fm - 1 then1034assert { -. r <=. vom fm k by vom fm (kdn fm (-. r)) <> -. r -> k = kdn fm (-. r) + 1 }1035end1036{qed}1037Valid (2.9s) (colibri2 6) (cvc5 3) (split_vc 3) (depth 2)1038let ghost round_fin_up (fm: format) (z: bool) (r: real) : unit1039ensures { ele (Fin r) (ext (round_fin fm RTP z r)) }1040= {proof…}1041vom_zero fm; nb_sign_ge fm;1042if pure { 0.0 <=. r } then begin1043round_mag_range fm RTP r;1044let k = round_mag fm RTP r in1045if k <> 0 then begin1046of_mag_index fm RTP false k;1047if k < nb_sign fm - 1 then1048assert { r <=. vom fm k by vom fm (kdn fm r) <> r -> k = kdn fm r + 1 }1049end1050end else begin1051round_mag_range fm RTN (-. r);1052let k = round_mag fm RTN (-. r) in1053if k <> 0 then begin1054of_mag_index fm RTN true k; vom_le fm (cmag fm RTN k) k1055end1056end1057{qed}1058
predicate widens (fm fm': format) = fm'.eb = fm.eb /\ fm'.sb = fm.sb + 11062Valid (357ms) (colibri2 13) (split_vc) (depth 1)1063let ghost vom_widen (fm fm': format) (k: int) : unit1064requires { widens fm fm' /\ 0 <= k }1065ensures { vom fm' (2 * k) = vom fm k }1066ensures { vom fm' (2 * k + 1) = (vom fm k +. vom fm (k + 1)) /. 2.0 }1067= {proof…}1068vom_dec fm k;1069let u = uexp fm k in1070let s = sig fm k in1071assert { binade fm' = 2 * binade fm };1072assert { qmin fm' = qmin fm - 1 };1073assert { u - 1 - qmin fm' = u - qmin fm };1074assert { (u - qmin fm) * binade fm' = 2 * ((u - qmin fm) * binade fm) };1075assert { 2 * k = (u - 1 - qmin fm') * binade fm' + 2 * s };1076assert { 2 * k + 1 = (u - 1 - qmin fm') * binade fm' + (2 * s + 1) };1077vom_s fm' (u - 1) (2 * s); vom_s fm' (u - 1) (2 * s + 1);1078pow2r_succ (u - 1)1079{qed}1080Valid (1.6s) (colibri2 15) (cvc4 2) (cvc5 4) (split_vc 2) (depth 2)1081let ghost ext_widen (fm fm': format) (i: int) : unit1082requires { widens fm fm' /\ - nb_sign fm <= i < nb_sign fm }1083ensures { ext (of_index fm' (if 0 <= i then 2 * i else 2 * i + 1)) = ext (of_index fm i) }1084= {proof…}1085assert { binade fm' = 2 * binade fm };1086assert { (power 2 fm'.eb - 1) * binade fm' = 2 * ((power 2 fm.eb - 1) * binade fm) };1087assert { nb_sign fm' = 2 * nb_sign fm - 1 };1088if 0 <= i then begin1089if i = nb_sign fm - 1 then begin1090assert { 2 * i = nb_sign fm' - 1 };1091assert { of_index fm' (2 * i) = mk fm' PlusInf };1092assert { of_index fm i = mk fm PlusInf };1093assert { ext (of_index fm' (if 0 <= i then 2 * i else 2 * i + 1)) = ext (of_index fm i) }1094end else begin1095vom_widen fm fm' i;1096assert { of_index fm' (2 * i) = mk fm' (Finite false (2 * i)) };1097assert { of_index fm i = mk fm (Finite false i) };1098assert { ext (of_index fm' (if 0 <= i then 2 * i else 2 * i + 1)) = ext (of_index fm i) }1099end1100end else begin1101if i = - nb_sign fm then begin1102assert { 2 * i + 1 = - nb_sign fm' };1103assert { of_index fm' (2 * i + 1) = mk fm' MinusInf };1104assert { of_index fm i = mk fm MinusInf };1105assert { ext (of_index fm' (if 0 <= i then 2 * i else 2 * i + 1)) = ext (of_index fm i) }1106end else begin1107vom_widen fm fm' (-1 - i);1108assert { of_index fm' (2 * i + 1) = mk fm' (Finite true (2 * (-1 - i))) };1109assert { of_index fm i = mk fm (Finite true (-1 - i)) };1110assert { ext (of_index fm' (if 0 <= i then 2 * i else 2 * i + 1)) = ext (of_index fm i) }1111end1112end1113{qed}1114Valid (38ms) (colibri2)1115let ghost nb_sign_widen (fm fm': format) : unit1116requires { widens fm fm' }1117ensures { nb_sign fm' = 2 * nb_sign fm - 1 }1118= {proof…}1119assert { binade fm' = 2 * binade fm };1120assert { (power 2 fm'.eb - 1) * binade fm' = 2 * ((power 2 fm.eb - 1) * binade fm) }1121{qed}1122
The rounding of a negative real is at most 0
Valid (1.2s) (cvc5)let ghost round_fin_neg_le (fm: format) (m: mode) (z: bool) (r: real) : unit1125requires { r <. 0.0 }1126ensures { ele (ext (round_fin fm m z r)) (Fin 0.0) }1127= {proof…}1128vom_zero fm; nb_sign_ge fm;1129round_mag_range fm (mirror m) (-. r);1130let k = round_mag fm (mirror m) (-. r) in1131if k <> 0 then begin1132of_mag_index fm (mirror m) true k;1133vom_le fm 0 (cmag fm (mirror m) k)1134end1135{qed}1136
Rounding toward zero a real r >= 0 gives at most r
Valid (1.4s) (cvc4)let ghost round_fin_pos_down (fm: format) (m: mode) (z: bool) (r: real) : unit1139requires { 0.0 <=. r /\ (m = RTN \/ m = RTZ) }1140ensures { ele (ext (round_fin fm m z r)) (Fin r) }1141= {proof…}1142vom_zero fm; nb_sign_ge fm;1143round_mag_range fm m r;1144let k = round_mag fm m r in1145if k <> 0 then begin1146of_mag_index fm m false k; vom_le fm (cmag fm m k) k1147end1148{qed}1149
Below a float b (not –0), the rounding is at most b
Valid (55ms) (colibri2)let ghost round_le_of (fm: format) (m: mode) (z: bool) (r: real) (b: t) : unit1152requires { not is_nan b /\ b.fmt = fm /\ index b <> -1 /\ ele (Fin r) (ext b) }1153ensures { le_dz (round_fin fm m z r) b }1154= {proof…}1155round_f_exact m b;1156round_fin_facts fm m z r;1157let zb = if is_positive b then false else true in1158match ext b with1159| Fin rb -> round_fin_le fm m z zb r rb1160| _ -> index_range (round_fin fm m z r)1161end1162{qed}1163Valid (3.7s) (colibri2 68) (cvc4 4) (cvc5 24) (split_vc 10) (depth 4)1164let ghost round_f_ge_thr (fm fm': format) (m: mode) (z: bool) (e: ereal) (a: t) : unit1165requires { widens fm fm' /\ a.fmt = fm /\ not is_nan a /\ not is_minus_infinity a }1166requires { index a <> 0 /\ le_dz a (round_f fm m z e) }1167ensures { ele (ext (of_index fm' (windex (index a) + lo_off m (index a)))) e }1168= {proof…}1169let i = index a in1170nb_sign_ge fm; nb_sign_widen fm fm'; index_range a; vom_zero fm;1171match e with1172| PInf -> ()1173| MInf -> ()1174| Fin r ->1175let res = round_fin fm m z r in1176round_fin_facts fm m z r;1177ext_le a res;1178let b = of_index fm (i - 1) in1179of_index_range fm (i - 1);1180ext_widen fm fm' i; ext_widen fm fm' (i - 1);1181assert { windex i - 2 = windex (i - 1) };1182match m with1183| RTN -> round_fin_down fm z r1184| RTP ->1185if pure { not ele (ext b) (Fin r) } then round_le_of fm m z r b1186| RTZ ->1187if 0 <= i then begin1188if pure { 0.0 <=. r } then round_fin_pos_down fm m z r1189else begin1190round_fin_neg_le fm m z r;1191match a.value with Finite _ k -> vom_pos fm k | _ -> () end1192end1193end else1194if pure { not ele (ext b) (Fin r) } then round_le_of fm m z r b1195| RNE | RNA ->1196if 0 <= i then begin1197vom_widen fm fm' (i - 1);1198assert { of_index fm' (windex i - 1) = mk fm' (Finite false (2 * (i - 1) + 1)) };1199let mid = (vom fm (i - 1) +. vom fm i) /. 2.0 in1200assert { windex i + lo_off m i = 2 * (i - 1) + 1 };1201assert { ext (of_index fm' (2 * (i - 1) + 1)) = Fin mid };1202if pure { r <. mid } then begin1203if pure { not ele (ext b) (Fin r) } then begin1204round_le_of fm m z r b; assert { index res <= i - 1 }1205end else begin1206assert { ext b = Fin (vom fm (i - 1)) };1207vom_lt fm (i - 1) i;1208vom_le fm 0 (i - 1);1209assert { 0.0 <=. vom fm (i - 1) <=. r <. vom fm i };1210kdn_unique fm (i - 1) r;1211assert { round_mag fm m r = i - 1 };1212if i - 1 <> 0 then of_mag_index fm m false (i - 1);1213assert { index res <= i - 1 }1214end1215end;1216assert { mid <=. r }1217end else begin1218let ka = -1 - i in1219vom_widen fm fm' ka;1220assert { of_index fm' (windex i - 1) = mk fm' (Finite true (2 * ka + 1)) };1221let mid = (vom fm ka +. vom fm (ka + 1)) /. 2.0 in1222assert { windex i + lo_off m i = 2 * i };1223assert { ext (of_index fm' (2 * i)) = Fin (-. mid) };1224if pure { r <. -. mid } then begin1225vom_lt fm ka (ka + 1); vom_le fm 0 ka;1226assert { vom fm ka <. mid <. -. r };1227kdn_unique fm ka (vom fm ka);1228kdn_mono fm (vom fm ka) (-. r);1229round_mag_range fm (mirror m) (-. r);1230assert { mirror m = m };1231let k = round_mag fm (mirror m) (-. r) in1232assert { ka + 1 <= k };1233of_mag_index fm (mirror m) true k;1234assert { ka + 1 <= nb_sign fm - 1 };1235assert { cmag fm (mirror m) k = (if k < nb_sign fm - 1 then k else nb_sign fm - 1) };1236assert { cmag fm (mirror m) k >= ka + 1 };1237assert { index res <= i - 1 }1238end;1239assert { -. mid <=. r }1240end1241end1242end1243{qed}1244Valid (1.0s) (cvc4)1245let ghost neg_of_mag (fm: format) (m: mode) (ng: bool) (k: int) : unit1246requires { 1 <= k }1247ensures { neg (of_mag fm m ng k) = of_mag fm m (not ng) k }1248= {proof…}1249nb_sign_ge fm;1250t_ext (neg (of_mag fm m ng k)) (of_mag fm m (not ng) k)1251{qed}1252Valid (1.6s) (colibri2 15) (cvc5 2) (split_vc 4) (depth 3)1253let ghost round_f_neg (fm: format) (m: mode) (z: bool) (e: ereal) : unit1254ensures { round_f fm m z (eneg e) = neg (round_f fm (mirror m) (not z) e) }1255= {proof…}1256nb_sign_ge fm; vom_zero fm;1257assert { mirror (mirror m) = m };1258match e with1259| Fin r ->1260let lhs = round_fin fm m z (-. r) in1261let rhs = neg (round_fin fm (mirror m) (not z) r) in1262if pure { 0.0 <. r } then begin1263let k = round_mag fm (mirror m) r in1264round_mag_range fm (mirror m) r;1265if k <> 0 then neg_of_mag fm (mirror m) false k1266end else if pure { r <. 0.0 } then begin1267let k = round_mag fm m (-. r) in1268round_mag_range fm m (-. r);1269if k <> 0 then neg_of_mag fm m true k1270end else begin1271round_mag_exact fm m 0; round_mag_exact fm (mirror m) 0;1272assert { -. r = 0.0 /\ r = 0.0 }1273end;1274t_ext lhs rhs1275| PInf -> t_ext (round_f fm m z (eneg e)) (neg (round_f fm (mirror m) (not z) e))1276| MInf -> t_ext (round_f fm m z (eneg e)) (neg (round_f fm (mirror m) (not z) e))1277end1278{qed}1279Valid (1.5s) (cvc4)1280let ghost of_index_neg (fm: format) (i: int) : unit1281requires { - nb_sign fm <= i < nb_sign fm }1282ensures { of_index fm (-1 - i) = neg (of_index fm i) }1283= {proof…} t_ext (of_index fm (-1 - i)) (neg (of_index fm i)) {qed}1284Valid (2.9s) (colibri2 12) (cvc4 3) (cvc5 4) (split_vc 5) (depth 2)1285let ghost round_f_le_thr (fm fm': format) (m: mode) (z: bool) (e: ereal) (b: t) : unit1286requires { widens fm fm' /\ b.fmt = fm /\ not is_nan b /\ not is_plus_infinity b }1287requires { index b <> -1 /\ le_dz (round_f fm m z e) b }1288ensures { ele e (ext (of_index fm' (windex (index b) + hi_off m (index b)))) }1289= {proof…}1290let j = index b in1291let m' = mirror m in1292assert { mirror m' = m };1293round_f_neg fm m' (not z) e;1294let x = round_f fm m z e in1295match e with Fin r -> round_fin_facts fm m z r | _ -> () end;1296assert { round_f fm m' (not z) (eneg e) = neg x };1297index_neg b; index_neg x;1298assert { le_dz (neg b) (neg x) };1299round_f_ge_thr fm fm' m' (not z) (eneg e) (neg b);1300let w = windex j + hi_off m j in1301assert { windex (-1 - j) + lo_off m' (-1 - j) = -1 - w };1302nb_sign_widen fm fm'; index_range b; nb_sign_ge fm;1303of_index_neg fm' w;1304ext_neg (of_index fm' w);1305assert { index (neg b) = -1 - j };1306assert { ele (eneg (ext (of_index fm' w))) (eneg e) }1307{qed}1308Valid (24ms) (colibri2)1309let lemma round_f_ge_thr_l (fm fm': format) (m: mode) (z: bool) (e: ereal) (a: t)1310requires { widens fm fm' /\ a.fmt = fm /\ not is_nan a /\ not is_minus_infinity a }1311requires { index a <> 0 /\ le_dz a (round_f fm m z e) }1312ensures { ele (ext (of_index fm' (windex (index a) + lo_off m (index a)))) e }1313= round_f_ge_thr fm fm' m z e a1314Valid (25ms) (colibri2)1315let lemma round_f_le_thr_l (fm fm': format) (m: mode) (z: bool) (e: ereal) (b: t)1316requires { widens fm fm' /\ b.fmt = fm /\ not is_nan b /\ not is_plus_infinity b }1317requires { index b <> -1 /\ le_dz (round_f fm m z e) b }1318ensures { ele e (ext (of_index fm' (windex (index b) + hi_off m (index b)))) }1319= round_f_le_thr fm fm' m z e b1320Valid (26ms) (colibri2)1321let lemma round_f_le_l (fm: format) (m: mode) (z1 z2: bool) (e1 e2: ereal)1322requires { ele e1 e2 }1323requires { is_zero (round_f fm m z1 e1) /\ is_zero (round_f fm m z2 e2) -> z2 -> z1 }1324ensures { le_dz (round_f fm m z1 e1) (round_f fm m z2 e2) }1325= round_f_le fm m z1 z2 e1 e21326Valid (29ms) (colibri2)1327let lemma round_f_exact_l (m: mode) (x: t)1328requires { not is_nan x }1329ensures { round_f x.fmt m (if is_positive x then false else true) (ext x) = x }1330= round_f_exact m x1331
The magnitude of the integer n, 1 <= n, scaled by 2^j below 2 binade: the significand n 2^j with the ulp 2^-j
Valid (383ms) (colibri2 19) (cvc5) (split_vc 5) (depth 3)let rec ghost mag_of_int (fm: format) (n j: int) : int1335requires { 1 <= n /\ 0 <= j /\ n * power 2 j < 2 * binade fm }1336ensures { 0 <= result /\ vom fm result = from_int n }1337variant { fm.sb - j }1338= {proof…}1339binade_ge_2 fm;1340let s = n * power 2 j in1341assert { power 2 j <= s };1342if binade fm <= s then begin1343assert { j < fm.sb by power 2 j < power 2 fm.sb = 2 * binade fm };1344assert { power 2 (fm.eb - 1) >= 1 };1345assert { qmin fm <= - j };1346vom_s fm (- j) s;1347pow2r_add j (- j); pow2r_int j;1348assert { pow2r j *. pow2r (- j) = 1.0 by pow2r 0 = 1.0 };1349assert { from_int s = from_int n *. pow2r j };1350assert { from_int s *. pow2r (- j) = from_int n *. (pow2r j *. pow2r (- j)) };1351(- j - qmin fm) * binade fm + s1352end else begin1353assert { power 2 (j + 1) = 2 * power 2 j };1354assert { n * power 2 (j + 1) = 2 * s };1355mag_of_int fm n (j + 1)1356end1357{qed}1358
The integers of magnitude at most 2^sb and at most the largest finite float are floats
Valid (788ms) (colibri2 15) (cvc5) (split_vc 3) (depth 3)let ghost int_exact (fm: format) (i: int) : t1362requires { - power 2 fm.sb <= i <= power 2 fm.sb }1363requires { -. to_real (of_index fm (nb_sign fm - 2)) <=. from_int i <=.1364to_real (of_index fm (nb_sign fm - 2)) }1365ensures { result.fmt = fm /\ not is_nan result /\ ext result = Fin (from_int i) }1366= {proof…}1367nb_sign_ge fm; binade_ge_2 fm;1368let mx = nb_sign fm - 2 in1369assert { to_real (of_index fm mx) = vom fm mx };1370let n = if i < 0 then - i else i in1371assert { from_int n <=. vom fm mx };1372let k =1373if n = 0 then begin vom_zero fm; 0 end1374else if n < power 2 fm.sb then begin1375assert { power 2 0 = 1 }; mag_of_int fm n 0 end1376else begin1377assert { power 2 fm.sb = 2 * binade fm };1378assert { power 2 (fm.eb - 1) >= 1 };1379vom_s fm 1 (binade fm);1380assert { pow2r 1 = 2.0 };1381(1 - qmin fm) * binade fm + binade fm1382end in1383if mx < k then begin vom_lt fm mx k; absurd end;1384let x = mk fm (Finite (i < 0) k) in1385assert { to_real x = from_int i };1386x1387{qed}1388
The magnitude of the dyadic s 2^u, 1 <= s < 2 binade, normalized by shifting s left
Valid (210ms) (colibri2)let rec ghost mag_of_dy (fm: format) (s u: int) : int1392requires { 1 <= s < 2 * binade fm /\ qmin fm <= u }1393ensures { 0 <= result /\ vom fm result = from_int s *. pow2r u }1394variant { u - qmin fm }1395= {proof…}1396binade_ge_2 fm;1397if binade fm <= s || u = qmin fm then begin1398vom_s fm u s;1399(u - qmin fm) * binade fm + s1400end else begin1401pow2r_succ (u - 1);1402assert { from_int (2 * s) *. pow2r (u - 1) = from_int s *. pow2r u };1403mag_of_dy fm (2 * s) (u - 1)1404end1405{qed}1406
The magnitude of the infinity is at 2^(bias + 1)
Valid (99ms) (colibri2)let ghost vom_inf (fm: format) : unit1409ensures { vom fm (nb_sign fm - 1) = pow2r (bias fm + 1) }1410= {proof…}1411binade_ge_2 fm;1412let b = binade fm in1413let u = power 2 fm.eb - 2 + qmin fm in1414assert { power 2 fm.eb = 2 * power 2 (fm.eb - 1) };1415assert { power 2 (fm.eb - 1) >= 2 by power 2 (fm.eb - 1) = 2 * power 2 (fm.eb - 2) /\ power 2 (fm.eb - 2) >= 1 };1416assert { nb_sign fm - 1 = (u - qmin fm) * b + b };1417vom_s fm u b;1418pow2r_int (fm.sb - 1); pow2r_add (fm.sb - 1) u;1419assert { fm.sb - 1 + u = bias fm + 1 }1420{qed}1421
A finite float is a float of the wider formats
Valid (790ms) (colibri2 14) (cvc5 2) (split_vc) (depth 1)let ghost widen_exact (fm': format) (x: t) : t1424requires { x.fmt.eb <= fm'.eb /\ x.fmt.sb <= fm'.sb }1425requires { not is_nan x /\ not is_plus_infinity x /\ not is_minus_infinity x }1426ensures { result.fmt = fm' /\ not is_nan result /\ ext result = ext x }1427= {proof…}1428let fm = x.fmt in1429match x.value with1430| Finite ng k ->1431vom_zero fm; vom_zero fm'; nb_sign_ge fm'; binade_ge_2 fm;1432if k = 0 then mk fm' (Finite ng 0)1433else begin1434vom_dec fm k; vom_pos fm k;1435let s = sig fm k in1436let u = uexp fm k in1437pow2r_pos u;1438assert { 1 <= s by from_int s *. pow2r u >. 0.0 };1439assert { power 2 (fm.sb - 1) <= power 2 (fm'.sb - 1) };1440assert { power 2 (fm.eb - 1) <= power 2 (fm'.eb - 1) };1441assert { qmin fm' <= qmin fm };1442let k' = mag_of_dy fm' s u in1443vom_lt fm k (nb_sign fm - 1); vom_inf fm; vom_inf fm';1444pow2r_le (bias fm + 1) (bias fm' + 1);1445if k' >= nb_sign fm' - 1 then begin vom_le fm' (nb_sign fm' - 1) k'; absurd end;1446let y = mk fm' (Finite ng k') in1447assert { to_real y = to_real x };1448y1449end1450| _ -> absurd1451end1452{qed}1453Valid (629ms) (colibri2)1454let lemma round_f_facts_l (fm: format) (m: mode) (z: bool) (e: ereal)1455ensures { not is_nan (round_f fm m z e) /\ (round_f fm m z e).fmt = fm }1456ensures { is_zero (round_f fm m z e) -> (is_positive (round_f fm m z e) <-> not z) }1457= match e with Fin r -> round_fin_facts fm m z r | _ -> () end1458Valid (34ms) (colibri2)1459let lemma round_f_down_l (fm: format) (z: bool) (e: ereal)1460ensures { ele (ext (round_f fm RTN z e)) e }1461= match e with Fin r -> round_fin_down fm z r | _ -> () end1462Valid (44ms) (colibri2)1463let lemma round_f_up_l (fm: format) (z: bool) (e: ereal)1464ensures { ele e (ext (round_f fm RTP z e)) }1465= match e with Fin r -> round_fin_up fm z r | _ -> () end1466Valid (1.1s) (cvc5)1467let lemma round_f_fin_zero_l (fm: format) (m: mode) (z: bool)1468ensures { is_zero (round_f fm m z (Fin 0.0)) }1469= vom_zero fm; round_mag_exact fm m 01470Valid (25ms) (colibri2)1471let lemma ext_widen_l (fm fm': format) (i: int)1472requires { widens fm fm' /\ - nb_sign fm <= i < nb_sign fm }1473ensures { ext (of_index fm' (if 0 <= i then 2 * i else 2 * i + 1)) = ext (of_index fm i) }1474= ext_widen fm fm' i1475
Valid (56ms) (colibri2)let ghost finite_sign (x: t) : unit1479ensures { match x.value with1480| Finite ng k ->1481(k = 0 -> to_real x = 0.0) /\1482(0 < k -> (ng -> to_real x <. 0.0) /\ (not ng -> 0.0 <. to_real x))1483| _ -> true end }1484= {proof…}1485vom_zero x.fmt;1486match x.value with Finite _ k -> if 0 < k then vom_pos x.fmt k | _ -> () end1487{qed}1488
The sign of a zero sum (IEEE 754 §6.3)
function add_zneg (m: mode) (x y: t) : bool =1491if is_positive x <-> is_positive y then (if is_positive x then false else true)1492else (if m = RTN then true else false)14931494function fp_add (m: mode) (x y: t) : t =1495if is_nan x \/ is_nan y \/ opposite (ext x) (ext y) then not_a_number x.fmt1496else round_f x.fmt m (add_zneg m x y) (eadd (ext x) (ext y))1497Valid (825ms) (colibri2)1498let add (m: mode) (x y: t) : t1499ensures { x.fmt = y.fmt -> result = fp_add m x y }1500= let fm = x.fmt in1501if not (eq_format fm y.fmt) then mk fm NaN else1502match x.value, y.value with1503| NaN, _ | _, NaN -> mk fm NaN1504| PlusInf, MinusInf | MinusInf, PlusInf -> mk fm NaN1505| PlusInf, _ | _, PlusInf -> mk fm PlusInf1506| MinusInf, _ | _, MinusInf -> mk fm MinusInf1507| Finite _ _, Finite _ _ ->1508let rtn = match m with RTN -> true | _ -> false end in1509let z = if is_positive x then (if is_positive y then false else rtn)1510else (if is_positive y then rtn else true) in1511round_d fm m z (dadd (to_dyadic x) (to_dyadic y))1512end15131514predicate is_infinity (x: t) = is_plus_infinity x \/ is_minus_infinity x1515
The sign of a product (IEEE 754 §6.3)
function mul_zneg (x y: t) : bool =1518if is_positive x <-> is_positive y then false else true15191520function fp_mul (m: mode) (x y: t) : t =1521if is_nan x \/ is_nan y \/ (is_zero x /\ is_infinity y)1522\/ (is_infinity x /\ is_zero y) then not_a_number x.fmt1523else round_f x.fmt m (mul_zneg x y) (emul (ext x) (ext y))1524Valid (1.4s) (colibri2 33) (cvc5 2) (split_vc 3) (depth 3)1525let mul (m: mode) (x y: t) : t1526ensures { x.fmt = y.fmt -> result = fp_mul m x y }1527= let fm = x.fmt in1528if not (eq_format fm y.fmt) then mk fm NaN else1529let z = if is_positive x then not (is_positive y) else is_positive y in1530let inf = if z then MinusInf else PlusInf in1531{proof…} finite_sign x; finite_sign y; {qed}1532match x.value, y.value with1533| NaN, _ | _, NaN -> mk fm NaN1534| Finite _ k, (PlusInf | MinusInf) | (PlusInf | MinusInf), Finite _ k ->1535if k = 0 then mk fm NaN else mk fm inf1536| (PlusInf | MinusInf), (PlusInf | MinusInf) -> mk fm inf1537| Finite _ _, Finite _ _ -> round_d fm m z (dmul (to_dyadic x) (to_dyadic y))1538end15391540function fp_convert (fm: format) (m: mode) (x: t) : t =1541if is_nan x then not_a_number fm1542else round_f fm m (if is_positive x then false else true) (ext x)1543Valid (40ms) (colibri2)1544let convert (fm: format) (m: mode) (x: t) : t1545ensures { result = fp_convert fm m x }1546= match x.value with1547| NaN -> mk fm NaN1548| PlusInf -> mk fm PlusInf1549| MinusInf -> mk fm MinusInf1550| Finite _ _ -> round_d fm m (not (is_positive x)) (to_dyadic x)1551end1552
The rounding of a real to an integer in the mode
function round_int (m: mode) (r: real) : int =1557let f = Truncate.floor r in1558let d = r -. from_int f in1559match m with1560| RTN -> f1561| RTP -> if d = 0.0 then f else f + 11562| RTZ -> if 0.0 <=. r \/ d = 0.0 then f else f + 11563| RNE -> if d <. 0.5 then f else if 0.5 <. d then f + 11564else if mod f 2 = 0 then f else f + 11565| RNA -> if d <. 0.5 then f else if 0.5 <. d then f + 11566else if 0.0 <=. r then f + 1 else f1567end1568Valid (43ms) (colibri2)1569let ghost floor_unique (r: real) (n: int) : unit1570requires { from_int n <=. r <. from_int n +. 1.0 }1571ensures { Truncate.floor r = n }1572= {proof…}1573assert { n <= Truncate.floor r by Truncate.floor (from_int n) = n };1574assert { Truncate.floor r < n + 1 by from_int (Truncate.floor r) <=. r }1575{qed}1576Valid (106ms) (cvc5)1577let ghost round_int_monotonic (m: mode) (x y: real) : unit1578requires { x <=. y }1579ensures { round_int m x <= round_int m y }1580= {proof…}1581let fx = Truncate.floor x in1582let fy = Truncate.floor y in1583assert { fx <= fy };1584if fx = fy then begin1585if fx >= 0 then assert { 0.0 <=. x }1586else assert { y <. 0.0 by from_int fy +. 1.0 <=. 0.0 }1587end1588{qed}1589Valid (33ms) (colibri2)1590let lemma round_int_monotonic_l (m: mode) (x y: real)1591requires { x <=. y }1592ensures { round_int m x <= round_int m y }1593= round_int_monotonic m x y1594
The rounding to an integer of a dyadic number
Valid (1.1s) (colibri2 29) (split_vc) (depth 1)let round_int_d (m: mode) (d: dyadic) : int1597ensures { result = round_int m (dval d) }1598= if d.de >= 0 then begin1599{proof…}1600lsl_mul d.dm d.de; pow2r_int d.de;1601assert { dval d = from_int (d.dm * power 2 d.de) };1602floor_unique (dval d) (d.dm * power 2 d.de);1603{qed}1604lsl_int d.dm d.de1605end else begin1606let sh = - d.de in1607let pw = Round.pow2_int sh in1608let f = asr_int d.dm sh in1609let rem = d.dm - f * pw in1610{proof…}1611asr_div d.dm sh;1612assert { 0 <= rem < pw /\ d.dm = f * pw + rem };1613let ghost c = pure { pow2r d.de } in1614pow2r_add sh d.de; pow2r_int sh; pow2r_pos d.de;1615assert { from_int pw *. c = 1.0 };1616assert { from_int d.dm = from_int f *. from_int pw +. from_int rem };1617assert { dval d = from_int f *. (from_int pw *. c) +. from_int rem *. c };1618assert { dval d = from_int f +. from_int rem *. c };1619scale_cmp 0 rem c; scale_cmp rem pw c;1620floor_unique (dval d) f;1621assert { dval d -. from_int f = from_int rem *. c };1622assert { rem = 0 <-> from_int rem *. c = 0.0 };1623assert { 0.0 <=. dval d <-> 0 <= d.dm by1624(0 <= d.dm -> 0 <= f) /\ (d.dm < 0 -> f < 0) };1625{qed}1626match m with1627| RTN -> f1628| RTP -> if rem = 0 then f else f + 11629| RTZ -> if d.dm >= 0 || rem = 0 then f else f + 11630| RNE | RNA ->1631let h = Round.pow2_int (sh - 1) in1632{proof…}1633assert { pw = 2 * h };1634assert { 0.5 = from_int h *. c };1635scale_cmp rem h c;1636{qed}1637if rem < h then f1638else if rem > h then f + 11639else match m with1640| RNA -> if d.dm >= 0 then f + 1 else f1641| _ -> if even f then f else f + 11642end1643end1644end16451646function eround_int (m: mode) (e: ereal) : ereal =1647match e with Fin r -> Fin (from_int (round_int m r)) | _ -> e end16481649function fp_rti (m: mode) (x: t) : t =1650if is_nan x then not_a_number x.fmt1651else round_f x.fmt m (if is_positive x then false else true) (eround_int m (ext x))1652Valid (88ms) (colibri2)1653let round_to_integral (m: mode) (x: t) : t1654ensures { result = fp_rti m x }1655= match x.value with1656| Finite _ _ ->1657let n = round_int_d m (to_dyadic x) in1658{proof…} pow2r_int 0; {qed}1659round_d x.fmt m (not (is_positive x)) { dm = n; de = 0 }1660| _ -> {proof…} t_ext x (fp_rti m x); {qed} x1661end1662
The reals strictly between n * 2^w and (n+1) * 2^w round alike, when 2^w is at most half the ulp of the result: w <= e - sb with 2^e <= r. The quotient and the square root are computed with such a w, and their remainder gives the odd dyadic number (2n+1) * 2^(w-1) of the same rounding.
Valid (158ms) (colibri2 8) (split_vc) (depth 1)let ghost uexp_ge (fm: format) (r: real) (e: int) : unit1672requires { pow2r e <=. r }1673ensures { e - fm.sb + 1 <= uexp fm (kdn fm r) }1674= {proof…}1675pow2r_pos e;1676let k = kdn fm r in1677vom_dec fm k;1678let u = uexp fm k in1679pow2r_add fm.sb u; pow2r_int fm.sb; pow2r_pos u;1680assert { power 2 fm.sb = 2 * binade fm };1681scale_cmp (sig fm k + 1) (power 2 fm.sb) (pow2r u);1682assert { r <. pow2r (fm.sb + u) };1683if e > u + fm.sb - 1 then pow2r_le (fm.sb + u) e1684{qed}1685
Two reals strictly inside the same cell, on the same side of its midpoint, have the same rounded magnitudes
Valid (881ms) (cvc5)let ghost round_mag_same_side (fm: format) (r r': real) (k: int) : unit1689requires { kdn fm r = k /\ kdn fm r' = k }1690requires { vom fm k <> r /\ vom fm k <> r' }1691requires { let mid = (vom fm k +. vom fm (k + 1)) /. 2.0 in1692(mid <. r /\ mid <. r') \/ (r <. mid /\ r' <. mid) }1693ensures { forall m. round_mag fm m r = round_mag fm m r' }1694= ()1695Valid (617ms) (colibri2 21) (cvc4) (cvc5 8) (split_vc 4) (depth 2)1696let ghost round_mag_cell (fm: format) (r r': real) (n w e: int) : unit1697requires { 0 <= n }1698requires { from_int n *. pow2r w <. r <. from_int (n + 1) *. pow2r w }1699requires { from_int n *. pow2r w <. r' <. from_int (n + 1) *. pow2r w }1700requires { pow2r e <=. r /\ w <= e - fm.sb }1701ensures { forall m. round_mag fm m r = round_mag fm m r' }1702= {proof…}1703let c = pow2r w in1704pow2r_pos w;1705assert { 0.0 <=. from_int n *. c };1706let k = kdn fm r in1707uexp_ge fm r e;1708vom_dec fm k;1709let u = uexp fm k in1710let s = sig fm k in1711let t = Round.pow2_int (u - w - 1) in1712pow2r_add w (u - w); pow2r_int (u - w);1713assert { power 2 (u - w) = 2 * t };1714assert { pow2r u = from_int (2 * t) *. c };1715let a = s * (2 * t) in1716let b = (s + 1) * (2 * t) in1717let mm = (2 * s + 1) * t in1718assert { vom fm k = from_int a *. c };1719assert { vom fm (k + 1) = from_int b *. c };1720assert { (vom fm k +. vom fm (k + 1)) /. 2.0 = from_int mm *. c };1721scale_cmp a (n + 1) c; scale_cmp n b c; scale_cmp (n + 1) b c;1722scale_cmp a n c; scale_cmp mm n c; scale_cmp mm (n + 1) c;1723assert { a <= n /\ n + 1 <= b };1724assert { vom fm k <. r' <. vom fm (k + 1) };1725kdn_unique fm k r';1726assert { vom fm k <> r /\ vom fm k <> r' };1727if mm <= n then1728assert { from_int mm *. c <. r /\ from_int mm *. c <. r' }1729else1730assert { r <. from_int mm *. c /\ r' <. from_int mm *. c };1731round_mag_same_side fm r r' k1732{qed}1733
Two reals of the same sign and the same rounded magnitudes round alike
Valid (445ms) (colibri2 3) (cvc4) (split_vc) (depth 1)let ghost round_fin_same (fm: format) (m: mode) (z: bool) (r r': real) : unit1737requires { (0.0 <. r /\ 0.0 <. r') \/ (r <. 0.0 /\ r' <. 0.0) }1738requires { forall m. round_mag fm m (if 0.0 <. r then r else -. r) =1739round_mag fm m (if 0.0 <. r' then r' else -. r') }1740ensures { round_fin fm m z r = round_fin fm m z r' }1741= {proof…}1742if pure { 0.0 <. r } then1743assert { round_mag fm m r = round_mag fm m r' }1744else begin1745let mm = mirror m in1746assert { round_mag fm mm (if 0.0 <. r then r else -. r) =1747round_mag fm mm (if 0.0 <. r' then r' else -. r') };1748assert { round_mag fm mm (-. r) = round_mag fm mm (-. r') }1749end1750{qed}1751
2^(qmin-1)The floats and the midpoints of two consecutive floats are multiples of g = 2^(qmin-1): two reals strictly between n g and (n+1) g round to the same float.
vom fm k is the even multiple 2 N of g
Valid (106ms) (colibri2)let ghost vom_cell (fm: format) (k: int) : int1760requires { 0 <= k }1761ensures { vom fm k = from_int (2 * result) *. pow2r (qmin fm - 1) }1762= let b = binade fm in1763binade_ge_2 fm;1764pow2r_succ (qmin fm - 1);1765let e = div k b in1766if e = 0 then begin1767assert { vom fm k = from_int (mod k b) *. pow2r (qmin fm) };1768mod k b1769end else begin1770pow2r_add (qmin fm) (e - 1); pow2r_int (e - 1);1771assert { 0 < e };1772assert { vom fm k = from_int (b + mod k b) *. pow2r (e - 1 + qmin fm) };1773assert { vom fm k = from_int ((b + mod k b) * power 2 (e - 1)) *. pow2r (qmin fm) };1774(b + mod k b) * power 2 (e - 1)1775end1776
A multiple N g compares with a real of the cell (n g, (n+1) g) as N with n
Valid (85ms) (colibri2)let ghost cell_cmp (fm: format) (n nn: int) (r: real) : unit1780requires { from_int n *. pow2r (qmin fm - 1) <. r <. from_int (n + 1) *. pow2r (qmin fm - 1) }1781ensures { from_int nn *. pow2r (qmin fm - 1) <=. r <-> nn <= n }1782ensures { from_int nn *. pow2r (qmin fm - 1) <. r <-> nn <= n }1783ensures { r <. from_int nn *. pow2r (qmin fm - 1) <-> n < nn }1784= {proof…}1785let g = pow2r (qmin fm - 1) in1786pow2r_pos (qmin fm - 1);1787scale_cmp nn n g; scale_cmp n nn g; scale_cmp nn (n + 1) g; scale_cmp (n + 1) nn g1788{qed}1789
The magnitudes of two positive reals of the same cell
Valid (1.5s) (colibri2)let ghost round_mag_gcell (fm: format) (m: mode) (c: int) (x x': real) : unit1792requires { 0 <= c }1793requires { from_int c *. pow2r (qmin fm - 1) <. x <. from_int (c + 1) *. pow2r (qmin fm - 1) }1794requires { from_int c *. pow2r (qmin fm - 1) <. x' <. from_int (c + 1) *. pow2r (qmin fm - 1) }1795ensures { round_mag fm m x = round_mag fm m x' }1796= {proof…}1797let g = pow2r (qmin fm - 1) in1798pow2r_pos (qmin fm - 1);1799assert { 0.0 <=. from_int c *. g };1800let k = kdn fm x in1801let a = vom_cell fm k in1802let b = vom_cell fm (k + 1) in1803cell_cmp fm c (2 * a) x; cell_cmp fm c (2 * a) x';1804cell_cmp fm c (2 * b) x; cell_cmp fm c (2 * b) x';1805cell_cmp fm c (a + b) x; cell_cmp fm c (a + b) x';1806assert { between fm k x' };1807kdn_unique fm k x';1808assert { vom fm k <> x /\ vom fm k <> x' };1809assert { (vom fm k +. vom fm (k + 1)) /. 2.0 = from_int (a + b) *. g }1810{qed}1811
Two reals of the same cell round to the same float
Valid (89ms) (colibri2 17) (cvc5 2) (split_vc) (depth 1)let ghost round_cell (fm: format) (m: mode) (z: bool) (n: int) (r r': real) : unit1814requires { from_int n *. pow2r (qmin fm - 1) <. r <. from_int (n + 1) *. pow2r (qmin fm - 1) }1815requires { from_int n *. pow2r (qmin fm - 1) <. r' <. from_int (n + 1) *. pow2r (qmin fm - 1) }1816ensures { round_fin fm m z r = round_fin fm m z r' }1817= {proof…}1818let g = pow2r (qmin fm - 1) in1819pow2r_pos (qmin fm - 1);1820if 0 <= n then begin1821assert { 0.0 <=. from_int n *. g };1822assert { 0.0 <. r /\ 0.0 <. r' };1823let lemma all (mm: mode) : unit1824ensures { round_mag fm mm r = round_mag fm mm r' }1825= round_mag_gcell fm mm n r r' in1826round_fin_same fm m z r r'1827end else begin1828let c = - n - 1 in1829assert { from_int (n + 1) *. g <=. 0.0 };1830assert { r <. 0.0 /\ r' <. 0.0 };1831assert { from_int c *. g = -. (from_int (n + 1) *. g) };1832assert { from_int (c + 1) *. g = -. (from_int n *. g) };1833let lemma all (mm: mode) : unit1834ensures { round_mag fm mm (-. r) = round_mag fm mm (-. r') }1835= round_mag_gcell fm mm c (-. r) (-. r') in1836round_fin_same fm m z r r'1837end1838{qed}1839Valid (130ms) (colibri2)1840let ghost mul_le_r (x y c: int) : unit1841requires { 0 <= c /\ x <= y }1842ensures { x * c <= y * c }1843= {proof…} assert { (y - x) * c >= 0 } {qed}1844Valid (83ms) (colibri2 8) (cvc5) (split_vc) (depth 1)1845let ghost div_neg (x y: real) : unit1846requires { y <> 0.0 }1847ensures { (-. x) /. y = -. (x /. y) }1848ensures { x /. (-. y) = -. (x /. y) }1849ensures { (-. x) /. (-. y) = x /. y }1850= {proof…}1851let q = x /. y in1852assert { q *. y = x };1853assert { q *. (-. y) = -. x };1854assert { ((-. x) /. (-. y)) *. (-. y) = -. x };1855assert { ((-. x) /. (-. y) -. q) *. (-. y) = 0.0 };1856assert { (-. x) /. (-. y) = q }1857{qed}1858
A dyadic number that rounds as (a / b) * 2^e, a, b > 0
Valid (456ms) (colibri2 41) (cvc4) (cvc5 5) (split_vc 4) (depth 2)let div_d (fm: format) (a b e: int) : dyadic1861requires { 0 < a /\ 0 < b }1862ensures { 0.0 <. dval result }1863ensures { forall m. round_mag fm m (dval result) =1864round_mag fm m (from_int a /. from_int b *. pow2r e) }1865= let na = numbits a in1866let nb = numbits b in1867let l = if fm.sb + 1 + nb - na > 0 then fm.sb + 1 + nb - na else 0 in1868let num = lsl_int a l in1869let q = Zarith.fdiv num b in1870let rem = num - q * b in1871let w = e - l in1872{proof…}1873let ghost g = na - 1 + l - nb in1874numbits_lsl_lt b; numbits_lsl_le a;1875lsl_mul 1 nb; lsl_mul 1 (na - 1); lsl_mul a l;1876assert { power 2 (na - 1) <= a /\ b < power 2 nb };1877assert { power 2 (na - 1 + l) = power 2 g * power 2 nb };1878assert { power 2 (na - 1 + l) = power 2 (na - 1) * power 2 l };1879assert { 1 <= na };1880assert { 0 <= g };1881assert { num = a * power 2 l };1882mul_le_r (power 2 (na - 1)) a (power 2 l);1883assert { power 2 g * b < power 2 g * power 2 nb };1884assert { power 2 g * b < num };1885mul_lt_cancel (power 2 g) q b;1886assert { power 2 g <= q };1887assert { 1 <= power 2 g };1888let ghost c = pure { pow2r w } in1889let ghost r = pure { from_int a /. from_int b *. pow2r e } in1890pow2r_pos w; pow2r_add w l; pow2r_int l;1891assert { r = (from_int num /. from_int b) *. c };1892assert { from_int num /. from_int b = from_int q +. from_int rem /. from_int b };1893assert { 0 <= rem < b };1894assert { 0.0 <=. from_int rem /. from_int b <. 1.0 };1895assert { r = from_int q *. c +. (from_int rem /. from_int b) *. c };1896pow2r_add w g; pow2r_int g;1897assert { pow2r (g + w) <=. from_int q *. c by1898pow2r (g + w) = from_int (power 2 g) *. c };1899{qed}1900if rem = 0 then begin1901{proof…} assert { r = from_int q *. c }; {qed}1902{ dm = q; de = w }1903end else begin1904{proof…}1905assert { 0.0 <. from_int rem /. from_int b };1906assert { (from_int rem /. from_int b) *. c <. c };1907assert { from_int (q + 1) *. c = from_int q *. c +. c };1908assert { from_int q *. c <. r <. from_int (q + 1) *. c };1909pow2r_succ (w - 1);1910assert { pow2r (w - 1) = 0.5 *. c };1911assert { from_int (2 * q + 1) = 2.0 *. from_int q +. 1.0 };1912assert { from_int (2 * q + 1) *. pow2r (w - 1) =1913(2.0 *. from_int q +. 1.0) *. (0.5 *. c) };1914assert { from_int (2 * q + 1) *. pow2r (w - 1) = (from_int q +. 0.5) *. c };1915round_mag_cell fm r (from_int (2 * q + 1) *. pow2r (w - 1)) q w (g + w);1916{qed}1917{ dm = 2 * q + 1; de = w - 1 }1918end1919
function fp_div (m: mode) (x y: t) : t =1923if is_nan x \/ is_nan y \/ (is_zero x /\ is_zero y)1924\/ (is_infinity x /\ is_infinity y) then not_a_number x.fmt1925else if is_zero y then1926(if mul_zneg x y then minus_infinity x.fmt else plus_infinity x.fmt)1927else round_f x.fmt m (mul_zneg x y) (ediv (ext x) (ext y))1928Valid (53ms) (colibri2)1929let ghost round_zero (fm: format) (m: mode) (z: bool) : unit1930ensures { round_fin fm m z 0.0 = mk fm (Finite z 0) }1931= {proof…} vom_zero fm; round_mag_exact fm m 0 {qed}1932Valid (1.3s) (colibri2 49) (cvc4) (cvc5 3) (split_vc 9) (depth 3)1933let div (m: mode) (x y: t) : t1934ensures { x.fmt = y.fmt -> result = fp_div m x y }1935= let fm = x.fmt in1936if not (eq_format fm y.fmt) then mk fm NaN else1937let z = if is_positive x then not (is_positive y) else is_positive y in1938let inf = if z then MinusInf else PlusInf in1939{proof…} finite_sign x; finite_sign y; round_zero fm m z; {qed}1940match x.value, y.value with1941| NaN, _ | _, NaN -> mk fm NaN1942| (PlusInf | MinusInf), (PlusInf | MinusInf) -> mk fm NaN1943| (PlusInf | MinusInf), Finite _ _ ->1944{proof…} assert { mk fm inf = fp_div m x y }; {qed}1945mk fm inf1946| Finite _ _, (PlusInf | MinusInf) ->1947{proof…} assert { mk fm (Finite z 0) = fp_div m x y }; {qed}1948mk fm (Finite z 0)1949| Finite _ kx, Finite _ ky ->1950if ky = 0 then (if kx = 0 then mk fm NaN else mk fm inf)1951else if kx = 0 then begin1952{proof…} assert { mk fm (Finite z 0) = fp_div m x y }; {qed}1953mk fm (Finite z 0)1954end else begin1955let dx = to_dyadic x in1956let dy = to_dyadic y in1957let a = if dx.dm < 0 then - dx.dm else dx.dm in1958let b = if dy.dm < 0 then - dy.dm else dy.dm in1959{proof…}1960pow2r_pos dx.de; pow2r_pos dy.de;1961assert { dx.dm <> 0 /\ dy.dm <> 0 };1962let ghost r = pure { to_real x *. (1.0 /. to_real y) } in1963let ghost e = dx.de - dy.de in1964pow2r_add e dy.de; pow2r_pos e;1965let ghost qq = pure { from_int dx.dm /. from_int dy.dm } in1966assert { r = qq *. pow2r e by1967to_real x = from_int dx.dm *. (pow2r e *. pow2r dy.de)1968/\ to_real y = from_int dy.dm *. pow2r dy.de };1969div_neg (from_int dx.dm) (from_int dy.dm);1970assert { from_int (- dx.dm) = -. from_int dx.dm };1971assert { from_int (- dy.dm) = -. from_int dy.dm };1972if dx.dm > 0 then begin1973if dy.dm > 0 then assert { from_int a /. from_int b = qq /\ 0.0 <. qq }1974else assert { from_int a /. from_int b = -. qq /\ qq <. 0.01975by from_int b = -. from_int dy.dm }1976end else begin1977if dy.dm > 0 then assert { from_int a /. from_int b = -. qq /\ qq <. 0.01978by from_int a = -. from_int dx.dm }1979else assert { from_int a /. from_int b = qq /\ 0.0 <. qq1980by from_int a = -. from_int dx.dm /\ from_int b = -. from_int dy.dm }1981end;1982assert { dx.dm > 0 <-> is_positive x };1983assert { dy.dm > 0 <-> is_positive y };1984assert { not z -> 0.0 <. r /\ r = from_int a /. from_int b *. pow2r e };1985assert { z -> r <. 0.0 /\ -. r = from_int a /. from_int b *. pow2r e };1986{qed}1987let d = div_d fm a b (dx.de - dy.de) in1988let sd = if z then { dm = - d.dm; de = d.de } else d in1989{proof…}1990assert { z -> dval sd = -. dval d };1991round_fin_same fm m z r (dval sd);1992assert { ediv (ext x) (ext y) = Fin r };1993assert { fp_div m x y = round_f fm m z (Fin r) };1994assert { round_f fm m z (Fin (dval sd)) = fp_div m x y };1995{qed}1996round_d fm m z sd1997end1998end1999
Valid (130ms) (colibri2)let ghost mul_lt_pos (x y c: real) : unit2003requires { 0.0 <. c /\ x <. y }2004ensures { x *. c <. y *. c }2005= {proof…} assert { 0.0 <. (y -. x) *. c } {qed}2006
A dyadic number that rounds as sqrt (a * 2^e), a > 0
Valid (899ms) (colibri2 60) (cvc5 8) (split_vc 15) (depth 5)let sqrt_d (fm: format) (a e: int) : dyadic2009requires { 0 < a }2010ensures { 0.0 <. dval result }2011ensures { forall m. round_mag fm m (dval result) =2012round_mag fm m (S.sqrt (from_int a *. pow2r e)) }2013= let ev = even e in2014let a1 = if ev then a else 2 * a in2015let e1 = if ev then e else e - 1 in2016let h = asr_int e1 1 in2017let n1 = numbits a1 in2018let l0 = fm.sb + 2 - asr_int n1 1 in2019let l = if l0 > 0 then l0 else 0 in2020let num = lsl_int a1 (2 * l) in2021let (s, rem) = Zarith.sqrt_rem num in2022let w = h - l in2023{proof…}2024asr_div e1 1; asr_div n1 1;2025assert { e1 = 2 * h };2026pow2r_succ e1;2027assert { from_int a *. pow2r e = from_int a1 *. pow2r e1 };2028numbits_lsl_le a1; lsl_mul 1 (n1 - 1); lsl_mul a1 (2 * l);2029assert { 1 <= n1 };2030let ghost g = fm.sb + 1 in2031assert { 2 * g <= n1 - 1 + 2 * l };2032assert { power 2 (n1 - 1 + 2 * l) = power 2 (n1 - 1) * power 2 (2 * l) };2033mul_le_r (power 2 (n1 - 1)) a1 (power 2 (2 * l));2034assert { power 2 (2 * g) <= power 2 (n1 - 1 + 2 * l) };2035assert { power 2 (2 * g) = power 2 g * power 2 g };2036assert { power 2 g * power 2 g <= num };2037if s < power 2 g then begin2038mul_le_r (s + 1) (power 2 g) (s + 1);2039mul_le_r (s + 1) (power 2 g) (power 2 g);2040assert { (s + 1) * power 2 g = power 2 g * (s + 1) };2041assert { false }2042end;2043assert { power 2 g <= s };2044let ghost c = pure { pow2r w } in2045pow2r_pos w;2046pow2r_add (2 * w) (2 * l); pow2r_int (2 * l); pow2r_add w w;2047assert { 2 * w + 2 * l = e1 };2048assert { from_int a1 *. pow2r e1 = from_int num *. (c *. c) };2049let ghost r = pure { S.sqrt (from_int a *. pow2r e) } in2050assert { r = S.sqrt (from_int num) *. c by2051S.sqrt (from_int num *. (c *. c)) = S.sqrt (from_int num) *. S.sqrt (c *. c)2052/\ S.sqrt (c *. c) = c };2053assert { from_int s <=. S.sqrt (from_int num) by2054S.sqrt (from_int (s * s)) = from_int s2055/\ S.sqrt (from_int (s * s)) <=. S.sqrt (from_int num) };2056assert { S.sqrt (from_int num) <. from_int (s + 1) by2057S.sqrt (from_int ((s + 1) * (s + 1))) = from_int (s + 1)2058/\ S.sqrt (from_int num) <=. S.sqrt (from_int ((s + 1) * (s + 1)))2059/\ (S.sqrt (from_int num) = from_int (s + 1) ->2060from_int num = from_int (s + 1) *. from_int (s + 1)2061by from_int num = S.sqr (S.sqrt (from_int num))) };2062scale_cmp 0 s c;2063pow2r_add w g; pow2r_int g;2064assert { pow2r (g + w) = from_int (power 2 g) *. c };2065scale_cmp (power 2 g) s c;2066assert { pow2r (g + w) <=. r };2067{qed}2068if rem = 0 then begin2069{proof…}2070assert { S.sqrt (from_int num) = from_int s by2071from_int num = from_int s *. from_int s };2072{qed}2073{ dm = s; de = w }2074end else begin2075{proof…}2076assert { from_int s <. S.sqrt (from_int num) by2077from_int s = S.sqrt (from_int num) ->2078from_int num = from_int s *. from_int s2079by from_int num = S.sqr (S.sqrt (from_int num)) };2080mul_lt_pos (from_int s) (S.sqrt (from_int num)) c;2081mul_lt_pos (S.sqrt (from_int num)) (from_int (s + 1)) c;2082assert { from_int s *. c <. r <. from_int (s + 1) *. c };2083pow2r_succ (w - 1);2084assert { pow2r (w - 1) = 0.5 *. c };2085assert { from_int (2 * s + 1) *. pow2r (w - 1) =2086(2.0 *. from_int s +. 1.0) *. (0.5 *. c) };2087assert { from_int (2 * s + 1) *. pow2r (w - 1) = (from_int s +. 0.5) *. c };2088assert { from_int s *. c <. (from_int s +. 0.5) *. c <. from_int (s + 1) *. c };2089round_mag_cell fm r (from_int (2 * s + 1) *. pow2r (w - 1)) s w (g + w);2090{qed}2091{ dm = 2 * s + 1; de = w - 1 }2092end20932094function fp_sqrt (m: mode) (x: t) : t =2095if is_nan x \/ (not is_positive x /\ not is_zero x) then not_a_number x.fmt2096else round_f x.fmt m (if is_positive x then false else true) (esqrt (ext x))2097Valid (324ms) (colibri2)2098let sqrt (m: mode) (x: t) : t2099ensures { result = fp_sqrt m x }2100= let fm = x.fmt in2101{proof…} finite_sign x; {qed}2102match x.value with2103| NaN | MinusInf -> mk fm NaN2104| PlusInf -> {proof…} t_ext x (fp_sqrt m x); {qed} x2105| Finite ng k ->2106if k = 0 then begin2107{proof…}2108assert { S.sqrt (0.0 *. 0.0) = 0.0 };2109round_zero fm m ng;2110t_ext x (fp_sqrt m x);2111{qed}2112x2113end else if ng then mk fm NaN2114else begin2115let d = to_dyadic x in2116{proof…} pow2r_pos d.de; assert { 0 < d.dm }; {qed}2117let sd = sqrt_d fm d.dm d.de in2118{proof…}2119assert { 0.0 <. S.sqrt (to_real x) by21200.0 <=. S.sqrt (to_real x) /\2121(S.sqrt (to_real x) = 0.0 -> to_real x = S.sqr (S.sqrt (to_real x)) = 0.0) };2122round_fin_same fm m false (S.sqrt (to_real x)) (dval sd);2123{qed}2124round_d fm m false sd2125end2126end2127
The index, and 0 for NaN
Valid (57ms) (colibri2)let index_t (x: t) : int2132ensures { not is_nan x -> result = index x }2133= if is_nan x then 0 else index_p x2134Valid (144ms) (colibri2)2135let of_index_p (fm: format) (i: int) : t2136ensures { result = of_index fm i }2137= let nb = nb_sign_p fm in2138if 0 <= i && i < nb - 1 then mk fm (Finite false i)2139else if - nb < i && i < 0 then mk fm (Finite true (-1 - i))2140else if i = nb - 1 then mk fm PlusInf2141else if i = - nb then mk fm MinusInf2142else mk fm NaN21432144function succ_dz (x: t) : t = of_index x.fmt (index x + 1)2145function pred_dz (x: t) : t = of_index x.fmt (index x - 1)2146
Total: NaN and +inf are returned unchanged
Valid (77ms) (colibri2)let succ_diff_zero (x: t) : t2149ensures { not is_nan x /\ not is_plus_infinity x -> result = succ_dz x }2150= match x.value with2151| NaN | PlusInf -> x2152| _ -> of_index_p x.fmt (index_p x + 1)2153end2154
Total: NaN and –inf are returned unchanged
Valid (76ms) (colibri2)let pred_diff_zero (x: t) : t2157ensures { not is_nan x /\ not is_minus_infinity x -> result = pred_dz x }2158= match x.value with2159| NaN | MinusInf -> x2160| _ -> of_index_p x.fmt (index_p x - 1)2161end2162
Total: NaN when an argument is NaN or the formats differ
Valid (80ms) (colibri2)let mid_index (x y: t) : t2165ensures { not is_nan x /\ not is_nan y /\ x.fmt = y.fmt ->2166result = of_index x.fmt (div (index x + index y) 2) }2167= if is_nan x || is_nan y || not (eq_format x.fmt y.fmt) then mk x.fmt NaN2168else begin2169{proof…} asr_div (index_p x + index_p y) 1; {qed}2170of_index_p x.fmt (asr_int (index_p x + index_p y) 1)2171end2172
Valid (88ms) (colibri2 14) (cvc5) (split_vc 2) (depth 2)let round_q (fm: format) (m: mode) (zneg: bool) (n d: int) : t2176ensures { 0 < d -> result = round_f fm m zneg (Fin (from_int n /. from_int d)) }2177= if d <= 0 then mk fm NaN2178else if n = 0 then begin2179{proof…} round_zero fm m zneg; assert { from_int n /. from_int d = 0.0 }; {qed}2180mk fm (Finite zneg 0)2181end else begin2182let a = if n < 0 then - n else n in2183let dd = div_d fm a d 0 in2184let sd = if n < 0 then { dm = - dd.dm; de = dd.de } else dd in2185{proof…}2186pow2r_int 0;2187let ghost r = pure { from_int n /. from_int d } in2188div_neg (from_int n) (from_int d);2189assert { from_int (- n) = -. from_int n };2190assert { from_int a /. from_int d *. pow2r 0 = from_int a /. from_int d };2191assert { 0 < n -> 0.0 <. r /\ r = from_int a /. from_int d };2192assert { n < 0 -> r <. 0.0 /\ -. r = from_int a /. from_int d };2193assert { n < 0 -> dval sd = -. dval dd };2194round_fin_same fm m zneg r (dval sd);2195{qed}2196round_d fm m zneg sd2197end2198
The rounding of every real strictly between n/2^k and (n+1)/2^k, when 2^-k <= 2^(qmin-1): the rounding of their midpoint (no float nor midpoint of two floats is strictly between them, round_cell)
Valid (531ms) (colibri2 33) (cvc4) (cvc5 6) (split_vc 4) (depth 2)let round_between (fm: format) (m: mode) (n k: int) : t2205requires { 1 - qmin fm <= k }2206ensures { forall r. from_int n /. from_int (power 2 k) <. r <. from_int (n + 1) /. from_int (power 2 k) ->2207result = round_f fm m (r <. 0.0) (Fin r) }2208= let d = lsl_int 1 (k + 1) in2209let n2 = 2 * n + 1 in2210{proof…}2211lsl_mul 1 (k + 1);2212let ghost j = pure { k - (1 - qmin fm) } in2213let ghost e = pure { pow2r (- (k + 1)) } in2214let ghost g = pure { pow2r (qmin fm - 1) } in2215pow2r_pos (- (k + 1)); pow2r_int j; pow2r_int (j + 1);2216assert { 0 < power 2 k /\ power 2 (k + 1) = 2 * power 2 k /\ d = power 2 (k + 1) };2217assert { e = 1.0 /. from_int d };2218pow2r_succ (- (k + 1));2219assert { pow2r (- k) = 1.0 /. from_int (power 2 k) };2220assert { pow2r (- k) = 2.0 *. e };2221pow2r_add (j + 1) (- (k + 1));2222assert { j + 1 + (- (k + 1)) = qmin fm - 1 };2223assert { g = from_int (power 2 (j + 1)) *. e };2224let ghost c = pure { EuclideanDivision.div n (power 2 j) } in2225assert { 0 < power 2 j /\ power 2 (j + 1) = 2 * power 2 j };2226assert { n = c * power 2 j + EuclideanDivision.mod n (power 2 j) };2227assert { 0 <= EuclideanDivision.mod n (power 2 j) < power 2 j };2228assert { c * power 2 j <= n < (c + 1) * power 2 j };2229assert { c * power 2 (j + 1) = 2 * (c * power 2 j) };2230assert { (c + 1) * power 2 (j + 1) = 2 * ((c + 1) * power 2 j) };2231assert { c * power 2 (j + 1) <= 2 * n /\ 2 * n + 2 <= (c + 1) * power 2 (j + 1) };2232let ghost lo = pure { from_int n /. from_int (power 2 k) } in2233let ghost hi = pure { from_int (n + 1) /. from_int (power 2 k) } in2234let ghost r0 = pure { from_int n2 /. from_int d } in2235assert { lo = from_int n *. pow2r (- k) };2236assert { hi = from_int (n + 1) *. pow2r (- k) };2237assert { lo = from_int (2 * n) *. e };2238assert { hi = from_int (2 * n + 2) *. e };2239assert { r0 = from_int n2 *. e };2240scale_cmp (2 * n) n2 e; scale_cmp n2 (2 * n + 2) e;2241assert { from_int c *. g = from_int (c * power 2 (j + 1)) *. e };2242assert { from_int (c + 1) *. g = from_int ((c + 1) * power 2 (j + 1)) *. e };2243scale_cmp (c * power 2 (j + 1)) (2 * n) e;2244scale_cmp (2 * n + 2) ((c + 1) * power 2 (j + 1)) e;2245assert { lo <. r0 <. hi };2246assert { from_int c *. g <=. lo };2247assert { hi <=. from_int (c + 1) *. g };2248scale_cmp n2 0 e;2249assert { n2 < 0 <-> r0 <. 0.0 };2250let lemma pt (r: real) : unit2251requires { lo <. r <. hi }2252ensures { round_fin fm m (n2 < 0) r0 = round_f fm m (r <. 0.0) (Fin r) }2253= scale_cmp n 0 e; scale_cmp 0 (2 * n + 2) e;2254assert { (r <. 0.0) <-> n2 < 0 };2255round_cell fm m (n2 < 0) c r0 r in2256{qed}2257round_q fm m (n2 < 0) n2 d2258
Every real r of [n1/d1, n2/d2] rounds to x (as to_fp of a real in SMT–LIB: a zero result is –0 when r < 0) when the two ends round to x. None when they round to different floats, or a denominator is not positive. F.of_a narrows the bracket of an algebraic number until it gives a float.
Valid (354ms) (colibri2 15) (split_vc) (depth 1)let round_bracket (fm: format) (m: mode) (n1 d1 n2 d2: int) : option t2267ensures { match result with2268| None -> d1 <= 0 \/ d2 <= 0 \/2269round_f fm m (n1 < 0) (Fin (from_int n1 /. from_int d1))2270<> round_f fm m (n2 < 0) (Fin (from_int n2 /. from_int d2))2271| Some x -> forall r. from_int n1 /. from_int d1 <=. r <=. from_int n2 /. from_int d2 ->2272x = round_f fm m (r <. 0.0) (Fin r)2273end }2274= if d1 <= 0 || d2 <= 0 then None2275else begin2276let x1 = round_q fm m (n1 < 0) n1 d1 in2277let x2 = round_q fm m (n2 < 0) n2 d2 in2278{proof…}2279let ghost r1 = pure { from_int n1 /. from_int d1 } in2280let ghost r2 = pure { from_int n2 /. from_int d2 } in2281round_fin_facts fm m (n1 < 0) r1; round_fin_facts fm m (n2 < 0) r2;2282{qed}2283if le_diff_zero x1 x2 && le_diff_zero x2 x1 then begin2284{proof…}2285assert { 0.0 <. from_int d1 /\ 0.0 <. from_int d2 };2286assert { n1 < 0 -> r1 <. 0.0 };2287assert { 0 <= n1 -> 0.0 <=. r1 };2288assert { n2 < 0 -> r2 <. 0.0 };2289assert { 0 <= n2 -> 0.0 <=. r2 };2290assert { index x1 = index x2 };2291let lemma pt (r: real) : unit2292requires { r1 <=. r <=. r2 }2293ensures { x1 = round_f fm m (r <. 0.0) (Fin r) }2294= let y = round_fin fm m (r <. 0.0) r in2295round_fin_facts fm m (r <. 0.0) r;2296round_fin_le fm m (n1 < 0) (r <. 0.0) r1 r;2297round_fin_le fm m (r <. 0.0) (n2 < 0) r r2;2298assert { index y = index x1 };2299index_inj x1; index_inj y in2300{qed}2301Some x12302end else None2303end2304
The sign of a zero result: the sign of the exact result when it is not zero, else the rule of the addition with the sign of the product (IEEE 754 §6.3)
function fma_zneg (m: mode) (x y z: t) (e: ereal) : bool =2311match e with2312| Fin r ->2313if r <. 0.0 then true else if 0.0 <. r then false2314else if (not mul_zneg x y) <-> is_positive z then mul_zneg x y2315else (if m = RTN then true else false)2316| _ -> false2317end23182319function fp_fma (m: mode) (x y z: t) : t =2320if is_nan x \/ is_nan y \/ is_nan z \/ (is_zero x /\ is_infinity y)2321\/ (is_infinity x /\ is_zero y)2322\/ opposite (emul (ext x) (ext y)) (ext z) then not_a_number x.fmt2323else2324let e = eadd (emul (ext x) (ext y)) (ext z) in2325round_f x.fmt m (fma_zneg m x y z e) e2326Valid (3.2s) (colibri2 18) (cvc4 2) (cvc5 3) (split_vc 5) (depth 5)2327let fma (m: mode) (x y z: t) : t2328ensures { x.fmt = y.fmt /\ x.fmt = z.fmt -> result = fp_fma m x y z }2329= let fm = x.fmt in2330if not (eq_format fm y.fmt && eq_format fm z.fmt) then mk fm NaN2331else if is_nan x || is_nan y || is_nan z then mk fm NaN2332else begin2333{proof…} finite_sign x; finite_sign y; finite_sign z; {qed}2334let pz = if is_positive x then not (is_positive y) else is_positive y in2335match x.value, y.value with2336| Finite _ _, Finite _ _ ->2337match z.value with2338| PlusInf | MinusInf -> z2339| _ ->2340let d = dadd (dmul (to_dyadic x) (to_dyadic y)) (to_dyadic z) in2341let rtn = match m with RTN -> true | _ -> false end in2342let same = if pz then not (is_positive z) else is_positive z in2343let zn = if d.dm < 0 then true else if d.dm > 0 then false2344else if same then pz else rtn in2345{proof…}2346pow2r_pos d.de;2347scale_cmp d.dm 0 (pow2r d.de); scale_cmp 0 d.dm (pow2r d.de);2348assert { zn = fma_zneg m x y z (Fin (dval d)) };2349{qed}2350round_d fm m zn d2351end2352| _ ->2353if is_zero x || is_zero y then mk fm NaN2354else begin2355let inf = if pz then MinusInf else PlusInf in2356match z.value with2357| PlusInf -> if pz then mk fm NaN else z2358| MinusInf -> if pz then z else mk fm NaN2359| _ -> mk fm inf2360end2361end2362end2363end2364
function next_up_index (i: int) : int = if i = -1 then 1 else i + 12368function next_down_index (i: int) : int = if i = 0 then -2 else i - 12369
Total: NaN and +inf are returned unchanged
Valid (62ms) (colibri2)let next_up (x: t) : t2372ensures { not is_nan x /\ not is_plus_infinity x ->2373result = of_index x.fmt (next_up_index (index x)) }2374ensures { is_nan x \/ is_plus_infinity x -> result = x }2375= match x.value with2376| NaN | PlusInf -> x2377| _ -> let i = index_p x in of_index_p x.fmt (if i = -1 then 1 else i + 1)2378end2379
Total: NaN and –inf are returned unchanged
Valid (57ms) (colibri2)let next_down (x: t) : t2382ensures { not is_nan x /\ not is_minus_infinity x ->2383result = of_index x.fmt (next_down_index (index x)) }2384ensures { is_nan x \/ is_minus_infinity x -> result = x }2385= match x.value with2386| NaN | MinusInf -> x2387| _ -> let i = index_p x in of_index_p x.fmt (if i = 0 then -2 else i - 1)2388end2389
f is the rounding of a real r up (float_lo) or down (float_hi), with a zero result negative when r < 0; exact tells whether f is finite of value r. The result is the least (resp. greatest) float v with r <= v (resp. v <= r), or r < v (resp. v < r) when strict, among the finite floats: –0 (resp. +0) when r = 0, the next float when r is a float and strict, else f.
Valid (1.4s) (colibri2 14) (cvc4 2) (cvc5 2) (split_vc) (depth 1)let float_lo (f: t) (strict exact: bool) : t2399ensures { result.fmt = f.fmt }2400ensures { forall r. f = round_f f.fmt RTP (r <. 0.0) (Fin r) ->2401(exact <-> is_finite f /\ to_real f = r) ->2402forall v. v.fmt = f.fmt -> is_finite v ->2403(if strict then r <. to_real v else r <=. to_real v) -> le_dz result v }2404= let g = if exact && is_zero f then mk f.fmt (Finite true 0) else f in2405let res = if exact && strict then next_up g else g in2406{proof…}2407let lemma pt (r: real) (v: t) : unit2408requires { f = round_f f.fmt RTP (r <. 0.0) (Fin r) }2409requires { exact <-> is_finite f /\ to_real f = r }2410requires { v.fmt = f.fmt /\ is_finite v }2411requires { if strict then r <. to_real v else r <=. to_real v }2412ensures { le_dz res v }2413= let fm = f.fmt in2414nb_sign_ge fm;2415round_fin_facts fm RTP (r <. 0.0) r;2416round_fin_up fm (r <. 0.0) r;2417if exact then begin2418assert { is_finite g /\ g.fmt = fm /\ to_real g = r };2419if strict then begin2420if pure { index v <= index g } then begin2421ext_le v g; absurd2422end;2423assert { index g < index v };2424if pure { index g = -1 } then begin2425if pure { index v = 0 } then begin2426assert { is_zero v }; vom_zero fm; absurd2427end2428end;2429of_index_range fm (next_up_index (index g))2430end else begin2431if pure { index v < index g } then begin2432if pure { is_zero v /\ is_zero g } then absurd;2433ext_lt v g; absurd2434end2435end2436end else begin2437round_f_exact RTP v;2438let zv = if is_positive v then false else true in2439if pure { is_zero f /\ is_zero v } then begin2440vom_zero fm;2441assert { to_real f = 0.0 /\ r <> 0.0 /\ r <. 0.0 }2442end;2443round_fin_le fm RTP (r <. 0.0) zv r (to_real v)2444end in2445{qed}2446res2447Valid (1.2s) (colibri2 14) (cvc4 2) (cvc5 2) (split_vc) (depth 1)2448let float_hi (f: t) (strict exact: bool) : t2449ensures { result.fmt = f.fmt }2450ensures { forall r. f = round_f f.fmt RTN (r <. 0.0) (Fin r) ->2451(exact <-> is_finite f /\ to_real f = r) ->2452forall v. v.fmt = f.fmt -> is_finite v ->2453(if strict then to_real v <. r else to_real v <=. r) -> le_dz v result }2454= let g = if exact && is_zero f then mk f.fmt (Finite false 0) else f in2455let res = if exact && strict then next_down g else g in2456{proof…}2457let lemma pt (r: real) (v: t) : unit2458requires { f = round_f f.fmt RTN (r <. 0.0) (Fin r) }2459requires { exact <-> is_finite f /\ to_real f = r }2460requires { v.fmt = f.fmt /\ is_finite v }2461requires { if strict then to_real v <. r else to_real v <=. r }2462ensures { le_dz v res }2463= let fm = f.fmt in2464nb_sign_ge fm;2465round_fin_facts fm RTN (r <. 0.0) r;2466round_fin_down fm (r <. 0.0) r;2467if exact then begin2468assert { is_finite g /\ g.fmt = fm /\ to_real g = r };2469if strict then begin2470if pure { index g <= index v } then begin2471ext_le g v; absurd2472end;2473assert { index v < index g };2474if pure { index g = 0 } then begin2475if pure { index v = -1 } then begin2476assert { is_zero v }; vom_zero fm; absurd2477end2478end;2479of_index_range fm (next_down_index (index g))2480end else begin2481if pure { index g < index v } then begin2482if pure { is_zero v /\ is_zero g } then absurd;2483ext_lt g v; absurd2484end2485end2486end else begin2487round_f_exact RTN v;2488let zv = if is_positive v then false else true in2489if pure { is_zero f /\ is_zero v } then begin2490vom_zero fm;2491assert { to_real f = 0.0 /\ r <> 0.0 /\ 0.0 <. r }2492end;2493round_fin_le fm RTN zv (r <. 0.0) (to_real v) r2494end in2495{qed}2496res2497end2498