library colibrilib.fbin — module ExactThe facts of fp.Intf on colibrilib/dyadic.mlw: FIX and FLT of the floats, the rounding keeps FIX, the reals that round to zero, and the dyadic numbers that are floats.
module Exact3944use int.Int3945use int.Power3946use int.EuclideanDivision3947use real.RealInfix3948use real.FromInt3949use colibrilib.fp.Widen3950use colibrilib.fp.Ereal3951use colibrilib.dyadic.Dyadic as D3952use Pow2r3953use Format3954use Float3955use Round3956use Impl3957use AddBound3958
The exponent of the ulp of the largest finite float
Valid (585ms) (colibri2 4) (cvc4) (split_vc) (depth 1)let ghost umax_val (fm: format) : unit3961ensures { umax fm = qmin fm + power 2 fm.eb - 3 }3962= {proof…}3963binade_ge_2 fm; nb_sign_ge fm;3964let b = binade fm in3965assert { power 2 fm.eb = 2 * power 2 (fm.eb - 1) };3966assert { power 2 (fm.eb - 1) >= 2 by power 2 (fm.eb - 1) = 2 * power 2 (fm.eb - 2) /\ power 2 (fm.eb - 2) >= 1 };3967assert { nb_sign fm - 2 = (power 2 fm.eb - 2) * b + (b - 1) };3968assert { div (nb_sign fm - 2) b = power 2 fm.eb - 2 }3969{qed}3970
The significand and the exponent of a finite float, (0, 0) for the others
Valid (49ms) (colibri2)let dyadic_of (x: t) : (int, int)3974ensures { let (n, e) = result in is_finite x -> to_real x = from_int n *. pow2r e }3975= match x.value with3976| Finite _ _ -> let d = to_dyadic x in (d.dm, d.de)3977| _ -> (0, 0)3978end3979Valid (572ms) (colibri2 9) (cvc5 2) (split_vc) (depth 1)3980let ghost float_dyadic (x: t) : unit3981requires { not is_nan x /\ not is_plus_infinity x /\ not is_minus_infinity x }3982ensures { D.fix (to_real x) (qmin x.fmt) /\ D.flt (to_real x) x.fmt.sb }3983= {proof…}3984let fm = x.fmt in3985match x.value with3986| Finite ng k ->3987vom_mult fm k; vom_dec fm k;3988mult_le (vom fm k) (qmin fm) (uexp fm k);3989let n = any int ensures { vom fm k = from_int result *. pow2r (qmin fm) } in3990assert { power 2 fm.sb = 2 * binade fm };3991if ng then begin3992assert { to_real x = from_int (- n) *. pow2r (qmin fm) };3993assert { to_real x = from_int (- sig fm k) *. pow2r (uexp fm k) }3994end else begin3995assert { to_real x = from_int n *. pow2r (qmin fm) };3996assert { to_real x = from_int (sig fm k) *. pow2r (uexp fm k) }3997end3998| _ -> absurd3999end4000{qed}4001Valid (92ms) (colibri2)4002let ghost round_fix (fm: format) (m: mode) (z: bool) (r: real) (e: int) : unit4003requires { D.fix r e /\ e <= qmin fm + power 2 fm.eb - 3 }4004requires { not is_plus_infinity (round_f fm m z (Fin r)) }4005requires { not is_minus_infinity (round_f fm m z (Fin r)) }4006ensures { D.fix (to_real (round_f fm m z (Fin r))) e }4007= {proof…}4008umax_val fm; round_fin_facts fm m z r;4009assert { mult r e };4010assert { is_finite (round_fin fm m z r) };4011round_fin_mult fm m z r e4012{qed}4013Valid (1.1s) (colibri2 15) (cvc5) (split_vc) (depth 1)4014let ghost round_zero_small (fm: format) (m: mode) (z: bool) (r: real) : unit4015requires { r <> 0.0 /\ is_zero (round_f fm m z (Fin r)) }4016ensures { -. pow2r (qmin fm) <. r <. pow2r (qmin fm) }4017= {proof…}4018binade_ge_2 fm; nb_sign_ge fm;4019vom_s fm (qmin fm) 1;4020assert { vom fm 1 = pow2r (qmin fm) };4021let f1 = round_fin fm m z (vom fm 1) in4022round_mag_exact fm m 1; round_mag_exact fm (mirror m) 1;4023if pure { pow2r (qmin fm) <=. r } then begin4024assert { 0.0 <=. vom fm 1 };4025assert { f1.value = Finite false 1 };4026round_fin_le fm m z z (vom fm 1) r;4027absurd4028end;4029if pure { r <=. -. pow2r (qmin fm) } then begin4030let g1 = round_fin fm m z (-. vom fm 1) in4031pow2r_pos (qmin fm);4032assert { -. (-. vom fm 1) = vom fm 1 };4033assert { g1.value = Finite true 1 };4034round_fin_le fm m z z r (-. vom fm 1);4035absurd4036end4037{qed}4038Valid (3.2s) (colibri2) (split_vc) (depth 1)4039let ghost max_float_ge (fm: format) : unit4040ensures { pow2r (qmin fm + power 2 fm.eb - 3 + fm.sb - 1) <=.4041to_real (of_index fm (nb_sign fm - 2)) }4042= {proof…}4043umax_val fm;4044pow2r_add (uexp fm (nb_sign fm - 2)) (fm.sb - 1)4045{qed}4046
Twice a magnitude above the largest finite float reaches the magnitude of the infinity (the top binade has the ulp 2^umax)
Valid (793ms) (colibri2 17) (split_vc) (depth 1)let ghost double_mag (fm: format) (k: int) : unit4050requires { 0 <= k <= nb_sign fm - 2 /\ vom fm (nb_sign fm - 2) <. 2.0 *. vom fm k }4051ensures { vom fm (nb_sign fm - 1) <=. 2.0 *. vom fm k }4052= {proof…}4053nb_sign_ge fm; binade_ge_2 fm; umax_val fm;4054let mx = nb_sign fm - 2 in4055let b = binade fm in4056vom_dec fm mx; vom_dec fm k; uexp_mono fm k mx;4057let um = uexp fm mx in4058assert { um - qmin fm = power 2 fm.eb - 3 };4059assert { mx = (um - qmin fm) * b + (2 * b - 1) };4060assert { sig fm mx = 2 * b - 1 };4061let u = uexp fm k in4062let s = sig fm k in4063pow2r_pos u; pow2r_pos um;4064if u = um then begin4065assert { 2.0 *. vom fm k = from_int (2 * s) *. pow2r um };4066scale_cmp (2 * b - 1) (2 * s) (pow2r um);4067assert { 2 * b <= 2 * s };4068scale_cmp (2 * b) (2 * s) (pow2r um)4069end else begin4070pow2r_succ u; pow2r_le (u + 1) um;4071assert { 2.0 *. vom fm k = from_int s *. pow2r (u + 1) };4072scale_cmp s (2 * b - 1) (pow2r (u + 1));4073assert { from_int s *. pow2r (u + 1) <=. from_int (2 * b - 1) *. pow2r (u + 1) };4074assert { from_int (2 * b - 1) *. pow2r (u + 1) <=. from_int (2 * b - 1) *. pow2r um };4075absurd4076end4077{qed}4078
In round to nearest, a real at least 2 x, x a finite float, rounds below the infinity only when 2 x is at most the largest finite float; the same on the negative side
Valid (865ms) (colibri2 12) (cvc4 4) (cvc5 4) (split_vc) (depth 1)let ghost near_double (m: mode) (z: bool) (x: t) (r: real) : unit4083requires { m = RNE \/ m = RNA }4084requires { not is_nan x /\ not is_plus_infinity x /\ not is_minus_infinity x }4085ensures { 2.0 *. to_real x <=. r ->4086not is_plus_infinity (round_f x.fmt m z (Fin r)) ->40872.0 *. to_real x <=. to_real (of_index x.fmt (nb_sign x.fmt - 2)) }4088ensures { r <=. 2.0 *. to_real x ->4089not is_minus_infinity (round_f x.fmt m z (Fin r)) ->4090-. to_real (of_index x.fmt (nb_sign x.fmt - 2)) <=. 2.0 *. to_real x }4091= {proof…}4092let fm = x.fmt in4093nb_sign_ge fm; binade_ge_2 fm; vom_zero fm;4094let mx = nb_sign fm - 2 in4095vom_le fm 0 mx;4096assert { to_real (of_index fm mx) = vom fm mx };4097assert { mirror m = m };4098match x.value with4099| Finite ng k ->4100vom_le fm 0 k;4101if pure { vom fm mx <. 2.0 *. vom fm k } then begin4102double_mag fm k;4103let t = vom fm (mx + 1) in4104round_mag_exact fm m (mx + 1);4105vom_le fm 0 (mx + 1);4106if not ng then begin4107if pure { 2.0 *. to_real x <=. r } then begin4108round_mag_mono fm m t r;4109assert { round_mag fm m r >= mx + 1 };4110assert { 0.0 <=. r by to_real x = vom fm k };4111assert { round_fin fm m z r = mk fm PlusInf };4112assert { is_plus_infinity (round_fin fm m z r) }4113end4114end else begin4115if pure { r <=. 2.0 *. to_real x } then begin4116round_mag_mono fm m t (-. r);4117assert { round_mag fm m (-. r) >= mx + 1 };4118assert { r <. 0.0 by to_real x = -. vom fm k };4119assert { round_fin fm m z r = mk fm MinusInf };4120assert { is_minus_infinity (round_fin fm m z r) }4121end4122end4123end4124| _ -> absurd4125end4126{qed}4127Valid (786ms) (colibri2 20) (cvc5 7) (split_vc 6) (depth 4)4128let ghost dyadic_exact (fm: format) (r: real) : t4129requires { D.fix r (qmin fm) /\ D.flt r fm.sb }4130requires { -. to_real (of_index fm (nb_sign fm - 2)) <=. r <=.4131to_real (of_index fm (nb_sign fm - 2)) }4132ensures { result.fmt = fm /\ not is_nan result /\ ext result = Fin r }4133= {proof…}4134nb_sign_ge fm; binade_ge_2 fm; vom_zero fm;4135let mx = nb_sign fm - 2 in4136assert { to_real (of_index fm mx) = vom fm mx };4137if pure { r = 0.0 } then mk fm (Finite false 0)4138else begin4139let n = any int ensures { r = from_int result *. pow2r (qmin fm) } in4140let m = any int ensures { exists e. r = from_int result *. pow2r e /\4141- power 2 fm.sb < result < power 2 fm.sb } in4142let e = any int ensures { r = from_int m *. pow2r result } in4143let an = if n < 0 then - n else n in4144let am = if m < 0 then - m else m in4145let ar = if pure { r <. 0.0 } then -. r else r in4146pow2r_pos (qmin fm); pow2r_pos e;4147assert { ar = from_int an *. pow2r (qmin fm) };4148assert { ar = from_int am *. pow2r e };4149assert { 1 <= an /\ 1 <= am };4150assert { power 2 fm.sb = 2 * binade fm };4151let (s, u) =4152if qmin fm <= e then (am, e)4153else begin4154(* r = n 2^qmin = m 2^e with e < qmin: |n| <= |m| *)4155pow2r_add e (qmin fm - e); pow2r_int (qmin fm - e);4156assert { 1 <= power 2 (qmin fm - e) };4157assert { from_int an *. pow2r (qmin fm) =4158(from_int an *. from_int (power 2 (qmin fm - e))) *. pow2r e };4159assert { from_int am = from_int an *. from_int (power 2 (qmin fm - e)) };4160assert { am = an * power 2 (qmin fm - e) };4161assert { an <= am };4162(an, qmin fm)4163end in4164let k = mag_of_dy fm s u in4165assert { vom fm k = ar };4166if mx < k then begin vom_lt fm mx k; absurd end;4167let x = mk fm (Finite (pure { r <. 0.0 }) k) in4168assert { to_real x = r };4169x4170end4171{qed}4172end4173