library colibrilib.fbin — module Formatmodule Format19use int.Int20use int.Power21use int.EuclideanDivision22use real.RealInfix23use real.FromInt24use real.Truncate25use Pow2r26
eb bits of exponent, sb bits of significand (the hidden bit included)
type format = { eb: int; sb: int } Valid (18ms) (colibri2)30invariant { 1 < eb /\ 1 < sb }31by { eb = 2; sb = 2 }32
The number of significands in a binade
function binade (fm: format) : int = power 2 (sb fm - 1)35function bias (fm: format) : int = power 2 (eb fm - 1) - 136
The exponent of the last bit of the subnormals
function qmin (fm: format) : int = 2 - bias fm - sb fm38
The number of floats of each sign: the zero, the subnormals, the normals and the infinity
function nb_sign (fm: format) : int =42(power 2 (eb fm) - 1) * binade fm + 143
The value of the magnitude k (the encoding of a float without its sign): subnormal for the biased exponent div k (binade fm) = 0
function vom (fm: format) (k: int) : real =47let e = div k (binade fm) in48if e = 0 then from_int (mod k (binade fm)) *. pow2r (qmin fm)49else from_int (binade fm + mod k (binade fm)) *. pow2r (e - 1 + qmin fm)50Valid (37ms) (colibri2)51let ghost binade_ge_2 (fm: format) : unit52ensures { 2 <= binade fm }53= {proof…}54assert { power 2 (sb fm - 1) = 2 * power 2 (sb fm - 2) };55assert { 1 <= power 2 (sb fm - 2) }56{qed}57
The magnitude k is the significand s in the binade of the ulp 2^u
Valid (1.0s) (colibri2)let ghost vom_s (fm: format) (u s: int) : unit61requires { qmin fm <= u /\ 0 <= s < 2 * binade fm }62requires { qmin fm < u -> binade fm <= s }63ensures { vom fm ((u - qmin fm) * binade fm + s) = from_int s *. pow2r u }64= {proof…}65let p = binade fm in66let k = (u - qmin fm) * p + s in67binade_ge_2 fm;68if s < p then begin69assert { u = qmin fm };70assert { div k p = 0 /\ mod k p = s }71end else begin72assert { k = (u - qmin fm + 1) * p + (s - p) };73assert { div k p = u - qmin fm + 1 /\ mod k p = s - p }74end75{qed}76Valid (266ms) (colibri2 5) (cvc5) (split_vc) (depth 1)77let ghost vom_s_succ (fm: format) (u s: int) : unit78requires { qmin fm <= u /\ 0 <= s < 2 * binade fm }79requires { qmin fm < u -> binade fm <= s }80ensures { vom fm ((u - qmin fm) * binade fm + s + 1) = from_int (s + 1) *. pow2r u }81= {proof…}82let p = binade fm in83binade_ge_2 fm;84if s + 1 < 2 * p then vom_s fm u (s + 1)85else begin86vom_s fm (u + 1) p;87pow2r_succ u;88assert { (u - qmin fm) * p + s + 1 = (u + 1 - qmin fm) * p + p }89end90{qed}91
The ulp exponent and the significand of a magnitude
function uexp (fm: format) (k: int) : int =94let e = div k (binade fm) in qmin fm + (if e = 0 then 0 else e - 1)95function sig (fm: format) (k: int) : int = k - (uexp fm k - qmin fm) * binade fm96Valid (1.1s) (colibri2)97let ghost vom_dec (fm: format) (k: int) : unit98requires { 0 <= k }99ensures { qmin fm <= uexp fm k /\ 0 <= sig fm k < 2 * binade fm }100ensures { qmin fm < uexp fm k -> binade fm <= sig fm k }101ensures { k = (uexp fm k - qmin fm) * binade fm + sig fm k }102ensures { vom fm k = from_int (sig fm k) *. pow2r (uexp fm k) }103ensures { vom fm (k + 1) = from_int (sig fm k + 1) *. pow2r (uexp fm k) }104= {proof…}105binade_ge_2 fm;106let p = binade fm in107assert { k = div k p * p + mod k p };108vom_s fm (uexp fm k) (sig fm k);109vom_s_succ fm (uexp fm k) (sig fm k)110{qed}111Valid (17ms) (colibri2)112let ghost vom_zero (fm: format) : unit113ensures { vom fm 0 = 0.0 }114= {proof…} binade_ge_2 fm; assert { div 0 (binade fm) = 0 /\ mod 0 (binade fm) = 0 } {qed}115
The gap between two neighbours is at least 2^qmin
Valid (27ms) (cvc5)let ghost vom_step (fm: format) (k: int) : unit118requires { 0 <= k }119ensures { vom fm k +. pow2r (qmin fm) <=. vom fm (k + 1) }120= {proof…}121vom_dec fm k; pow2r_le (qmin fm) (uexp fm k)122{qed}123Valid (51ms) (colibri2)124let rec ghost vom_lt (fm: format) (k l: int) : unit125requires { 0 <= k < l }126ensures { vom fm k <. vom fm l }127variant { l - k }128= {proof…}129pow2r_pos (qmin fm); vom_step fm (l - 1);130if k < l - 1 then vom_lt fm k (l - 1)131{qed}132Valid (26ms) (colibri2 4) (cvc5) (split_vc 2) (depth 2)133let rec ghost vom_ge (fm: format) (k: int) : unit134requires { 0 <= k }135ensures { from_int k *. pow2r (qmin fm) <=. vom fm k }136variant { k }137= {proof…}138if k = 0 then vom_zero fm139else begin vom_ge fm (k - 1); vom_step fm (k - 1) end140{qed}141
predicate between (fm: format) (k: int) (r: real) =1450 <= k /\ vom fm k <=. r <. vom fm (k + 1)146Valid (24ms) (colibri2)147let rec ghost function find_between (fm: format) (r: real) (n: int) : int148requires { 0.0 <=. r /\ 0 <= n /\ r <. vom fm n }149ensures { between fm result r }150variant { n }151= {proof…} vom_zero fm; {qed}152if pure { vom fm (n - 1) <=. r } then n - 1153else find_between fm r (n - 1)154
The magnitude rounded down of r >= 0
Valid (29ms) (colibri2)let ghost function kdn (fm: format) (r: real) : int157requires { 0.0 <=. r }158ensures { between fm result r }159= let c = pow2r (qmin fm) in160let n = pure { Truncate.floor (r /. c) + 1 } in161{proof…}162pow2r_pos (qmin fm);163assert { r /. c <. from_int n };164assert { r <. from_int n *. c by r = (r /. c) *. c };165assert { 0 <= n };166vom_ge fm n;167{qed}168find_between fm r n169Valid (415ms) (colibri2 4) (split_vc) (depth 1)170let ghost kdn_unique (fm: format) (k: int) (r: real) : unit171requires { between fm k r }172ensures { kdn fm r = k }173= {proof…}174let j = kdn fm r in175if j < k then (if j + 1 < k then vom_lt fm (j + 1) k)176else if k < j then (if k + 1 < j then vom_lt fm (k + 1) j)177{qed}178end179