library colibrilib.fbin_ieee — module Equivfbin.mlw is the rounding of Flocqround_fin fm m z r (fbin.Float) is Flocq's round radix2 (FLT_exp (qmin fm) (sb fm)) in the mode m (colibrilib.flocq.Round, realized in Rocq from Flocq's definitions and lemmas) when the magnitude of that rounding is below 2^emax. Otherwise it is the overflow of IEEE 754 §7.4, as in Flocq's binary_overflow. The sign of a zero result is not Flocq's business: it is z.
The other operations of fbin.Impl are specified with round_f, which is round_fin on the finite reals.
module Equiv13use int.Int14use int.Power15use int.EuclideanDivision16use real.RealInfix17use real.FromInt18use real.Abs19use colibrilib.fp.Widen20use colibrilib.fbin.Pow2r21use colibrilib.fbin.Format22use colibrilib.fbin.Float23use colibrilib.flocq.Round as F24
Flocq's rounding in the mode m, for the format fm
function flocq (fm: format) (m: mode) (r: real) : real =27match m with28| RTN -> F.rnd_dn (sb fm) (qmin fm) r29| RTP -> F.rnd_up (sb fm) (qmin fm) r30| RTZ -> F.rnd_zr (sb fm) (qmin fm) r31| RNE -> F.rnd_ne (sb fm) (qmin fm) r32| RNA -> F.rnd_na (sb fm) (qmin fm) r33end34
The largest exponent: 2^emax is the least magnitude that overflows
function emax (fm: format) : int = power 2 (eb fm - 1)38
Flocq's overflow_to_inf
predicate overflow_to_inf (m: mode) (neg: bool) =41match m with42| RNE | RNA -> true43| RTP -> not neg44| RTN -> neg45| RTZ -> false46end47
Flocq's binary_overflow: the infinity, or the largest finite float
function overflow (fm: format) (m: mode) (neg: bool) : value =51if overflow_to_inf m neg then (if neg then MinusInf else PlusInf)52else Finite neg (nb_sign fm - 2)53
Valid (19ms) (colibri2)let ghost pow2_pow2r (e: int) : unit57ensures { F.pow2 e = pow2r e }58= ()59Valid (28ms) (colibri2)60let ghost binade_2 (fm: format) : unit61ensures { power 2 (sb fm) = 2 * binade fm }62= {proof…} assert { power 2 (sb fm) = power 2 ((sb fm - 1) + 1) } {qed}63Valid (25ms) (colibri2)64let ghost vom_mono (fm: format) (k l: int) : unit65requires { 0 <= k <= l }66ensures { vom fm k <=. vom fm l }67= {proof…} if k < l then vom_lt fm k l {qed}68Valid (26ms) (colibri2)69let ghost vom_generic (fm: format) (k: int) : unit70requires { 0 <= k }71ensures { F.generic (sb fm) (qmin fm) (vom fm k) }72= {proof…}73vom_dec fm k; binade_2 fm; pow2_pow2r (uexp fm k);74assert { vom fm k = from_int (sig fm k) *. F.pow2 (uexp fm k) }75{qed}76
The magnitude of m * 2^e
Valid (43ms) (colibri2)let rec ghost function norm (fm: format) (m e: int) : int79requires { qmin fm <= e /\ 0 <= m < 2 * binade fm }80ensures { 0 <= result /\ vom fm result = from_int m *. pow2r e }81variant { e - qmin fm }82= if pure { e = qmin fm \/ binade fm <= m } then begin83{proof…}84vom_s fm e m;85assert { 0 <= (e - qmin fm) * binade fm };86{qed}87pure { (e - qmin fm) * binade fm + m }88end else begin89{proof…} pow2r_succ (e - 1); {qed}90norm fm (2 * m) (e - 1)91end92Valid (45ms) (colibri2)93let ghost generic_vom (fm: format) (x: real) : int94requires { F.generic (sb fm) (qmin fm) x /\ 0.0 <=. x }95ensures { 0 <= result /\ vom fm result = x }96= let (m, e) = any (int, int) ensures { let (m, e) = result in97qmin fm <= e /\ - power 2 (sb fm) < m < power 2 (sb fm) /\98x = from_int m *. F.pow2 e } in99{proof…}100pow2_pow2r e; pow2r_pos e; binade_2 fm;101assert { 0 <= m by m < 0 -> from_int m *. pow2r e <. 0.0 };102{qed}103norm fm m e104Valid (31ms) (colibri2 2) (cvc5) (split_vc) (depth 1)105let ghost generic_neg (p q: int) (x: real) : unit106requires { F.generic p q x }107ensures { F.generic p q (-. x) }108= {proof…}109let (m, e) = any (int, int) ensures { let (m, e) = result in110q <= e /\ - power 2 p < m < power 2 p /\ x = from_int m *. F.pow2 e } in111assert { -. x = from_int (- m) *. F.pow2 e }112{qed}113Valid (21ms) (colibri2)114let lemma generic_neg_l (p q: int) (x: real)115requires { F.generic p q x }116ensures { F.generic p q (-. x) }117= generic_neg p q x118Valid (69ms) (colibri2 2) (cvc5) (split_vc) (depth 1)119let ghost even_repr_neg (p q: int) (x: real) : unit120requires { F.even_repr p q (-. x) }121ensures { F.even_repr p q x }122= {proof…}123let (m, e, h) = any (int, int, int) ensures { let (m, e, h) = result in124q <= e /\ - power 2 p < m < power 2 p /\ -. x = from_int m *. F.pow2 e /\125m = 2 * h } in126assert { x = from_int (- m) *. F.pow2 e /\ - m = 2 * (- h) }127{qed}128
The floats are not strictly between the neighbours of a real
Valid (100ms) (colibri2)let ghost neighbours (fm: format) (k: int) (r g: real) : unit131requires { between fm k r /\ F.generic (sb fm) (qmin fm) g }132ensures { g <=. vom fm k \/ vom fm (k + 1) <=. g }133= {proof…}134vom_zero fm; vom_mono fm 0 k;135if pure { 0.0 <=. g } then begin136let j = generic_vom fm g in137if j <= k then vom_mono fm j k else vom_mono fm (k + 1) j138end139{qed}140Valid (17ms) (colibri2)141let lemma neighbours_l (fm: format) (k: int) (r g: real)142requires { between fm k r /\ F.generic (sb fm) (qmin fm) g }143ensures { g <=. vom fm k \/ vom fm (k + 1) <=. g }144= neighbours fm k r g145
Valid (24ms) (colibri2)let ghost scale_eq (a b x y: int) : unit149requires { x <= y /\ from_int a *. pow2r x = from_int b *. pow2r y }150ensures { a = b * power 2 (y - x) }151= {proof…}152pow2r_add x (y - x); pow2r_int (y - x); pow2r_pos x;153assert { from_int a *. pow2r x = from_int (b * power 2 (y - x)) *. pow2r x };154scale_cmp a (b * power 2 (y - x)) (pow2r x)155{qed}156Valid (30ms) (colibri2)157let ghost parity (j t: int) : unit158ensures { j = 2 * t -> mod j 2 = 0 }159ensures { j = 2 * t + 1 -> mod j 2 = 1 }160= {proof…}161assert { mod (2 * t + 0) 2 = mod 0 2 };162assert { mod (2 * t + 1) 2 = mod 1 2 }163{qed}164Valid (391ms) (colibri2 15) (cvc4) (cvc5) (split_vc) (depth 1)165let ghost even_vom (fm: format) (j: int) : unit166requires { 0 <= j /\ F.even_repr (sb fm) (qmin fm) (vom fm j) }167ensures { mod j 2 = 0 }168= {proof…}169let (_m, e, q) = any (int, int, int) ensures { let (m, e, q) = result in170qmin fm <= e /\ - power 2 (sb fm) < m < power 2 (sb fm) /\171vom fm j = from_int m *. F.pow2 e /\ m = 2 * q } in172pow2_pow2r e; pow2r_succ e; pow2r_pos e; binade_2 fm; binade_ge_2 fm;173vom_dec fm j; vom_zero fm; vom_mono fm 0 j;174let u = pure { uexp fm j } in175let s = pure { sig fm j } in176assert { vom fm j = from_int q *. pow2r (e + 1) };177assert { 0 <= q by q < 0 -> from_int q *. pow2r (e + 1) <. 0.0 };178assert { q < binade fm };179assert { binade fm = 2 * power 2 (sb fm - 2)180by power 2 (sb fm - 1) = power 2 ((sb fm - 2) + 1) };181if u <= e then begin182scale_eq s q u (e + 1);183assert { power 2 (e + 1 - u) = 2 * power 2 (e - u) };184let t = pure { (u - qmin fm) * power 2 (sb fm - 2) + q * power 2 (e - u) } in185assert { s = 2 * (q * power 2 (e - u)) };186assert { (u - qmin fm) * binade fm = 2 * ((u - qmin fm) * power 2 (sb fm - 2)) };187assert { j = 2 * t };188parity j t189end else begin190scale_eq q s (e + 1) u;191assert { 1 <= power 2 (u - (e + 1)) };192assert { s <= s * power 2 (u - (e + 1)) };193absurd194end195{qed}196
Valid (7.8s) (colibri2 15) (cvc5 2) (split_vc 3) (depth 2)let ghost between_round (p q: int) (lo hi r: real) : unit200requires { 1 < p }201requires { F.generic p q lo /\ F.generic p q hi /\ lo <. r <. hi }202requires { forall g. F.generic p q g -> g <=. lo \/ hi <=. g }203ensures { F.rnd_dn p q r = lo /\ F.rnd_up p q r = hi }204ensures { r -. lo <. hi -. r -> F.rnd_ne p q r = lo /\ F.rnd_na p q r = lo }205ensures { hi -. r <. r -. lo -> F.rnd_ne p q r = hi /\ F.rnd_na p q r = hi }206ensures { r -. lo = hi -. r ->207(F.rnd_ne p q r = lo /\ F.even_repr p q lo) \/208(F.rnd_ne p q r = hi /\ F.even_repr p q hi) }209ensures { r -. lo = hi -. r ->210(F.rnd_na p q r = lo /\ abs hi <=. abs lo) \/211(F.rnd_na p q r = hi /\ abs lo <=. abs hi) }212= {proof…}213assert { F.rnd_dn p q r = lo };214assert { F.rnd_up p q r = hi };215assert { F.rnd_ne p q r = lo \/ F.rnd_ne p q r = hi216by abs (F.rnd_ne p q r -. r) <=. abs (lo -. r) /\217abs (F.rnd_ne p q r -. r) <=. abs (hi -. r) /\218(F.rnd_ne p q r <=. lo \/ hi <=. F.rnd_ne p q r) };219assert { F.rnd_na p q r = lo \/ F.rnd_na p q r = hi220by abs (F.rnd_na p q r -. r) <=. abs (lo -. r) /\221abs (F.rnd_na p q r -. r) <=. abs (hi -. r) /\222(F.rnd_na p q r <=. lo \/ hi <=. F.rnd_na p q r) };223if pure { r -. lo = hi -. r } then begin224assert { F.nearest p q r lo };225assert { F.nearest p q r hi }226end227{qed}228Valid (379ms) (colibri2 10) (split_vc) (depth 1)229let ghost flocq_exact (fm: format) (m: mode) (x: real) : unit230requires { F.generic (sb fm) (qmin fm) x }231ensures { flocq fm m x = x }232= {proof…}233let p = sb fm in234let q = qmin fm in235match m with236| RNE ->237assert { 1 < p };238assert { F.nearest p q x (F.rnd_ne p q x) };239assert { abs (F.rnd_ne p q x -. x) <=. abs (x -. x) }240| RNA ->241assert { 1 < p };242assert { F.nearest p q x (F.rnd_na p q x) };243assert { abs (F.rnd_na p q x -. x) <=. abs (x -. x) }244| RTN -> assert { F.rnd_dn p q x = x }245| RTP -> assert { F.rnd_up p q x = x }246| RTZ -> assert { F.rnd_dn p q x = x /\ F.rnd_up p q x = x }247end248{qed}249
The rounding of a real r >= 0
Valid (9.1s) (colibri2 18) (split_vc 5) (depth 4)let ghost flocq_pos (fm: format) (m: mode) (r: real) : unit252requires { 0.0 <=. r }253ensures { flocq fm m r = vom fm (round_mag fm m r) }254= {proof…}255let k = kdn fm r in256vom_generic fm k;257if pure { vom fm k = r } then flocq_exact fm m r258else begin259vom_generic fm (k + 1);260vom_zero fm; vom_mono fm 0 k; vom_lt fm k (k + 1);261let lo = pure { vom fm k } in262let hi = pure { vom fm (k + 1) } in263assert { forall g. F.generic (sb fm) (qmin fm) g -> g <=. lo \/ hi <=. g };264between_round (sb fm) (qmin fm) lo hi r;265if pure { F.even_repr (sb fm) (qmin fm) lo } then even_vom fm k;266if pure { F.even_repr (sb fm) (qmin fm) hi } then even_vom fm (k + 1);267assert { mod (k + 1) 2 = 0 -> mod k 2 <> 0 }268end269{qed}270
The rounding of a real r < 0
Valid (697ms) (colibri2 36) (split_vc 7) (depth 4)let ghost flocq_neg (fm: format) (m: mode) (r: real) : unit273requires { r <. 0.0 }274ensures { flocq fm m r = -. vom fm (round_mag fm (mirror m) (-. r)) }275= {proof…}276let k = kdn fm (-. r) in277vom_generic fm k;278generic_neg (sb fm) (qmin fm) (vom fm k);279if pure { vom fm k = -. r } then flocq_exact fm m r280else begin281vom_generic fm (k + 1);282generic_neg (sb fm) (qmin fm) (vom fm (k + 1));283vom_zero fm; vom_mono fm 0 k; vom_lt fm k (k + 1);284let lo = pure { -. vom fm (k + 1) } in285let hi = pure { -. vom fm k } in286assert { forall g. F.generic (sb fm) (qmin fm) g -> g <=. lo \/ hi <=. g287by F.generic (sb fm) (qmin fm) (-. g) };288between_round (sb fm) (qmin fm) lo hi r;289if pure { F.even_repr (sb fm) (qmin fm) hi } then begin290even_repr_neg (sb fm) (qmin fm) (vom fm k); even_vom fm k291end;292if pure { F.even_repr (sb fm) (qmin fm) lo } then begin293even_repr_neg (sb fm) (qmin fm) (vom fm (k + 1)); even_vom fm (k + 1)294end;295assert { mod (k + 1) 2 = 0 -> mod k 2 <> 0 };296let mid = pure { (vom fm k +. vom fm (k + 1)) /. 2.0 } in297assert { r -. lo <. hi -. r <-> mid <. -. r };298assert { hi -. r <. r -. lo <-> -. r <. mid };299assert { r -. lo = hi -. r <-> -. r = mid };300assert { abs hi <. abs lo };301match m with302| RNE -> assert { mirror m = RNE }303| RNA -> assert { mirror m = RNA }304| RTN -> assert { mirror m = RTP }305| RTP -> assert { mirror m = RTN }306| RTZ -> assert { mirror m = RTZ }307end308end309{qed}310
Valid (48ms) (colibri2)let ghost vom_max (fm: format) : unit314ensures { vom fm (nb_sign fm - 1) = pow2r (emax fm) }315ensures { 2 <= nb_sign fm - 1 }316= {proof…}317binade_ge_2 fm;318assert { power 2 (eb fm) = 2 * power 2 (eb fm - 1)319by power 2 (eb fm) = power 2 ((eb fm - 1) + 1) };320assert { 2 <= power 2 (eb fm - 1)321by power 2 (eb fm - 1) = 2 * power 2 (eb fm - 2)322by power 2 (eb fm - 1) = power 2 ((eb fm - 2) + 1) };323let u = pure { qmin fm + power 2 (eb fm) - 2 } in324vom_s fm u (binade fm);325assert { nb_sign fm - 1 = (u - qmin fm) * binade fm + binade fm };326pow2r_int (sb fm - 1); pow2r_add (sb fm - 1) u;327assert { sb fm - 1 + u = emax fm }328{qed}329
Valid (2.7s) (colibri2 17) (cvc4 5) (cvc5 10) (split_vc 9) (depth 5)let ghost round_fin_flocq (fm: format) (m: mode) (z: bool) (r: real) : unit333ensures { let x = round_fin fm m z r in334let f = flocq fm m r in335if abs f <. pow2r (emax fm) then336(exists ng k. x.value = Finite ng k) /\ to_real x = f337else x.value = overflow fm m (r <. 0.0) }338= {proof…}339vom_max fm; vom_zero fm;340let n = pure { nb_sign fm - 1 } in341let x = pure { round_fin fm m z r } in342if pure { 0.0 <=. r } then begin343flocq_pos fm m r;344let k = pure { round_mag fm m r } in345assert { 0 <= k };346if k = 0 then assert { x.value = Finite z 0 }347else if k < n then begin348vom_lt fm k n; vom_mono fm 0 k;349assert { abs (flocq fm m r) <. pow2r (emax fm) };350assert { x.value = Finite false k }351end else begin352vom_mono fm n k;353match m with354| RTN | RTZ -> assert { x.value = Finite false (nb_sign fm - 2) }355| _ -> assert { x.value = PlusInf }356end357end358end else begin359flocq_neg fm m r;360let k = pure { round_mag fm (mirror m) (-. r) } in361assert { 0 <= k };362if k = 0 then assert { x.value = Finite z 0 }363else if k < n then begin364vom_lt fm k n; vom_mono fm 0 k;365assert { abs (flocq fm m r) <. pow2r (emax fm) };366assert { x.value = Finite true k }367end else begin368vom_mono fm n k;369match m with370| RTP | RTZ -> assert { x.value = Finite true (nb_sign fm - 2) }371| _ -> assert { x.value = MinusInf }372end373end374end375{qed}376end377