Common — library colibrilib.fbin — module Round

Computing the rounding on dyadic numbers

260
module Round
261
use int.Int
262
use int.Power
263
use int.EuclideanDivision
264
use real.RealInfix
265
use real.FromInt
266
use colibrilib.fp.Widen
267
use colibrilib.fp.Ereal as E
268
use colibrilib.zarith.Zbit
269
use colibrilib.zbit.ZbitInt
270
use Pow2r
271
use Format
272
use Float

dm * 2^de

275
type
dyadic
= {
dm
: int;
de
: int }
276
277
function
dval
(d: dyadic) : real = from_int d.dm *. pow2r d.de
278
Valid (22ms) (colibri2)
279
let
pow2_int
(n: int) : int
280
requires { 0 <= n }
281
ensures { result = power 2 n }
282
= {proof…} lsl_mul 1 n; {qed} lsl_int 1 n
283
Valid (30ms) (colibri2)
284
let
binade_p
(fm: format) : int
285
ensures { result = binade fm }
286
= pow2_int (fm.sb - 1)
287
Valid (24ms) (colibri2)
288
let
nb_sign_p
(fm: format) : int
289
ensures { result = nb_sign fm }
290
= (pow2_int fm.eb - 1) * binade_p fm + 1
291
Valid (29ms) (colibri2)
292
let
qmin_p
(fm: format) : int
293
ensures { result = qmin fm }
294
= 2 - (pow2_int (fm.eb - 1) - 1) - fm.sb
295
Valid (20ms) (colibri2 2) (split_vc) (depth 1)
296
let ghost
mul_lt_cancel
(x y c: int) : unit
297
requires { 0 < c /\ x * c < y * c + c }
298
ensures { x <= y }
299
= {proof…} if x > y then assert { x * c >= (y + 1) * c } {qed}

The parity, by the lowest bit

  Valid (32ms) (colibri2)
302
let
even
(k: int) : bool
303
ensures { result <-> mod k 2 = 0 }
304
= {proof…}
305
let ghost h = div k 2 in
306
if mod k 2 = 0 then begin assert { k = 2 * h }; even_bittest h 0 end
307
else begin assert { k = 2 * h + 1 }; odd_bittest h 0 end;
308
{qed}
309
not (test_bit k 0)

The rounding of a * 2^e, a > 0, on the magnitudes

  Valid (977ms) (colibri2 59) (cvc4 2) (cvc5 4) (split_vc 6) (depth 3)
312
let
round_mag_d
(fm: format) (m: mode) (a e: int) : int
313
requires { 0 < a }
314
ensures { result = round_mag fm m (from_int a *. pow2r e) }
315
= let p = binade_p fm in
316
let q = qmin_p fm in
317
let nb = numbits a in
318
let u = if nb - fm.sb + e < q then q else nb - fm.sb + e in
319
let ghost r = pure { from_int a *. pow2r e } in
320
{proof…}
321
binade_ge_2 fm;
322
numbits_lsl_lt a; numbits_lsl_le a;
323
lsl_mul 1 nb; lsl_mul 1 (nb - 1);
324
assert { power 2 nb = 2 * power 2 (nb - 1) };
325
assert { power 2 (nb - 1) <= a < power 2 nb };
326
{qed}
327
if u <= e then begin
328
let s = lsl_int a (e - u) in
329
{proof…}
330
lsl_mul a (e - u);
331
assert { power 2 (e - u + nb) = power 2 (e - u) * power 2 nb };
332
assert { s < 2 * p by
333
s < power 2 (e - u) * power 2 nb = power 2 (e - u + nb)
334
/\ e - u + nb <= fm.sb /\ power 2 fm.sb = 2 * p
335
/\ power 2 (e - u + nb) <= power 2 fm.sb };
336
assert { q < u -> p <= s by
337
u = nb - fm.sb + e
338
so power 2 (e - u) * power 2 (nb - 1) = power 2 (e - u + nb - 1) = p };
339
let k = (u - q) * p + s in
340
vom_s fm u s; vom_s_succ fm u s;
341
pow2r_add u (e - u); pow2r_int (e - u); pow2r_pos u;
342
assert { vom fm k = r };
343
assert { vom fm (k + 1) = from_int (s + 1) *. pow2r u };
344
scale_cmp s (s + 1) (pow2r u);
345
kdn_unique fm k r;
346
{qed}
347
(u - q) * p + s
348
end else begin
349
let sh = u - e in
350
let s = asr_int a sh in
351
let pw = pow2_int sh in
352
let rem = a - s * pw in
353
let k = (u - q) * p + s in
354
{proof…}
355
asr_div a sh;
356
assert { 0 <= rem < pw /\ a = s * pw + rem };
357
assert { power 2 fm.sb = 2 * p };
358
assert { power 2 (sh + fm.sb) = pw * (2 * p) };
359
assert { power 2 nb <= power 2 (sh + fm.sb) };
360
mul_lt_cancel s (2 * p - 1) pw;
361
if pure { q < u } then begin
362
assert { power 2 (sh + fm.sb - 1) = pw * p };
363
assert { power 2 (sh + fm.sb - 1) = power 2 (nb - 1) };
364
mul_lt_cancel p s pw
365
end;
366
vom_s fm u s; vom_s_succ fm u s;
367
pow2r_add e sh; pow2r_int sh; pow2r_pos e;
368
let ghost c = pure { pow2r e } in
369
assert { vom fm k = from_int (s * pw) *. c };
370
assert { vom fm (k + 1) = from_int (s * pw + pw) *. c };
371
assert { r = from_int (s * pw + rem) *. c };
372
scale_cmp (s * pw) (s * pw + rem) c;
373
scale_cmp (s * pw + rem) (s * pw + pw) c;
374
kdn_unique fm k r;
375
{qed}
376
if rem = 0 then k
377
else match m with
378
| RTN | RTZ -> k
379
| RTP -> k + 1
380
| RNE | RNA ->
381
let h = pow2_int (sh - 1) in
382
{proof…}
383
assert { pw = 2 * h };
384
assert { (vom fm k +. vom fm (k + 1)) /. 2.0 = from_int (s * pw + h) *. c };
385
scale_cmp (s * pw + rem) (s * pw + h) c;
386
{qed}
387
if rem < h then k
388
else if rem > h then k + 1
389
else match m with RNA -> k + 1 | _ -> if even k then k else k + 1 end
390
end
391
end
392
Valid (59ms) (colibri2)
393
let
of_mag_p
(fm: format) (m: mode) (neg: bool) (k: int) : t
394
requires { 0 <= k }
395
ensures { result = of_mag fm m neg k }
396
= let nb = nb_sign_p fm in
397
if k < nb - 1 then mk fm (Finite neg k)
398
else match m with
399
| RTN | RTZ -> {proof…} binade_ge_2 fm; assert { 1 <= power 2 fm.eb - 1 }; {qed}
400
mk fm (Finite neg (nb - 2))
401
| _ -> mk fm (if neg then MinusInf else PlusInf)
402
end

The rounding of a dyadic number

  Valid (939ms) (colibri2 14) (cvc5) (split_vc) (depth 1)
405
let
round_d
(fm: format) (m: mode) (zneg: bool) (d: dyadic) : t
406
ensures { result = round_f fm m zneg (E.Fin (dval d)) }
407
= {proof…} binade_ge_2 fm; {qed}
408
if d.dm = 0 then begin
409
{proof…}
410
vom_zero fm; pow2r_pos 1;
411
vom_lt fm 0 1;
412
assert { between fm 0 0.0 };
413
kdn_unique fm 0 0.0;
414
assert { dval d = 0.0 };
415
{qed}
416
mk fm (Finite zneg 0)
417
end else if d.dm > 0 then begin
418
let k = round_mag_d fm m d.dm d.de in
419
{proof…}
420
pow2r_pos d.de; let _ = kdn fm (dval d) in ();
421
{qed}
422
if k = 0 then mk fm (Finite zneg 0) else of_mag_p fm m false k
423
end else begin
424
let k = round_mag_d fm (mirror m) (- d.dm) d.de in
425
{proof…}
426
pow2r_pos d.de; let _ = kdn fm (-. dval d) in ();
427
assert { -. dval d = from_int (- d.dm) *. pow2r d.de };
428
{qed}
429
if k = 0 then mk fm (Finite zneg 0) else of_mag_p fm (mirror m) true k
430
end

The exact operations on dyadic numbers

  Valid (32ms) (colibri2)
433
let
dadd
(a b: dyadic) : dyadic
434
ensures { dval result = dval a +. dval b }
435
= if a.de <= b.de then begin
436
{proof…}
437
lsl_mul b.dm (b.de - a.de); pow2r_add a.de (b.de - a.de); pow2r_int (b.de - a.de);
438
{qed}
439
{ dm = a.dm + lsl_int b.dm (b.de - a.de); de = a.de }
440
end else begin
441
{proof…}
442
lsl_mul a.dm (a.de - b.de); pow2r_add b.de (a.de - b.de); pow2r_int (a.de - b.de);
443
{qed}
444
{ dm = lsl_int a.dm (a.de - b.de) + b.dm; de = b.de }
445
end
446
Valid (21ms) (colibri2)
447
let
dmul
(a b: dyadic) : dyadic
448
ensures { dval result = dval a *. dval b }
449
= {proof…} pow2r_add a.de b.de; {qed}
450
{ dm = a.dm * b.dm; de = a.de + b.de }
451
452
predicate
is_finite
(x: t) = match x.value with Finite _ _ -> true | _ -> false end

The dyadic number of a finite float: its significand and the exponent of its ulp

  Valid (46ms) (colibri2 9) (cvc5) (split_vc 3) (depth 3)
456
let
to_dyadic
(x: t) : dyadic
457
requires { is_finite x }
458
ensures { dval result = to_real x }
459
= match x.value with
460
| Finite neg k ->
461
let fm = x.fmt in
462
let p = binade_p fm in
463
let q = qmin_p fm in
464
let e = asr_int k (fm.sb - 1) in
465
{proof…} asr_div k (fm.sb - 1); {qed}
466
let s = k - e * p in
467
let u = if e = 0 then q else e - 1 + q in
468
let sg = if e = 0 then s else p + s in
469
{proof…}
470
binade_ge_2 fm;
471
assert { e = div k p /\ s = mod k p };
472
assert { vom fm k = from_int sg *. pow2r u };
473
assert { from_int (- sg) *. pow2r u = -. (from_int sg *. pow2r u) };
474
assert { to_real x = if neg then -. vom fm k else vom fm k };
475
{qed}
476
{ dm = if neg then - sg else sg; de = u }
477
| _ -> absurd
478
end
479
end