Common — library colibrilib.dyadic — module Dyadic
16
module Dyadic
17
use int.Int
18
use int.Power
19
use int.EuclideanDivision
20
use option.Option
21
use real.RealInfix
22
use real.FromInt
23
use colibrilib.pow2r.Pow2r
24
use colibrilib.dv.Dv

The predicates

x is an integer multiple of 2^k

29
predicate
fix
(x: real) (k: int) = dv x (pow2r k)

x is m 2^e with |m| < 2^p

32
predicate
flt
(x: real) (p: int) =
33
exists m e: int. x = from_int m *. pow2r e /\ - power 2 p < m < power 2 p

The domain

lo: fix x lo, so a finite lo excludes the non–dyadic numbers; hi: a nonzero x is not a multiple of 2^(hi+1) (the domain always holds 0); prec: flt x prec. None, and a negative prec, are no information.

41
type
t
= {
lo
: option int;
hi
: option int;
prec
: option int }
42
43
predicate
mem_lo
(x: real) (l: option int) =
44
match l with None -> true | Some k -> fix x k end
45
predicate
mem_hi
(x: real) (h: option int) =
46
match h with None -> true | Some k -> x <> 0.0 -> not fix x (k + 1) end
47
predicate
mem_prec
(x: real) (p: option int) =
48
match p with None -> true | Some k -> 0 <= k -> flt x k end
49
50
predicate
mem
(x: real) (d: t) =
51
mem_lo x d.lo /\ mem_hi x d.hi /\ mem_prec x d.prec
52
53
let function
mk
(lo hi prec: option int) : t = { lo = lo; hi = hi; prec = prec }
54
55
let constant
top
: t = { lo = None; hi = None; prec = None }

Facts on fix

  Valid (16ms) (colibri2)
59
let ghost
fix_zero
(k: int) : unit
60
ensures { fix 0.0 k }
61
= dv_zero (pow2r k)

A multiple of 2^k' is a multiple of 2^k, k <= k'

  Valid (22ms) (colibri2)
64
let ghost
fix_mono
(x: real) (k k': int) : unit
65
requires { k <= k' /\ fix x k' }
66
ensures { fix x k }
67
= {proof…}
68
let n = quot x (pow2r k') in
69
pow2r_add k (k' - k); pow2r_int (k' - k);
70
assert { from_int (n * power 2 (k' - k)) = from_int n *. from_int (power 2 (k' - k)) };
71
dv_intro x (pow2r k) (n * power 2 (k' - k))
72
{qed}

The same, for every x

  Valid (5.9s) (colibri2 4) (split_vc) (depth 1)
75
let ghost
fix_mono_all
(k k': int) : unit
76
requires { k <= k' }
77
ensures { forall x. fix x k' -> fix x k }
78
= {proof…}
79
pow2r_add k (k' - k); pow2r_int (k' - k);
80
assert { forall n. from_int (n * power 2 (k' - k)) =
81
from_int n *. from_int (power 2 (k' - k)) };
82
assert { forall x n. x = from_int n *. pow2r k' ->
83
x = from_int (n * power 2 (k' - k)) *. pow2r k }
84
{qed}
85
Valid (66ms) (colibri2)
86
let ghost
flt_mono_all
(p q: int) : unit
87
requires { 0 <= p <= q }
88
ensures { forall x. flt x p -> flt x q }
89
= assert { power 2 p <= power 2 q }
90
Valid (18ms) (colibri2)
91
let ghost
fix_add
(x y: real) (k: int) : unit
92
requires { fix x k /\ fix y k }
93
ensures { fix (x +. y) k }
94
= dv_add x y (pow2r k)
95
Valid (18ms) (colibri2)
96
let ghost
fix_sub
(x y: real) (k: int) : unit
97
requires { fix x k /\ fix y k }
98
ensures { fix (x -. y) k }
99
= dv_sub x y (pow2r k)
100
Valid (33ms) (colibri2)
101
let ghost
fix_neg
(x: real) (k: int) : unit
102
ensures { fix (-. x) k <-> fix x k }
103
= {proof…}
104
if pure { fix x k } then dv_neg x (pow2r k);
105
if pure { fix (-. x) k } then dv_neg (-. x) (pow2r k)
106
{qed}
107
Valid (57ms) (colibri2)
108
let ghost
fix_mul
(x y: real) (k j: int) : unit
109
requires { fix x k /\ fix y j }
110
ensures { fix (x *. y) (k + j) }
111
= {proof…}
112
let n = quot x (pow2r k) in
113
let m = quot y (pow2r j) in
114
pow2r_add k j;
115
assert { from_int (n * m) = from_int n *. from_int m };
116
assert { x *. y = from_int (n * m) *. pow2r (k + j) };
117
dv_intro (x *. y) (pow2r (k + j)) (n * m)
118
{qed}
119
Valid (50ms) (colibri2 16) (cvc5 3) (split_vc 6) (depth 4)
120
let ghost
flt_mul
(x y: real) (p q: int) : unit
121
requires { flt x p /\ flt y q /\ 0 <= p /\ 0 <= q }
122
ensures { flt (x *. y) (p + q) }
123
= {proof…}
124
let n = any int ensures { exists e. x = from_int result *. pow2r e /\
125
- power 2 p < result < power 2 p } in
126
let e = any int ensures { x = from_int n *. pow2r result } in
127
let m = any int ensures { exists f. y = from_int result *. pow2r f /\
128
- power 2 q < result < power 2 q } in
129
let f = any int ensures { y = from_int m *. pow2r result } in
130
pow2r_add e f; assert { power 2 (p + q) = power 2 p * power 2 q };
131
let a = if n < 0 then - n else n in
132
let b = if m < 0 then - m else m in
133
assert { a * b < power 2 p * power 2 q
134
by (a * b <= a * power 2 q by b < power 2 q /\ 0 <= a)
135
so (a = 0 \/ a * power 2 q < power 2 p * power 2 q) };
136
assert { - power 2 (p + q) < n * m < power 2 (p + q)
137
by n * m = a * b \/ n * m = - (a * b) };
138
assert { from_int (n * m) = from_int n *. from_int m };
139
assert { x *. y = from_int (n * m) *. pow2r (e + f) }
140
{qed}

A nonzero multiple of 2^k is at least 2^k in magnitude

  Valid (32ms) (colibri2 7) (cvc5 2) (split_vc) (depth 1)
143
let ghost
fix_nz_ge
(x: real) (k: int) : unit
144
requires { fix x k /\ x <> 0.0 }
145
ensures { x <=. -. pow2r k \/ pow2r k <=. x }
146
= {proof…}
147
let n = quot x (pow2r k) in
148
pow2r_pos k;
149
assert { n <> 0 };
150
let p = pow2r k in
151
if n > 0 then begin
152
assert { from_int n >=. 1.0 };
153
assert { x -. p = (from_int n -. 1.0) *. p };
154
assert { (from_int n -. 1.0) *. p >=. 0.0 }
155
end else begin
156
assert { from_int n <=. -. 1.0 };
157
assert { -. p -. x = (-. from_int n -. 1.0) *. p };
158
assert { (-. from_int n -. 1.0) *. p >=. 0.0 }
159
end
160
{qed}

An integer of magnitude at most 2^p, 1 <= p, has p bits and is a multiple of 2^0

  Valid (64ms) (colibri2)
164
let ghost
int_dyadic
(n p: int) : unit
165
requires { 1 <= p /\ - power 2 p <= n <= power 2 p }
166
ensures { fix (from_int n) 0 /\ flt (from_int n) p }
167
= {proof…}
168
assert { pow2r 0 = 1.0 };
169
dv_intro (from_int n) (pow2r 0) n;
170
assert { 2 <= power 2 p by power 2 p = 2 * power 2 (p - 1) /\ power 2 (p - 1) >= 1 };
171
if n = power 2 p then begin
172
pow2r_int p;
173
assert { from_int n = from_int 1 *. pow2r p }
174
end else if n = - power 2 p then begin
175
pow2r_int p;
176
assert { from_int n = from_int (-1) *. pow2r p }
177
end else
178
assert { from_int n = from_int n *. pow2r 0 }
179
{qed}

Meet and join

183
let function
min_o
(a b: option int) : option int =
184
match a, b with None, _ | _, None -> None
185
| Some x, Some y -> Some (if x <= y then x else y) end
186
let function
max_o
(a b: option int) : option int =
187
match a, b with None, _ | _, None -> None
188
| Some x, Some y -> Some (if x <= y then y else x) end

Every domain holds 0

  Valid (85ms) (colibri2)
191
let ghost
mem_zero
(d: t) : unit
192
ensures { mem 0.0 d }
193
= {proof…}
194
match d.lo with Some k -> fix_zero k | None -> () end;
195
match d.prec with
196
| Some k -> if 0 <= k then assert { 0.0 = from_int 0 *. pow2r 0 }
197
| None -> () end
198
{qed}

The bound of the exponents of the reals (clamp), and the domain of {0} that every domain lo > hi is: it is the least of them, so that their meets do not move without end

203
let constant
zbound
: int = 32768
204
let constant
zero_d
: t = { lo = Some zbound; hi = Some (- zbound); prec = Some 0 }

A domain with hi < lo holds only 0

  Valid (22ms) (colibri2)
207
let ghost
zero_only
(x: real) (d: t) (l h: int) : unit
208
requires { mem x d /\ d.lo = Some l /\ d.hi = Some h /\ h < l }
209
ensures { x = 0.0 }
210
= if pure { x <> 0.0 } then fix_mono x (h + 1) l
211
Valid (48ms) (colibri2)
212
let ghost
zero_d_mem
(x: real) : unit
213
ensures { mem x zero_d <-> x = 0.0 }
214
= {proof…}
215
mem_zero zero_d;
216
if pure { mem x zero_d } then zero_only x zero_d zbound (- zbound)
217
{qed}

The meet as a logic function: the result of inter (for the specifications of the environment: fp_conv.Env.upddr)

221
function
meet_lo
(a b: option int) : option int =
222
match a, b with
223
| None, l | l, None -> l
224
| Some x, Some y -> Some (if x <= y then y else x)
225
end
226
function
meet_hi
(a b: option int) : option int =
227
match a, b with
228
| None, h | h, None -> h
229
| Some x, Some y -> Some (if x <= y then x else y)
230
end
231
function
meet_prec
(a b: option int) : option int =
232
match a, b with
233
| None, p | p, None -> p
234
| Some x, Some y ->
235
Some (if x < 0 then y else if y < 0 then x else if x <= y then x else y)
236
end
237
function
meet
(a b: t) : t =
238
let rl = meet_lo a.lo b.lo in
239
let rh = meet_hi a.hi b.hi in
240
match rl, rh with
241
| Some l, Some h -> if h < l then zero_d else mk rl rh (meet_prec a.prec b.prec)
242
| _ -> mk rl rh (meet_prec a.prec b.prec)
243
end

The equality of two domains

  Valid (29ms) (colibri2)
246
let
deq
(a b: t) : bool
247
ensures { result <-> a = b }
248
= let eqo (x y: option int) : bool ensures { result <-> x = y } =
249
match x, y with
250
| None, None -> true
251
| Some u, Some v -> u = v
252
| _ -> false
253
end in
254
eqo a.lo b.lo && eqo a.hi b.hi && eqo a.prec b.prec

The meet: the intersection, exactly (fix and flt are monotonic); a domain of {0} is zero_d

  Valid (1.2s) (colibri2 16) (cvc5 5) (split_vc 7) (depth 4)
258
let
inter
(a b: t) : t
259
ensures { forall x. mem x result <-> mem x a /\ mem x b }
260
ensures { result = meet a b }
261
= let rl = match a.lo, b.lo with
262
| None, l | l, None -> l
263
| Some x, Some y -> Some (if x <= y then y else x) end in
264
let rh = match a.hi, b.hi with
265
| None, h | h, None -> h
266
| Some x, Some y -> Some (if x <= y then x else y) end in
267
let rp = match a.prec, b.prec with
268
| None, p | p, None -> p
269
| Some x, Some y ->
270
Some (if x < 0 then y else if y < 0 then x else if x <= y then x else y) end in
271
{proof…}
272
match a.lo, b.lo with
273
| Some u, Some v -> if u <= v then fix_mono_all u v else fix_mono_all v u
274
| _ -> () end;
275
match a.hi, b.hi with
276
| Some u, Some v ->
277
if u <= v then fix_mono_all (u + 1) (v + 1) else fix_mono_all (v + 1) (u + 1)
278
| _ -> () end;
279
match a.prec, b.prec with
280
| Some u, Some v ->
281
if 0 <= u && 0 <= v then begin
282
if u <= v then flt_mono_all u v else flt_mono_all v u end
283
| _ -> () end;
284
{qed}
285
match rl, rh with
286
| Some l, Some h ->
287
if h < l then begin
288
{proof…}
289
let lemma z (x: real) : unit
290
ensures { mem x zero_d <-> mem x (mk rl rh rp) }
291
= zero_d_mem x; mem_zero (mk rl rh rp);
292
if pure { mem x (mk rl rh rp) } then zero_only x (mk rl rh rp) l h in
293
{qed}
294
zero_d
295
end else mk rl rh rp
296
| _ -> mk rl rh rp
297
end

Sums

  Valid (47ms) (colibri2)
301
let ghost
fix_add_all
(k: int) : unit
302
ensures { forall x y. fix x k -> fix y k -> fix (x +. y) k }
303
= {proof…}
304
assert { forall n m. from_int (n + m) = from_int n +. from_int m };
305
assert { forall x y n m. x = from_int n *. pow2r k -> y = from_int m *. pow2r k ->
306
x +. y = from_int (n + m) *. pow2r k }
307
{qed}
308
Valid (41ms) (colibri2)
309
let ghost
fix_sub_all
(k: int) : unit
310
ensures { forall x y. fix x k -> fix y k -> fix (x -. y) k }
311
= {proof…}
312
assert { forall n m. from_int (n - m) = from_int n -. from_int m };
313
assert { forall x y n m. x = from_int n *. pow2r k -> y = from_int m *. pow2r k ->
314
x -. y = from_int (n - m) *. pow2r k }
315
{qed}

hi (x + y) <= hi x when hi x < lo y and x is nonzero

  Valid (1.6s) (colibri2 3) (split_vc) (depth 1)
318
let ghost
add_hi_all
(h l: int) : unit
319
requires { h < l }
320
ensures { forall x y. x <> 0.0 -> not fix x (h + 1) -> fix y l ->
321
not fix (x +. y) (h + 1) }
322
= {proof…}
323
fix_mono_all (h + 1) l; fix_sub_all (h + 1);
324
assert { forall x y. x +. y -. y = x }
325
{qed}

The sum; anz (bnz): the first (second) operand is nonzero

  Valid (804ms) (colibri2 7) (cvc5) (split_vc) (depth 1)
328
let
add
(a b: t) (anz bnz: bool) : t
329
ensures { forall x y. mem x a -> mem y b -> (anz -> x <> 0.0) ->
330
(bnz -> y <> 0.0) -> mem (x +. y) result }
331
= let rl = min_o a.lo b.lo in
332
{proof…}
333
match a.lo, b.lo with
334
| Some u, Some v ->
335
let k = if u <= v then u else v in
336
fix_mono_all k u; fix_mono_all k v; fix_add_all k
337
| _ -> () end;
338
{qed}
339
let hi_of (ha: option int) (lb hb: option int) (nz: bool) : option int
340
ensures { forall x y. mem_hi x ha -> mem_lo y lb -> mem_hi y hb ->
341
(nz -> x <> 0.0) ->
342
match result with None -> true | Some k -> mem_hi (x +. y) (Some k) end }
343
= match ha, lb with
344
| Some h, Some l ->
345
if h < l then begin
346
add_hi_all h l;
347
if nz then Some h
348
else match hb with
349
| Some h' ->
350
let k = if h <= h' then h' else h in
351
fix_mono_all (h + 1) (k + 1); fix_mono_all (h' + 1) (k + 1);
352
assert { forall y. 0.0 +. y = y };
353
Some k
354
| None -> None end end
355
else None
356
| _ -> None
357
end in
358
let rh = match hi_of a.hi b.lo b.hi anz with
359
| Some k -> Some k
360
| None -> hi_of b.hi a.lo a.hi bnz end in
361
mk rl rh None

Negation and difference

  Valid (788ms) (colibri2) (cvc5 2) (split_vc) (depth 1)
365
let ghost
neg_mem
(x: real) (d: t) : unit
366
ensures { mem (-. x) d <-> mem x d }
367
= {proof…}
368
match d.lo with Some k -> fix_neg x k | None -> () end;
369
match d.hi with Some k -> fix_neg x (k + 1) | None -> () end;
370
match d.prec with
371
| Some p ->
372
assert { forall m e. x = from_int m *. pow2r e -> -. x = from_int (- m) *. pow2r e };
373
assert { forall m e. -. x = from_int m *. pow2r e -> x = from_int (- m) *. pow2r e }
374
| None -> () end
375
{qed}

The difference, and the backward step of a sum: x = s - y

  Valid (68ms) (colibri2)
378
let
sub
(a b: t) (anz bnz: bool) : t
379
ensures { forall x y. mem x a -> mem y b -> (anz -> x <> 0.0) ->
380
(bnz -> y <> 0.0) -> mem (x -. y) result }
381
= let r = add a b anz bnz in
382
{proof…}
383
let lemma nm (y: real) ensures { mem y b -> mem (-. y) b } = neg_mem y b in
384
assert { forall x y. x -. y = x +. (-. y) };
385
{qed}
386
r

Products

The valuation of a nonzero dyadic x = n 2^l

  Valid (376ms) (colibri2)
391
let rec ghost
valuation
(x: real) (l n: int) : int
392
requires { x <> 0.0 /\ x = from_int n *. pow2r l }
393
ensures { l <= result /\ fix x result /\ not fix x (result + 1) }
394
variant { if n < 0 then - n else n }
395
= {proof…}
396
pow2r_succ l; pow2r_pos l;
397
if mod n 2 = 0 then begin
398
assert { n = 2 * div n 2 /\ div n 2 <> 0 };
399
assert { from_int n = 2.0 *. from_int (div n 2) };
400
assert { x = from_int (div n 2) *. pow2r (l + 1) };
401
assert { (if div n 2 < 0 then - div n 2 else div n 2) < (if n < 0 then - n else n) };
402
valuation x (l + 1) (div n 2)
403
end else begin
404
dv_intro x (pow2r l) n;
405
if pure { fix x (l + 1) } then begin
406
let m = quot x (pow2r (l + 1)) in
407
assert { from_int n *. pow2r l = from_int (2 * m) *. pow2r l };
408
assert { n = 2 * m };
409
absurd
410
end;
411
l
412
end
413
{qed}

n and m odd: n m is odd

  Valid (140ms) (colibri2 2) (cvc4) (split_vc) (depth 1)
416
let ghost
odd_mul
(n m: int) : unit
417
requires { mod n 2 = 1 /\ mod m 2 = 1 }
418
ensures { mod (n * m) 2 = 1 }
419
= {proof…}
420
assert { n = 2 * div n 2 + 1 /\ m = 2 * div m 2 + 1 };
421
assert { n * m = 2 * (2 * div n 2 * div m 2 + div n 2 + div m 2) + 1 }
422
{qed}

The valuation of a product is the sum of the valuations

  Valid (61ms) (colibri2)
425
let ghost
val_mul
(x y: real) (k j: int) : unit
426
requires { fix x k /\ not fix x (k + 1) /\ fix y j /\ not fix y (j + 1) }
427
ensures { fix (x *. y) (k + j) /\ not fix (x *. y) (k + j + 1) }
428
= {proof…}
429
fix_mul x y k j;
430
pow2r_succ k; pow2r_succ j; pow2r_pos k; pow2r_pos j;
431
let n = quot x (pow2r k) in
432
let m = quot y (pow2r j) in
433
if mod n 2 = 0 then begin
434
assert { n = 2 * div n 2 };
435
assert { x = from_int (div n 2) *. pow2r (k + 1) }; absurd end;
436
if mod m 2 = 0 then begin
437
assert { m = 2 * div m 2 };
438
assert { y = from_int (div m 2) *. pow2r (j + 1) }; absurd end;
439
odd_mul n m;
440
pow2r_add k j; pow2r_succ (k + j); pow2r_pos (k + j);
441
if pure { fix (x *. y) (k + j + 1) } then begin
442
let p = quot (x *. y) (pow2r (k + j + 1)) in
443
assert { from_int (n * m) = from_int n *. from_int m };
444
assert { x *. y = from_int (n * m) *. pow2r (k + j) };
445
assert { from_int (n * m) *. pow2r (k + j) = from_int (2 * p) *. pow2r (k + j) };
446
assert { n * m = 2 * p };
447
absurd
448
end
449
{qed}

A nonzero x with fix x k and not fix x (h + 1): k <= h

  Valid (20ms) (colibri2)
452
let ghost
fix_le_hi
(x: real) (k h: int) : unit
453
requires { fix x k /\ not fix x (h + 1) }
454
ensures { k <= h }
455
= {proof…} if k > h then fix_mono x (h + 1) k {qed}

The product: lo and prec add; hi adds when both lo are finite (dyadic factors)

A factor ±2^e (or 0) keeps the bits of the other

  Valid (56ms) (colibri2 6) (cvc5) (split_vc) (depth 1)
460
let ghost
flt_mul_pow2
(x y: real) (q: int) : unit
461
requires { flt x 1 /\ flt y q /\ 0 <= q }
462
ensures { flt (x *. y) q }
463
= {proof…}
464
let n = any int ensures { exists e. x = from_int result *. pow2r e /\ -2 < result < 2 } in
465
let e = any int ensures { x = from_int n *. pow2r result } in
466
let m = any int ensures { exists f. y = from_int result *. pow2r f /\
467
- power 2 q < result < power 2 q } in
468
let f = any int ensures { y = from_int m *. pow2r result } in
469
pow2r_add e f;
470
assert { x *. y = from_int (n * m) *. pow2r (e + f) };
471
assert { n * m = 0 \/ n * m = m \/ n * m = - m }
472
{qed}
473
Valid (829ms) (colibri2 33) (cvc4) (cvc5 5) (split_vc 9) (depth 5)
474
let
mul
(a b: t) : t
475
ensures { forall x y. mem x a -> mem y b -> mem (x *. y) result }
476
= let rl = match a.lo, b.lo with
477
| Some u, Some v -> Some (u + v) | _ -> None end in
478
let rh = match a.lo, b.lo, a.hi, b.hi with
479
| Some _, Some _, Some u, Some v -> Some (u + v) | _ -> None end in
480
let rp = match a.prec, b.prec with
481
| Some u, Some v ->
482
if 0 <= u && 0 <= v then
483
Some (if u <= 1 then v else if v <= 1 then u else u + v)
484
else None
485
| _ -> None end in
486
{proof…}
487
match a.lo, b.lo with
488
| Some u, Some v ->
489
let lemma lo_mul (x y: real) requires { fix x u /\ fix y v }
490
ensures { fix (x *. y) (u + v) } = fix_mul x y u v in ()
491
| _ -> () end;
492
match a.prec, b.prec with
493
| Some u, Some v -> if 0 <= u && 0 <= v then begin
494
if u <= 1 then begin
495
flt_mono_all u 1;
496
let lemma prec_mul (x y: real) requires { flt x u /\ flt y v }
497
ensures { flt (x *. y) v } = flt_mul_pow2 x y v in () end
498
else if v <= 1 then begin
499
flt_mono_all v 1;
500
let lemma prec_mul (x y: real) requires { flt x u /\ flt y v }
501
ensures { flt (x *. y) u } =
502
flt_mul_pow2 y x u; assert { x *. y = y *. x } in () end
503
else begin
504
let lemma prec_mul (x y: real) requires { flt x u /\ flt y v }
505
ensures { flt (x *. y) (u + v) } = flt_mul x y u v in () end
506
end
507
| _ -> () end;
508
match a.lo, b.lo, a.hi, b.hi with
509
| Some la, Some lb, Some u, Some v ->
510
let lemma hi_mul (x y: real) : unit
511
requires { fix x la /\ fix y lb /\ mem_hi x (Some u) /\ mem_hi y (Some v) }
512
ensures { mem_hi (x *. y) (Some (u + v)) }
513
= if pure { x *. y <> 0.0 } then begin
514
assert { x <> 0.0 /\ y <> 0.0 };
515
assert { not fix x (u + 1) /\ not fix y (v + 1) };
516
let kx = valuation x la (quot x (pow2r la)) in
517
let ky = valuation y lb (quot y (pow2r lb)) in
518
fix_le_hi x kx u; fix_le_hi y ky v;
519
val_mul x y kx ky;
520
if pure { fix (x *. y) (u + v + 1) } then
521
fix_mono (x *. y) (kx + ky + 1) (u + v + 1)
522
end in
523
()
524
| _ -> () end;
525
assert { forall x y. mem x a -> mem y b -> mem_lo (x *. y) rl };
526
assert { forall x y. mem x a -> mem y b -> mem_hi (x *. y) rh };
527
assert { forall x y. mem x a -> mem y b -> mem_prec (x *. y) rp };
528
{qed}
529
mk rl rh rp

The backward step of a product x y in c, on x in a; bnz: y is nonzero. hi (x) <= hi c - lo b; lo x >= lo c - hi b when lo a and lo b are finite (dyadic factors)

  Valid (302ms) (colibri2 12) (cvc5) (split_vc) (depth 1)
534
let
mul_back
(a c b: t) (bnz: bool) : t
535
ensures { forall x y. mem x a -> mem y b -> (bnz -> y <> 0.0) ->
536
mem (x *. y) c -> mem x result }
537
= let rh = match bnz, c.hi, b.lo with
538
| True, Some hc, Some lb -> Some (hc - lb) | _ -> None end in
539
let rl = match bnz, a.lo, b.lo, c.lo, b.hi with
540
| True, Some _, Some _, Some lc, Some hb -> Some (lc - hb) | _ -> None end in
541
{proof…}
542
match bnz, c.hi, b.lo with
543
| True, Some hc, Some lb ->
544
let lemma hi_back (x y: real)
545
requires { fix y lb /\ y <> 0.0 /\ mem_hi (x *. y) (Some hc) }
546
ensures { mem_hi x (Some (hc - lb)) }
547
= if pure { x <> 0.0 /\ fix x (hc - lb + 1) } then begin
548
fix_mul x y (hc - lb + 1) lb;
549
assert { x *. y <> 0.0 }
550
end in ()
551
| _ -> () end;
552
match bnz, a.lo, b.lo, c.lo, b.hi with
553
| True, Some la, Some lb, Some lc, Some hb ->
554
let lemma lo_back (x y: real)
555
requires { fix x la /\ fix y lb /\ y <> 0.0 /\ mem_hi y (Some hb) /\
556
fix (x *. y) lc }
557
ensures { fix x (lc - hb) }
558
= if pure { x = 0.0 } then fix_zero (lc - hb)
559
else begin
560
let kx = valuation x la (quot x (pow2r la)) in
561
let ky = valuation y lb (quot y (pow2r lb)) in
562
fix_le_hi y ky hb;
563
val_mul x y kx ky;
564
fix_le_hi (x *. y) lc (kx + ky);
565
fix_mono x (lc - hb) kx
566
end in ()
567
| _ -> () end;
568
{qed}
569
mk rl rh None

A bound on the exponents

The domain of a real can go up without end along a cycle of operations (x = 2 x): beyond b the information is weakened, so that the domains of the reals form a finite lattice

  Valid (338ms) (cvc5)
576
let
clamp
(b: int) (a: t) : t
577
ensures { forall x. mem x a -> mem x result }
578
= let l = match a.lo with
579
| Some l -> if l < - b then None else if l > b then Some b else Some l
580
| None -> None end in
581
let h = match a.hi with
582
| Some h -> if h > b then None else if h < - b then Some (- b) else Some h
583
| None -> None end in
584
let p = match a.prec with
585
| Some p -> if p > b then None else Some p
586
| None -> None end in
587
{proof…}
588
match a.lo with
589
| Some k -> if k > b then begin
590
let lemma lo (x: real) requires { fix x k } ensures { fix x b } = fix_mono x b k in () end
591
| None -> () end;
592
match a.hi with
593
| Some k -> if k < - b then begin
594
let lemma hi (x: real) requires { not fix x (k + 1) } ensures { not fix x (- b + 1) }
595
= if pure { fix x (- b + 1) } then fix_mono x (k + 1) (- b + 1) in () end
596
| None -> () end;
597
{qed}
598
mk l h p

Quotients by a power of 2

±2^e is a multiple of 2^k exactly when k <= e

  Valid (694ms) (colibri2)
603
let ghost
fix_pow2
(s: real) (e k: int) : unit
604
requires { s = 1.0 \/ s = -. 1.0 }
605
ensures { fix (s *. pow2r e) k <-> k <= e }
606
= {proof…}
607
if k <= e then begin
608
dv_intro (s *. pow2r e) (pow2r e) (if pure { s = 1.0 } then 1 else -1);
609
fix_mono (s *. pow2r e) k e
610
end else if pure { fix (s *. pow2r e) k } then begin
611
fix_mono (s *. pow2r e) (e + 1) k;
612
absurd
613
end
614
{qed}
615
616
let function
neg_o
(a: option int) : option int =
617
match a with None -> None | Some k -> Some (- k) end

The inverse of a power of 2 up to the sign (prec <= 1): 1/(±2^e) = ±2^(-e); else no information

  Valid (374ms) (colibri2 9) (cvc5) (split_vc) (depth 1)
621
let
inv
(a: t) : t
622
ensures { forall x. mem x a -> x <> 0.0 -> mem (1.0 /. x) result }
623
= match a.prec with
624
| Some p ->
625
if 0 <= p && p <= 1 then begin
626
{proof…}
627
let lemma pt (x: real) : unit
628
requires { mem x a /\ x <> 0.0 }
629
ensures { mem (1.0 /. x) (mk (neg_o a.hi) (neg_o a.lo) (Some 1)) }
630
= let n = any int ensures { exists e. x = from_int result *. pow2r e /\
631
- power 2 p < result < power 2 p } in
632
let e = any int ensures { x = from_int n *. pow2r result } in
633
assert { power 2 p <= 2 by p = 0 \/ p = 1 };
634
let s = from_int n in
635
assert { 1.0 /. x = from_int n *. pow2r (- e) };
636
match a.lo with Some l -> fix_pow2 s e l; fix_pow2 s (- e) (- l + 1)
637
| None -> () end;
638
match a.hi with Some h -> fix_pow2 s e (h + 1); fix_pow2 s (- e) (- h)
639
| None -> () end in
640
{qed}
641
mk (neg_o a.hi) (neg_o a.lo) (Some 1)
642
end else top
643
| None -> top
644
end

The domain of one dyadic number

A number of bits of n >= 0: n < 2^result

  Valid (40ms) (colibri2)
649
let rec
nbits
(n: int) : int
650
requires { 0 <= n }
651
ensures { 0 <= result /\ n < power 2 result }
652
variant { n }
653
= if n = 0 then 0
654
else begin
655
let k = nbits (div n 2) in
656
k + 1
657
end

The valuation and the odd significand of a nonzero x = n 2^l

  Valid (1.2s) (colibri2)
660
let rec
odd_part
(ghost x: real) (l n: int) : (int, int)
661
requires { x <> 0.0 /\ x = from_int n *. pow2r l }
662
ensures { let (k, m) = result in x = from_int m *. pow2r k /\
663
fix x k /\ not fix x (k + 1) }
664
variant { if n < 0 then - n else n }
665
= if mod n 2 = 0 then begin
666
{proof…} pow2r_succ l; {qed}
667
odd_part x (l + 1) (div n 2)
668
end else begin
669
{proof…}
670
if pure { fix x (l + 1) } then begin
671
let m = quot x (pow2r (l + 1)) in
672
assert { from_int n *. pow2r l = from_int (2 * m) *. pow2r l };
673
assert { n = 2 * m };
674
absurd
675
end;
676
{qed}
677
(l, n)
678
end

The domain of n 2^e: exact for a nonzero number (lo = hi, the bits of the odd significand); for 0, lo = z and hi < lo (any z: 0 is a multiple of every power of 2)

  Valid (349ms) (colibri2)
683
let
exact
(n e z: int) : t
684
ensures { mem (from_int n *. pow2r e) result }
685
= if n = 0 then begin
686
{proof…}
687
fix_zero z;
688
{qed}
689
mk (Some z) (Some (z - 1)) (Some 0)
690
end else begin
691
let ghost x = pure { from_int n *. pow2r e } in
692
let (k, m) = odd_part x e n in
693
let a = if m < 0 then - m else m in
694
let p = nbits a in
695
mk (Some k) (Some k) (Some p)
696
end

A valuation bound for the nonzero reals of magnitude at most |n| 2^e: they are below 2^(result+1)

  Valid (34ms) (colibri2 6) (split_vc) (depth 1)
700
let
log2_up
(n e: int) : int
701
ensures { forall x. x <> 0.0 ->
702
-. (from_int (if n < 0 then - n else n) *. pow2r e) <=. x <=.
703
from_int (if n < 0 then - n else n) *. pow2r e ->
704
mem_hi x (Some result) }
705
= let a = if n < 0 then - n else n in
706
let b = nbits a in
707
{proof…}
708
pow2r_add e b;
709
assert { from_int a *. pow2r e <. pow2r (e + b) };
710
let lemma hi (x: real)
711
requires { x <> 0.0 /\ -. (from_int a *. pow2r e) <=. x <=. from_int a *. pow2r e }
712
ensures { mem_hi x (Some (e + b - 1)) }
713
= if pure { fix x (e + b) } then begin
714
fix_nz_ge x (e + b);
715
absurd
716
end in
717
{qed}
718
e + b - 1

A class rem + div ℤ of the congruence domain, rem = rn 2^re and div = dn 2^de: its members are multiples of the powers of 2 dividing rem and div (the integers, div = 1 and rem = 0, have lo = 0); exact when div = 0

  Valid (1.0s) (colibri2)
724
let
congr
(dn de rn re: int) : t
725
ensures { forall x k. x = from_int rn *. pow2r re +. from_int k *. (from_int dn *. pow2r de) ->
726
mem x result }
727
= if dn = 0 then exact rn re 0
728
else
729
let dd = exact dn de zbound in
730
let dr = exact rn re zbound in
731
match dd.lo, dr.lo with
732
| Some kd, Some kr ->
733
let m = if kd < kr then kd else kr in
734
{proof…}
735
let lemma c (x: real) (k: int)
736
requires { x = from_int rn *. pow2r re +. from_int k *. (from_int dn *. pow2r de) }
737
ensures { fix x m }
738
= let y = pure { from_int dn *. pow2r de } in
739
dv_intro (from_int k) (pow2r 0) k;
740
fix_mul (from_int k) y 0 kd;
741
fix_mono (from_int k *. y) m kd;
742
fix_mono (from_int rn *. pow2r re) m kr;
743
fix_add (from_int rn *. pow2r re) (from_int k *. y) m in
744
{qed}
745
mk (Some m) None None
746
| _ -> top
747
end

The magnitude of the nonzero members

x <> 0 in d: lo <= hi, 2^lo <= |x| and |x| < 2^(hi+prec) (Gappa's fix_of_flt_bnd and flt_of_fix_bnd read backward)

  Valid (41ms) (colibri2 15) (cvc5) (split_vc 2) (depth 2)
753
let ghost
mag
(x: real) (d: t) : unit
754
requires { mem x d /\ x <> 0.0 }
755
ensures { match d.lo, d.hi with Some l, Some h -> l <= h | _ -> true end }
756
ensures { match d.lo with
757
| Some l -> x <=. -. pow2r l \/ pow2r l <=. x | None -> true end }
758
ensures { match d.hi, d.prec with
759
| Some h, Some p -> 0 <= p -> -. pow2r (h + p) <. x <. pow2r (h + p)
760
| _ -> true end }
761
= {proof…}
762
match d.lo with
763
| Some l ->
764
fix_nz_ge x l;
765
match d.hi with
766
| Some h -> if l > h then begin fix_mono x (h + 1) l; absurd end
767
| None -> ()
768
end
769
| None -> ()
770
end;
771
match d.hi, d.prec with
772
| Some h, Some p ->
773
if 0 <= p then begin
774
let m = any int ensures { exists e. x = from_int result *. pow2r e /\
775
- power 2 p < result < power 2 p } in
776
let e = any int ensures { x = from_int m *. pow2r result } in
777
if e > h then begin
778
dv_intro x (pow2r e) m;
779
fix_mono x (h + 1) e;
780
absurd
781
end;
782
pow2r_add p e; pow2r_le (p + e) (h + p);
783
let q = pow2r p in
784
let u = pow2r e in
785
assert { q *. u -. x = (q -. from_int m) *. u };
786
assert { (q -. from_int m) *. u >. 0.0 };
787
assert { -. pow2r p *. pow2r e <. x <. pow2r p *. pow2r e }
788
end
789
| _ -> ()
790
end
791
{qed}
792
end