Common — library colibrilib.fbin — module Format

Formats and the values of the magnitudes

19
module Format
20
use int.Int
21
use int.Power
22
use int.EuclideanDivision
23
use real.RealInfix
24
use real.FromInt
25
use real.Truncate
26
use Pow2r

eb bits of exponent, sb bits of significand (the hidden bit included)

30
type
format
= {
eb
: int;
sb
: int } Valid (18ms) (colibri2)
31
invariant { 1 < eb /\ 1 < sb }
32
by { eb = 2; sb = 2 }

The number of significands in a binade

35
function
binade
(fm: format) : int = power 2 (sb fm - 1)
36
function
bias
(fm: format) : int = power 2 (eb fm - 1) - 1

The exponent of the last bit of the subnormals

38
function
qmin
(fm: format) : int = 2 - bias fm - sb fm

The number of floats of each sign: the zero, the subnormals, the normals and the infinity

42
function
nb_sign
(fm: format) : int =
43
(power 2 (eb fm) - 1) * binade fm + 1

The value of the magnitude k (the encoding of a float without its sign): subnormal for the biased exponent div k (binade fm) = 0

47
function
vom
(fm: format) (k: int) : real =
48
let e = div k (binade fm) in
49
if e = 0 then from_int (mod k (binade fm)) *. pow2r (qmin fm)
50
else from_int (binade fm + mod k (binade fm)) *. pow2r (e - 1 + qmin fm)
51
Valid (37ms) (colibri2)
52
let ghost
binade_ge_2
(fm: format) : unit
53
ensures { 2 <= binade fm }
54
= {proof…}
55
assert { power 2 (sb fm - 1) = 2 * power 2 (sb fm - 2) };
56
assert { 1 <= power 2 (sb fm - 2) }
57
{qed}

The magnitude k is the significand s in the binade of the ulp 2^u

  Valid (1.0s) (colibri2)
61
let ghost
vom_s
(fm: format) (u s: int) : unit
62
requires { qmin fm <= u /\ 0 <= s < 2 * binade fm }
63
requires { qmin fm < u -> binade fm <= s }
64
ensures { vom fm ((u - qmin fm) * binade fm + s) = from_int s *. pow2r u }
65
= {proof…}
66
let p = binade fm in
67
let k = (u - qmin fm) * p + s in
68
binade_ge_2 fm;
69
if s < p then begin
70
assert { u = qmin fm };
71
assert { div k p = 0 /\ mod k p = s }
72
end else begin
73
assert { k = (u - qmin fm + 1) * p + (s - p) };
74
assert { div k p = u - qmin fm + 1 /\ mod k p = s - p }
75
end
76
{qed}
77
Valid (266ms) (colibri2 5) (cvc5) (split_vc) (depth 1)
78
let ghost
vom_s_succ
(fm: format) (u s: int) : unit
79
requires { qmin fm <= u /\ 0 <= s < 2 * binade fm }
80
requires { qmin fm < u -> binade fm <= s }
81
ensures { vom fm ((u - qmin fm) * binade fm + s + 1) = from_int (s + 1) *. pow2r u }
82
= {proof…}
83
let p = binade fm in
84
binade_ge_2 fm;
85
if s + 1 < 2 * p then vom_s fm u (s + 1)
86
else begin
87
vom_s fm (u + 1) p;
88
pow2r_succ u;
89
assert { (u - qmin fm) * p + s + 1 = (u + 1 - qmin fm) * p + p }
90
end
91
{qed}

The ulp exponent and the significand of a magnitude

94
function
uexp
(fm: format) (k: int) : int =
95
let e = div k (binade fm) in qmin fm + (if e = 0 then 0 else e - 1)
96
function
sig
(fm: format) (k: int) : int = k - (uexp fm k - qmin fm) * binade fm
97
Valid (1.1s) (colibri2)
98
let ghost
vom_dec
(fm: format) (k: int) : unit
99
requires { 0 <= k }
100
ensures { qmin fm <= uexp fm k /\ 0 <= sig fm k < 2 * binade fm }
101
ensures { qmin fm < uexp fm k -> binade fm <= sig fm k }
102
ensures { k = (uexp fm k - qmin fm) * binade fm + sig fm k }
103
ensures { vom fm k = from_int (sig fm k) *. pow2r (uexp fm k) }
104
ensures { vom fm (k + 1) = from_int (sig fm k + 1) *. pow2r (uexp fm k) }
105
= {proof…}
106
binade_ge_2 fm;
107
let p = binade fm in
108
assert { k = div k p * p + mod k p };
109
vom_s fm (uexp fm k) (sig fm k);
110
vom_s_succ fm (uexp fm k) (sig fm k)
111
{qed}
112
Valid (17ms) (colibri2)
113
let ghost
vom_zero
(fm: format) : unit
114
ensures { vom fm 0 = 0.0 }
115
= {proof…} binade_ge_2 fm; assert { div 0 (binade fm) = 0 /\ mod 0 (binade fm) = 0 } {qed}

The gap between two neighbours is at least 2^qmin

  Valid (27ms) (cvc5)
118
let ghost
vom_step
(fm: format) (k: int) : unit
119
requires { 0 <= k }
120
ensures { vom fm k +. pow2r (qmin fm) <=. vom fm (k + 1) }
121
= {proof…}
122
vom_dec fm k; pow2r_le (qmin fm) (uexp fm k)
123
{qed}
124
Valid (51ms) (colibri2)
125
let rec ghost
vom_lt
(fm: format) (k l: int) : unit
126
requires { 0 <= k < l }
127
ensures { vom fm k <. vom fm l }
128
variant { l - k }
129
= {proof…}
130
pow2r_pos (qmin fm); vom_step fm (l - 1);
131
if k < l - 1 then vom_lt fm k (l - 1)
132
{qed}
133
Valid (26ms) (colibri2 4) (cvc5) (split_vc 2) (depth 2)
134
let rec ghost
vom_ge
(fm: format) (k: int) : unit
135
requires { 0 <= k }
136
ensures { from_int k *. pow2r (qmin fm) <=. vom fm k }
137
variant { k }
138
= {proof…}
139
if k = 0 then vom_zero fm
140
else begin vom_ge fm (k - 1); vom_step fm (k - 1) end
141
{qed}

The neighbours of a real

145
predicate
between
(fm: format) (k: int) (r: real) =
146
0 <= k /\ vom fm k <=. r <. vom fm (k + 1)
147
Valid (24ms) (colibri2)
148
let rec ghost function
find_between
(fm: format) (r: real) (n: int) : int
149
requires { 0.0 <=. r /\ 0 <= n /\ r <. vom fm n }
150
ensures { between fm result r }
151
variant { n }
152
= {proof…} vom_zero fm; {qed}
153
if pure { vom fm (n - 1) <=. r } then n - 1
154
else find_between fm r (n - 1)

The magnitude rounded down of r >= 0

  Valid (29ms) (colibri2)
157
let ghost function
kdn
(fm: format) (r: real) : int
158
requires { 0.0 <=. r }
159
ensures { between fm result r }
160
= let c = pow2r (qmin fm) in
161
let n = pure { Truncate.floor (r /. c) + 1 } in
162
{proof…}
163
pow2r_pos (qmin fm);
164
assert { r /. c <. from_int n };
165
assert { r <. from_int n *. c by r = (r /. c) *. c };
166
assert { 0 <= n };
167
vom_ge fm n;
168
{qed}
169
find_between fm r n
170
Valid (415ms) (colibri2 4) (split_vc) (depth 1)
171
let ghost
kdn_unique
(fm: format) (k: int) (r: real) : unit
172
requires { between fm k r }
173
ensures { kdn fm r = k }
174
= {proof…}
175
let j = kdn fm r in
176
if j < k then (if j + 1 < k then vom_lt fm (j + 1) k)
177
else if k < j then (if k + 1 < j then vom_lt fm (k + 1) j)
178
{qed}
179
end