library colibrilib.fbin — module Roundmodule Round260use int.Int261use int.Power262use int.EuclideanDivision263use real.RealInfix264use real.FromInt265use colibrilib.fp.Widen266use colibrilib.fp.Ereal as E267use colibrilib.zarith.Zbit268use colibrilib.zbit.ZbitInt269use Pow2r270use Format271use Float272
dm * 2^de
type dyadic = { dm: int; de: int }275276function dval (d: dyadic) : real = from_int d.dm *. pow2r d.de277Valid (22ms) (colibri2)278let pow2_int (n: int) : int279requires { 0 <= n }280ensures { result = power 2 n }281= {proof…} lsl_mul 1 n; {qed} lsl_int 1 n282Valid (30ms) (colibri2)283let binade_p (fm: format) : int284ensures { result = binade fm }285= pow2_int (fm.sb - 1)286Valid (24ms) (colibri2)287let nb_sign_p (fm: format) : int288ensures { result = nb_sign fm }289= (pow2_int fm.eb - 1) * binade_p fm + 1290Valid (29ms) (colibri2)291let qmin_p (fm: format) : int292ensures { result = qmin fm }293= 2 - (pow2_int (fm.eb - 1) - 1) - fm.sb294Valid (20ms) (colibri2 2) (split_vc) (depth 1)295let ghost mul_lt_cancel (x y c: int) : unit296requires { 0 < c /\ x * c < y * c + c }297ensures { x <= y }298= {proof…} if x > y then assert { x * c >= (y + 1) * c } {qed}299
The parity, by the lowest bit
Valid (32ms) (colibri2)let even (k: int) : bool302ensures { result <-> mod k 2 = 0 }303= {proof…}304let ghost h = div k 2 in305if mod k 2 = 0 then begin assert { k = 2 * h }; even_bittest h 0 end306else begin assert { k = 2 * h + 1 }; odd_bittest h 0 end;307{qed}308not (test_bit k 0)309
The rounding of a * 2^e, a > 0, on the magnitudes
Valid (977ms) (colibri2 59) (cvc4 2) (cvc5 4) (split_vc 6) (depth 3)let round_mag_d (fm: format) (m: mode) (a e: int) : int312requires { 0 < a }313ensures { result = round_mag fm m (from_int a *. pow2r e) }314= let p = binade_p fm in315let q = qmin_p fm in316let nb = numbits a in317let u = if nb - fm.sb + e < q then q else nb - fm.sb + e in318let ghost r = pure { from_int a *. pow2r e } in319{proof…}320binade_ge_2 fm;321numbits_lsl_lt a; numbits_lsl_le a;322lsl_mul 1 nb; lsl_mul 1 (nb - 1);323assert { power 2 nb = 2 * power 2 (nb - 1) };324assert { power 2 (nb - 1) <= a < power 2 nb };325{qed}326if u <= e then begin327let s = lsl_int a (e - u) in328{proof…}329lsl_mul a (e - u);330assert { power 2 (e - u + nb) = power 2 (e - u) * power 2 nb };331assert { s < 2 * p by332s < power 2 (e - u) * power 2 nb = power 2 (e - u + nb)333/\ e - u + nb <= fm.sb /\ power 2 fm.sb = 2 * p334/\ power 2 (e - u + nb) <= power 2 fm.sb };335assert { q < u -> p <= s by336u = nb - fm.sb + e337so power 2 (e - u) * power 2 (nb - 1) = power 2 (e - u + nb - 1) = p };338let k = (u - q) * p + s in339vom_s fm u s; vom_s_succ fm u s;340pow2r_add u (e - u); pow2r_int (e - u); pow2r_pos u;341assert { vom fm k = r };342assert { vom fm (k + 1) = from_int (s + 1) *. pow2r u };343scale_cmp s (s + 1) (pow2r u);344kdn_unique fm k r;345{qed}346(u - q) * p + s347end else begin348let sh = u - e in349let s = asr_int a sh in350let pw = pow2_int sh in351let rem = a - s * pw in352let k = (u - q) * p + s in353{proof…}354asr_div a sh;355assert { 0 <= rem < pw /\ a = s * pw + rem };356assert { power 2 fm.sb = 2 * p };357assert { power 2 (sh + fm.sb) = pw * (2 * p) };358assert { power 2 nb <= power 2 (sh + fm.sb) };359mul_lt_cancel s (2 * p - 1) pw;360if pure { q < u } then begin361assert { power 2 (sh + fm.sb - 1) = pw * p };362assert { power 2 (sh + fm.sb - 1) = power 2 (nb - 1) };363mul_lt_cancel p s pw364end;365vom_s fm u s; vom_s_succ fm u s;366pow2r_add e sh; pow2r_int sh; pow2r_pos e;367let ghost c = pure { pow2r e } in368assert { vom fm k = from_int (s * pw) *. c };369assert { vom fm (k + 1) = from_int (s * pw + pw) *. c };370assert { r = from_int (s * pw + rem) *. c };371scale_cmp (s * pw) (s * pw + rem) c;372scale_cmp (s * pw + rem) (s * pw + pw) c;373kdn_unique fm k r;374{qed}375if rem = 0 then k376else match m with377| RTN | RTZ -> k378| RTP -> k + 1379| RNE | RNA ->380let h = pow2_int (sh - 1) in381{proof…}382assert { pw = 2 * h };383assert { (vom fm k +. vom fm (k + 1)) /. 2.0 = from_int (s * pw + h) *. c };384scale_cmp (s * pw + rem) (s * pw + h) c;385{qed}386if rem < h then k387else if rem > h then k + 1388else match m with RNA -> k + 1 | _ -> if even k then k else k + 1 end389end390end391Valid (59ms) (colibri2)392let of_mag_p (fm: format) (m: mode) (neg: bool) (k: int) : t393requires { 0 <= k }394ensures { result = of_mag fm m neg k }395= let nb = nb_sign_p fm in396if k < nb - 1 then mk fm (Finite neg k)397else match m with398| RTN | RTZ -> {proof…} binade_ge_2 fm; assert { 1 <= power 2 fm.eb - 1 }; {qed}399mk fm (Finite neg (nb - 2))400| _ -> mk fm (if neg then MinusInf else PlusInf)401end402
The rounding of a dyadic number
Valid (939ms) (colibri2 14) (cvc5) (split_vc) (depth 1)let round_d (fm: format) (m: mode) (zneg: bool) (d: dyadic) : t405ensures { result = round_f fm m zneg (E.Fin (dval d)) }406= {proof…} binade_ge_2 fm; {qed}407if d.dm = 0 then begin408{proof…}409vom_zero fm; pow2r_pos 1;410vom_lt fm 0 1;411assert { between fm 0 0.0 };412kdn_unique fm 0 0.0;413assert { dval d = 0.0 };414{qed}415mk fm (Finite zneg 0)416end else if d.dm > 0 then begin417let k = round_mag_d fm m d.dm d.de in418{proof…}419pow2r_pos d.de; let _ = kdn fm (dval d) in ();420{qed}421if k = 0 then mk fm (Finite zneg 0) else of_mag_p fm m false k422end else begin423let k = round_mag_d fm (mirror m) (- d.dm) d.de in424{proof…}425pow2r_pos d.de; let _ = kdn fm (-. dval d) in ();426assert { -. dval d = from_int (- d.dm) *. pow2r d.de };427{qed}428if k = 0 then mk fm (Finite zneg 0) else of_mag_p fm (mirror m) true k429end430
The exact operations on dyadic numbers
Valid (32ms) (colibri2)let dadd (a b: dyadic) : dyadic433ensures { dval result = dval a +. dval b }434= if a.de <= b.de then begin435{proof…}436lsl_mul b.dm (b.de - a.de); pow2r_add a.de (b.de - a.de); pow2r_int (b.de - a.de);437{qed}438{ dm = a.dm + lsl_int b.dm (b.de - a.de); de = a.de }439end else begin440{proof…}441lsl_mul a.dm (a.de - b.de); pow2r_add b.de (a.de - b.de); pow2r_int (a.de - b.de);442{qed}443{ dm = lsl_int a.dm (a.de - b.de) + b.dm; de = b.de }444end445Valid (21ms) (colibri2)446let dmul (a b: dyadic) : dyadic447ensures { dval result = dval a *. dval b }448= {proof…} pow2r_add a.de b.de; {qed}449{ dm = a.dm * b.dm; de = a.de + b.de }450451predicate is_finite (x: t) = match x.value with Finite _ _ -> true | _ -> false end452
The dyadic number of a finite float: its significand and the exponent of its ulp
Valid (46ms) (colibri2 9) (cvc5) (split_vc 3) (depth 3)let to_dyadic (x: t) : dyadic456requires { is_finite x }457ensures { dval result = to_real x }458= match x.value with459| Finite neg k ->460let fm = x.fmt in461let p = binade_p fm in462let q = qmin_p fm in463let e = asr_int k (fm.sb - 1) in464{proof…} asr_div k (fm.sb - 1); {qed}465let s = k - e * p in466let u = if e = 0 then q else e - 1 + q in467let sg = if e = 0 then s else p + s in468{proof…}469binade_ge_2 fm;470assert { e = div k p /\ s = mod k p };471assert { vom fm k = from_int sg *. pow2r u };472assert { from_int (- sg) *. pow2r u = -. (from_int sg *. pow2r u) };473assert { to_real x = if neg then -. vom fm k else vom fm k };474{qed}475{ dm = if neg then - sg else sg; de = u }476| _ -> absurd477end478end479