Common — library colibrilib.fbin — module Exact

The powers of 2 dividing the floats

The 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.

3944
module Exact
3945
use int.Int
3946
use int.Power
3947
use int.EuclideanDivision
3948
use real.RealInfix
3949
use real.FromInt
3950
use colibrilib.fp.Widen
3951
use colibrilib.fp.Ereal
3952
use colibrilib.dyadic.Dyadic as D
3953
use Pow2r
3954
use Format
3955
use Float
3956
use Round
3957
use Impl
3958
use AddBound

The exponent of the ulp of the largest finite float

  Valid (585ms) (colibri2 4) (cvc4) (split_vc) (depth 1)
3961
let ghost
umax_val
(fm: format) : unit
3962
ensures { umax fm = qmin fm + power 2 fm.eb - 3 }
3963
= {proof…}
3964
binade_ge_2 fm; nb_sign_ge fm;
3965
let b = binade fm in
3966
assert { power 2 fm.eb = 2 * power 2 (fm.eb - 1) };
3967
assert { power 2 (fm.eb - 1) >= 2 by power 2 (fm.eb - 1) = 2 * power 2 (fm.eb - 2) /\ power 2 (fm.eb - 2) >= 1 };
3968
assert { nb_sign fm - 2 = (power 2 fm.eb - 2) * b + (b - 1) };
3969
assert { div (nb_sign fm - 2) b = power 2 fm.eb - 2 }
3970
{qed}

The significand and the exponent of a finite float, (0, 0) for the others

  Valid (49ms) (colibri2)
3974
let
dyadic_of
(x: t) : (int, int)
3975
ensures { let (n, e) = result in is_finite x -> to_real x = from_int n *. pow2r e }
3976
= match x.value with
3977
| Finite _ _ -> let d = to_dyadic x in (d.dm, d.de)
3978
| _ -> (0, 0)
3979
end
3980
Valid (572ms) (colibri2 9) (cvc5 2) (split_vc) (depth 1)
3981
let ghost
float_dyadic
(x: t) : unit
3982
requires { not is_nan x /\ not is_plus_infinity x /\ not is_minus_infinity x }
3983
ensures { D.fix (to_real x) (qmin x.fmt) /\ D.flt (to_real x) x.fmt.sb }
3984
= {proof…}
3985
let fm = x.fmt in
3986
match x.value with
3987
| Finite ng k ->
3988
vom_mult fm k; vom_dec fm k;
3989
mult_le (vom fm k) (qmin fm) (uexp fm k);
3990
let n = any int ensures { vom fm k = from_int result *. pow2r (qmin fm) } in
3991
assert { power 2 fm.sb = 2 * binade fm };
3992
if ng then begin
3993
assert { to_real x = from_int (- n) *. pow2r (qmin fm) };
3994
assert { to_real x = from_int (- sig fm k) *. pow2r (uexp fm k) }
3995
end else begin
3996
assert { to_real x = from_int n *. pow2r (qmin fm) };
3997
assert { to_real x = from_int (sig fm k) *. pow2r (uexp fm k) }
3998
end
3999
| _ -> absurd
4000
end
4001
{qed}
4002
Valid (92ms) (colibri2)
4003
let ghost
round_fix
(fm: format) (m: mode) (z: bool) (r: real) (e: int) : unit
4004
requires { D.fix r e /\ e <= qmin fm + power 2 fm.eb - 3 }
4005
requires { not is_plus_infinity (round_f fm m z (Fin r)) }
4006
requires { not is_minus_infinity (round_f fm m z (Fin r)) }
4007
ensures { D.fix (to_real (round_f fm m z (Fin r))) e }
4008
= {proof…}
4009
umax_val fm; round_fin_facts fm m z r;
4010
assert { mult r e };
4011
assert { is_finite (round_fin fm m z r) };
4012
round_fin_mult fm m z r e
4013
{qed}
4014
Valid (1.1s) (colibri2 15) (cvc5) (split_vc) (depth 1)
4015
let ghost
round_zero_small
(fm: format) (m: mode) (z: bool) (r: real) : unit
4016
requires { r <> 0.0 /\ is_zero (round_f fm m z (Fin r)) }
4017
ensures { -. pow2r (qmin fm) <. r <. pow2r (qmin fm) }
4018
= {proof…}
4019
binade_ge_2 fm; nb_sign_ge fm;
4020
vom_s fm (qmin fm) 1;
4021
assert { vom fm 1 = pow2r (qmin fm) };
4022
let f1 = round_fin fm m z (vom fm 1) in
4023
round_mag_exact fm m 1; round_mag_exact fm (mirror m) 1;
4024
if pure { pow2r (qmin fm) <=. r } then begin
4025
assert { 0.0 <=. vom fm 1 };
4026
assert { f1.value = Finite false 1 };
4027
round_fin_le fm m z z (vom fm 1) r;
4028
absurd
4029
end;
4030
if pure { r <=. -. pow2r (qmin fm) } then begin
4031
let g1 = round_fin fm m z (-. vom fm 1) in
4032
pow2r_pos (qmin fm);
4033
assert { -. (-. vom fm 1) = vom fm 1 };
4034
assert { g1.value = Finite true 1 };
4035
round_fin_le fm m z z r (-. vom fm 1);
4036
absurd
4037
end
4038
{qed}
4039
Valid (3.2s) (colibri2) (split_vc) (depth 1)
4040
let ghost
max_float_ge
(fm: format) : unit
4041
ensures { pow2r (qmin fm + power 2 fm.eb - 3 + fm.sb - 1) <=.
4042
to_real (of_index fm (nb_sign fm - 2)) }
4043
= {proof…}
4044
umax_val fm;
4045
pow2r_add (uexp fm (nb_sign fm - 2)) (fm.sb - 1)
4046
{qed}

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)
4050
let ghost
double_mag
(fm: format) (k: int) : unit
4051
requires { 0 <= k <= nb_sign fm - 2 /\ vom fm (nb_sign fm - 2) <. 2.0 *. vom fm k }
4052
ensures { vom fm (nb_sign fm - 1) <=. 2.0 *. vom fm k }
4053
= {proof…}
4054
nb_sign_ge fm; binade_ge_2 fm; umax_val fm;
4055
let mx = nb_sign fm - 2 in
4056
let b = binade fm in
4057
vom_dec fm mx; vom_dec fm k; uexp_mono fm k mx;
4058
let um = uexp fm mx in
4059
assert { um - qmin fm = power 2 fm.eb - 3 };
4060
assert { mx = (um - qmin fm) * b + (2 * b - 1) };
4061
assert { sig fm mx = 2 * b - 1 };
4062
let u = uexp fm k in
4063
let s = sig fm k in
4064
pow2r_pos u; pow2r_pos um;
4065
if u = um then begin
4066
assert { 2.0 *. vom fm k = from_int (2 * s) *. pow2r um };
4067
scale_cmp (2 * b - 1) (2 * s) (pow2r um);
4068
assert { 2 * b <= 2 * s };
4069
scale_cmp (2 * b) (2 * s) (pow2r um)
4070
end else begin
4071
pow2r_succ u; pow2r_le (u + 1) um;
4072
assert { 2.0 *. vom fm k = from_int s *. pow2r (u + 1) };
4073
scale_cmp s (2 * b - 1) (pow2r (u + 1));
4074
assert { from_int s *. pow2r (u + 1) <=. from_int (2 * b - 1) *. pow2r (u + 1) };
4075
assert { from_int (2 * b - 1) *. pow2r (u + 1) <=. from_int (2 * b - 1) *. pow2r um };
4076
absurd
4077
end
4078
{qed}

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)
4083
let ghost
near_double
(m: mode) (z: bool) (x: t) (r: real) : unit
4084
requires { m = RNE \/ m = RNA }
4085
requires { not is_nan x /\ not is_plus_infinity x /\ not is_minus_infinity x }
4086
ensures { 2.0 *. to_real x <=. r ->
4087
not is_plus_infinity (round_f x.fmt m z (Fin r)) ->
4088
2.0 *. to_real x <=. to_real (of_index x.fmt (nb_sign x.fmt - 2)) }
4089
ensures { r <=. 2.0 *. to_real x ->
4090
not is_minus_infinity (round_f x.fmt m z (Fin r)) ->
4091
-. to_real (of_index x.fmt (nb_sign x.fmt - 2)) <=. 2.0 *. to_real x }
4092
= {proof…}
4093
let fm = x.fmt in
4094
nb_sign_ge fm; binade_ge_2 fm; vom_zero fm;
4095
let mx = nb_sign fm - 2 in
4096
vom_le fm 0 mx;
4097
assert { to_real (of_index fm mx) = vom fm mx };
4098
assert { mirror m = m };
4099
match x.value with
4100
| Finite ng k ->
4101
vom_le fm 0 k;
4102
if pure { vom fm mx <. 2.0 *. vom fm k } then begin
4103
double_mag fm k;
4104
let t = vom fm (mx + 1) in
4105
round_mag_exact fm m (mx + 1);
4106
vom_le fm 0 (mx + 1);
4107
if not ng then begin
4108
if pure { 2.0 *. to_real x <=. r } then begin
4109
round_mag_mono fm m t r;
4110
assert { round_mag fm m r >= mx + 1 };
4111
assert { 0.0 <=. r by to_real x = vom fm k };
4112
assert { round_fin fm m z r = mk fm PlusInf };
4113
assert { is_plus_infinity (round_fin fm m z r) }
4114
end
4115
end else begin
4116
if pure { r <=. 2.0 *. to_real x } then begin
4117
round_mag_mono fm m t (-. r);
4118
assert { round_mag fm m (-. r) >= mx + 1 };
4119
assert { r <. 0.0 by to_real x = -. vom fm k };
4120
assert { round_fin fm m z r = mk fm MinusInf };
4121
assert { is_minus_infinity (round_fin fm m z r) }
4122
end
4123
end
4124
end
4125
| _ -> absurd
4126
end
4127
{qed}
4128
Valid (786ms) (colibri2 20) (cvc5 7) (split_vc 6) (depth 4)
4129
let ghost
dyadic_exact
(fm: format) (r: real) : t
4130
requires { D.fix r (qmin fm) /\ D.flt r fm.sb }
4131
requires { -. to_real (of_index fm (nb_sign fm - 2)) <=. r <=.
4132
to_real (of_index fm (nb_sign fm - 2)) }
4133
ensures { result.fmt = fm /\ not is_nan result /\ ext result = Fin r }
4134
= {proof…}
4135
nb_sign_ge fm; binade_ge_2 fm; vom_zero fm;
4136
let mx = nb_sign fm - 2 in
4137
assert { to_real (of_index fm mx) = vom fm mx };
4138
if pure { r = 0.0 } then mk fm (Finite false 0)
4139
else begin
4140
let n = any int ensures { r = from_int result *. pow2r (qmin fm) } in
4141
let m = any int ensures { exists e. r = from_int result *. pow2r e /\
4142
- power 2 fm.sb < result < power 2 fm.sb } in
4143
let e = any int ensures { r = from_int m *. pow2r result } in
4144
let an = if n < 0 then - n else n in
4145
let am = if m < 0 then - m else m in
4146
let ar = if pure { r <. 0.0 } then -. r else r in
4147
pow2r_pos (qmin fm); pow2r_pos e;
4148
assert { ar = from_int an *. pow2r (qmin fm) };
4149
assert { ar = from_int am *. pow2r e };
4150
assert { 1 <= an /\ 1 <= am };
4151
assert { power 2 fm.sb = 2 * binade fm };
4152
let (s, u) =
4153
if qmin fm <= e then (am, e)
4154
else begin
4155
(* r = n 2^qmin = m 2^e with e < qmin: |n| <= |m| *)
4156
pow2r_add e (qmin fm - e); pow2r_int (qmin fm - e);
4157
assert { 1 <= power 2 (qmin fm - e) };
4158
assert { from_int an *. pow2r (qmin fm) =
4159
(from_int an *. from_int (power 2 (qmin fm - e))) *. pow2r e };
4160
assert { from_int am = from_int an *. from_int (power 2 (qmin fm - e)) };
4161
assert { am = an * power 2 (qmin fm - e) };
4162
assert { an <= am };
4163
(an, qmin fm)
4164
end in
4165
let k = mag_of_dy fm s u in
4166
assert { vom fm k = ar };
4167
if mx < k then begin vom_lt fm mx k; absurd end;
4168
let x = mk fm (Finite (pure { r <. 0.0 }) k) in
4169
assert { to_real x = r };
4170
x
4171
end
4172
{qed}
4173
end